{'fraction_non_alphanumeric': 0.04818787170233315, 'fraction_numerical': 0.01646927260712652, 'mean_word_length': 4.4543942334349875, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Distributed Convex Optimization With Coupling Constraints Over Time-Varying Directed Graphs

This paper considers a distributed convex optimization problem over a time-varying multi-agent network, where each agent has its own decision variables that should be set so as to minimize its individual objective subject to local constraints and global coupling equality constraints. Over directed graphs, a distributed algorithm is proposed that incorporates the push-sum protocol into dual subgradient methods. Under the convexity assumption, the optimality of primal and dual variables, and constraint violations is first established. Then the explicit convergence rates of the proposed algorithm are obtained. Finally, some numerical experiments on the economic dispatch problem are provided to demonstrate the efficacy of the proposed algorithm.


Introduction
Due to the emergence of large-scale networks, distributed optimization problems have attracted recently considerable interests in many fields such as the control and operational research communities, wireless and social networks [4], [5], power systems [6], [7], robotics [8], and name a few. These problems share some common characteristics: the entire optimization objective function can be decomposed into the sum of several individual objective functions over a network, and each individual only knows its own objective function, and only individual and its neighbors cooperate to solve the problem by interacting the network information locally [11]. Many researchers have investigated various multi-agent optimization problems arising in the engineering community [9,14,22,25].
In literatures, consensus based distributed algorithms for solving distributed problems are mainly divided into three classes: primal consensus based algorithms, dual consensus based algorithms and primal-dual consensus based algorithms, see [11,13,12,29,30] In [11], Nedić et al. firstly proposed a distributed subgradient algorithm with provable convergence rates, while its stochastic variant was investigated in [26] and its asynchronous variant in [27].
Based on dual averaging methods, Duchi et al. [13] proposed a distributed dual averaging algorithm and obtained the convergence rate, scaling inversely in the spectral gap of the networks. Resorting to Lagrange dual method, the papers [12,35] designed a distributed primal-dual algorithm for solving distributed problem with equality or inequality constraints.
However, distributed methods proposed in most to previous works require the use of doubly stochastic weight matrices, which are not easily constructed in a distributed fashion when the graphs are directed.
To overcome this issue, the work in [10] proposed a different distributed subgradient approach in directed and fixed network topology, in which the messages among agents is propagated by "push-sum" protocol. The push-sum based distributed method eliminates the requirement of graph balancing, however, the communication protocol is required to know the number of agents or the graph. Although the authors in [15] canceled the requirement of a balanced graph and proposed a push-subgradient approach with an explicit convergence rate at order of O(lnt/ √ t), they only investigated the unconstrained distributed optimization problems. Very recently, the reference [28] proposed a Push-DIGing method that uses column stochastic matrices and fixed step-sizes, which can achieve a geometric rate.
The problems for solving distributed optimization subject to equality or (and) inequality constraints has received considerable attentions [12,35,2,16,31,32]. In [12], Zhu et al. firstly proposed a distributed Lagrangian primal-dual subgradient method by characterizing the primal-dual optimal solutions as the saddle points of the Lagrangian function related to the problem under consideration. Yuan et al. in [35] developed a variant of the distributed primal-dual subgradient method by introducing multistep consensus mechanism.
For more general distributed optimization problems with inequality constraints that couple all the agents' decision variables, Chang et al. [2] designed a novel distributed primal-dual perturbed subgradient method and obtained the estimates on convergence rate, also see [3].
By making use of dual decomposition and proximal minimization, Falsone et al. [17] pro-posed a novel distributed method to solve inequality-coupled optimization problems. Their proposed approach can converge to some optimal dual solution of the centralized problem counterpart, while the primal variables converge to the set of optimal primal solutions. However, the implementation of the algorithm proposed in [17] requires the double stochasticity of communication weight matrices, without any estimates on the convergence rate of their proposed method.
In this paper, we investigate a distributed optimization problem subject to coupling equality constraints over time-varying directed networks. Under the framework of dual decomposition, we propose a distributed dual subgradient method with push-sum protocol to solve this problem. Under the assumption of directed graphs, we prove the optimality of dual and primal variables, and obtain the explicit convergence rates of the proposed method.
Compared to existing literatures, the contributions of this paper are two folds: i) Relaxations undirected graphs to directed graphs. The work in [15] proposed a pushsum based distributed method to unconstrained optimization problems. By resorting to dual methods and push-sum protocols, we propose distributed dual subgradient method to solve a class of convex optimization subject to coupling equality constraints. Our algorithm can be viewed as an extension of push-sum based algorithms [15] to a constrained setting. The consensus based primal-dual distributed methods proposed in [12,35] require that the networks are undirected and the communication weight matrices are double stochastic, which are unrealistic over directed networks. By utilizing the push-sum scheme considered in [10,15], our method can deal with distributed optimization problems over time-varying directed graphs, only needing the column stochastic matrices.
ii) Estimates on the convergence rate of the proposed method. The reference in [17] analyze the convergence of dual optimality and primal optimality, without investigating constraint violations of the problem interest. In our algorithm, we extend the algorithm in [17] to directed graphs, and establish the convergence results for dual optimality, primal optimality and constraint violations. More importantly, we obtain the explicit convergence rate of the proposed algorithm.
The remainder of this paper is organized as follows. We state the problem and related assumptions in Section 2. Section 3 proposes the solution method and main results. Section 4 provides the proof of main results. Numerical simulations are given in Section 5. Finally, Section 6 draws some conclusions.
Notation: We use boldface to distinguish the scalars and vectors in R n . For instance, is a scalar and u i [t] is a vector. For a matrix D, we will use the D i j to show its i, j'th entry.
We use ||x|| to denote the Euclidean norm of a vector x, ||x|| 1 denote the ℓ 1 norm of a vector x, and 1 represent the vector of ones.
2. Distributed optimization with coupling equality constraints

Problem statement and dual decomposition
Consider a time-varying network with m agents which would like to cooperatively solve the following minimization problem: where each agent i, i = 1, . . . , m only knows its own vector x i ∈ R n i of n i decision variables, its local constraint set X i ⊆ R n i , objective function f i (x i ) : R n i → R, and all agents subject to the coupling equality constraints For examples, distributed model predictive control [23], network utility maximization [1], real-time pricing problems for smart grid [21,7,24] can be modeled in this class of problems.
To decouple the coupling equality constraints, we utilize the Lagrange dual method.
Firstly, we introduce the Lagrangian function L(x, λ ) of problem (1), given by where L(x, λ ): Note that the Lagrangian function L(x, λ ) is separable with respect to x i , i = 1, . . ., m. Thus, the dual function φ (λ ) can be rewritten as where φ i (λ ) can be regarded as the dual function of agent i, i = 1, . . ., m. It is obvious that the dual function φ (λ ) is concave but non-smooth generally.
Then, the dual problem of problem (1) can be written as max λ min x∈X L(x, λ ), or, equivalently, The coupling equality constraints between agents is represented by the fact that λ is a common decision vector and all the agents should agree on its value.

Assumptions
The following assumptions on the problem (1) and on the communication time-varying network are required to show properties of convergence for the proposed algorithm.
Note that, under Assumption 1, for any is the relative interior of the constrained set X .
We assume that each agent can communicate with other agents over a time-varying network. The communication topology is modeled by a directed graph represent the collection of in-neighbors and N out i [t] represent the collection of out-neighbors of agent i at time t, respectively. That is, where ( j, i) represents agent j may send its information to agent i. And let d i (t) be the out-degree of agent i, i.e., Note that the communicated weight matrix D[t] is column-stochastic. In our paper, we do not require the assumption of double-stochastic on D[t]. We need the following assumption on the weight matrix D[t], which can be found in [15], [20].

Assumption 3. i) Every agent i knows its out-degree d i [t] at every time t; ii) The graph sequence G [t] is B-strongly connected, namely, there exists an integer B
is strongly connected, for all k ≥ 0.

Distributed dual sub-gradient push-sum algorithm
Generally, the problem (1) could be solved in a centralized manner [19]. However, if the number m of agents is significantly large, this may cause computational challenge. Additionally, each agent would be required to share its own information, such as the objective f i , the constraints X i and (A i , b i ), either with the other agents or with a central coordinate collecting all information, which is possibly undesirable in many cases, due to privacy concerns [17].
To overcome both the computational challenge and the privacy issues stated above, we propose a Distributed Dual Sub-Gradient Push-Sum algorithm (DDSG-PS, for short) by resorting to solve the dual problem (4). Our proposed algorithm DDSG-PS is motivated by the sub-gradient push-sum method [15] and dual decomposition [24,17], described as in 7: It is shown in [20,1] that the local primal vector x i [t] does not converge to the optimal solution x * i to problem (1) in general. As compared to x i [t], however, the following recursive auxiliary primal iterates shows better convergence properties with [11,12,2]. In a similar way, we introduce an recursive auxiliary dual iterates as follows Remark 1. i) Motivated by the algorithm proposed in [15], we solve an optimization problem with coupling equality constraints by resorting to dual methods, while the problem considered in [15] has no coupling equality constraints. Our algorithm can be viewed as an extension of push-sum based algorithms [15] to a constrained setting.
ii) The primal-dual distributed methods proposed in [12,35] require that each agent generates local copies of primal and dual variables, which then are optimized and exchanged.
This, however, immediately leads to an increased computational and communication effort, which indeed scale as the number of agents. In our method instead agents need to only optimize local variables and just exchange the estimate of dual variables, which are as many as the number of coupling constraints. The required local computational effort is thus much smaller when the number of coupling constraints is low compared to the overall dimensionality of primal decision variables.
iii) Under the assumption that the network is undirected, the work in [17] obtain the convergence of dual optimality and primal optimality, without considering constraint violations of the problem interest. In our algorithm, we extend the algorithm in [17] to directed graphs.
We establish the convergence results for dual optimality, primal optimality and constraint violation, stated as in Theorem 1 below. More importantly, we derive the explicit convergence rate of the proposed algorithm, presented in the following Theorems 2 and 3.

Main results
In this section, we show that the convergence results of the proposed Algorithm 1. Moreover, we provide the explicit estimates on the convergence rate of objective function' values and constraint violations.
Then, for some x * ∈ X * and λ * ∈ Λ * , we have that where c > 0 is a constant, and ξ > 0 and η ∈ (0, 1) satisfy ξ ≥ 1 m mB , η ≤ (1 − 1 m mB ) ii) More importantly, Theorem 2 shows that the diffidence between the iterative sequence of primal objective function {F( x[t + 1])} and the optimal value F(x * ) converges at a rate of with the constant depending on the initial values µ[0] at the agents, the subgradient norm G of dual function, and on both the speed η of the network information diffusion and the imbalances ξ of influence among the agents.

Proof of main results
We first prove the result that the dual optimal solutions are restricted in some specific sets, which will be useful to deduce the convergence of Algorithm 1. (4) is bounded, i.e., there an exist constant C > 0 such that 0 ≤ ||λ * || ≤ C.

Lemma 1. Under the Assumptions 1 and 2, the dual optimal solution λ * of dual problem
Proof. Lettingx ∈ X be a Slater vector, it holds that ∑ m i A ixi − b i = 0. Under Assumption 2, the strong duality holds, that is, for all λ ∈ R p , x ∈ X where x(λ ) = arg min x∈X L(x, λ ). By (8), it gives rise to Using the inequality above and the fact ∑ m Letting x i =x i + e l i in (9), where e l i denote the unit vector such that the l i th component of e l i equals to 1, and the other components of e l i are 0, l i = 1, 2, . . ., n i , we have Similarly, selecting x i =x i − e l i , we obtain By (10) and (11), for all λ ∈ R p , we get Choosing a bounded vectorλ ∈ R p randomly and letting λ =λ in the above inequality, it leads to LettingC l i be an arbitrary value larger than max{ Since the vector ∑ m i=1 (A i e l i ) is a constant in (13), ||λ * || is bounded. Note that x i =x i ± e l i may not belong to X i , butx i is an interior point of X i , so there exists a small number ε > 0 such that x i =x i ± εe l i ∈ X i . Then we can still have the same conclusion as above. The proof of this lemma is completed.
Next we establish a fundamental lemma, which is helpful to prove the main results.

Lemma 2. Under the Assumptions 1-3, for all
x ∈ X and λ ∈ R p , we have, ).
Proof. By Step 8 of Algorithm 1 and the column-stochasticity of matrix D[t] defined by (6), we can obtain Due to ||A i x i − b i || ≤ G i , for any λ ∈ R p , it follows from (14) that Considering the cross-term (15), we have Using the Cauchy-Schwartz inequality, we can get For the second term of right-hand side in (16), we can obtain

By
Step 7 of Algorithm 1, we get Using the inequality as above and (18), we have where the last inequality uses the definition of the function L j given by (2). Finally, combining (15), (16), (17) and (19), we can obtain the conclusion.
In what follows, we give the well-known Supermartingale Convergence Theorem [18], refer to Lemma 3, which is useful to prove Theorem 1.
} be a non-negative scalar sequence such that We are ready to give the proof of main results. We firstly prove Theorem 1 to show the optimality of dual and primal variables, and constraint violations.
Next we prove the ii) of Theorem 1. By the definition of x i [t + 1], it can be rewritten as implying that x i [t + 1] is a convex combination of past values of x i [t + 1]. Thus, for all t ≥ 0, .

By Step 8 of Algorithm 1 and the column-stochasticity of matrix D[t], it follows that
Since lim t→∞ µ[t + 1] = λ * , we further get It follows from (25) and the above relation that which completes the proof of ii) in Theorem 1.
Now we begin to prove the iii) of Theorem 1. Considering the quantity 2 ∑ m i=1 L i ( x i [t + 1], λ * ), and using the convexity of L(·, λ ) and (24), we obtain Rearranging the terms in (20) and letting t = r, we have where the second inequality is due to L(x * , µ[r]) ≤ L(x * , λ * ). Combining (27) and (26), we can obtain By (23), the stepsize rule (7) and the fact that lim t→∞ µ[t + 1] = λ * , each term of right-hand side in (28) is convergent to zero as t → ∞, thus, we can obtain Note that L( x[t + 1], λ * ) ≥ L(x * , λ * ), we further get Since L(·, λ * ) is continuous and convex for any λ * , all limit points of { x[t]} t→∞ are feasible and achieve the optimal value. This means that these limit points are optimal for the primal problem, thus, the proof of Theorem 1 is completed.
Theorem 2 shows the convergence rate of the objective function's value under Assumptions 1-3.
Proof of Theorem 2: By Lemma 2, for any x ∈ X and λ ∈ R p , we can obtain Dividing both sides in above inequality by 2 m ∑ t r=0 β [r + 1], for any x ∈ X , λ ∈ R p and t > 0, we have Note that L(·, λ ) is convex, it follows that .
Similarly, due to the concavity of L(x, ·), it holds Thus, for all x ∈ X, λ ∈ R p , we obtain ).

Numerical simulations
In this section we report and illustrate some experimental results of the proposed algorithm.
We consider the economic dispatch problem (EDP), which is vital in power system operation [34]. EDP is commonly formulated as an optimization problem, where the objective is to minimize the total generation cost while meeting total demand and subjecting to individual generator output constraints: where p i is the power generation of generator i, m is the number of generators, p min i /p max i are the corresponding minimum/maximum generation output, D is the total demand, C i is the cost function of generator i.
In practice, individual generator i only holds itself private information including the cost C i and generation limits p min i , p max i for privacy concern. Thus, centralized optimization methods are often unavailable.
The proposed Algorithm DDSG-PS is examined on IEEE 57-bus test system with 7 generators [33]. The cost function of each generator i is taken as C i (p i ) = a i p 2 i + b i p i + c i , and the parameters of all the generators are given in Table 1 [33]. The local demand at each generator is set as (241.0712,100.0000,74.8088,100.0000,550.0000,100.0000,410.0000) (MW) with total demand D = 1575.88 MW.  It can seen that Algorithm DDSG-PS can gradually approximate the optimal solution in a very short time. Figure 1(c) illustrates the evolution of total generations versus total demand.
From Figure 1(c), we can find that the outputs of total generation indeed meet the total demand. Figures 1(a), 1(b) and 1(c) validate our theoretical results. As shown in Figure 1(d), the iterative values of of total cost function are rapidly convergent to the optimal value (red solid line).

Conclusions
In this paper, a distributed algorithm for convex optimization with local and coupling constraints over time-varying directed networks was proposed. The algorithm incorporated the push-sum protocol into dual subgradient methods. The optimality of primal and dual variables, and constraint violations was established. Moreover, the explicit convergence rates of the proposed algorithm were obtained. Some numerical results showed that the proposed method is efficacy.