{'fraction_non_alphanumeric': 0.04554500483311537, 'fraction_numerical': 0.014158185023028373, 'mean_word_length': 4.560543787543471, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Composite Optimization with Coupling Constraints via Dual Proximal Gradient Method with Applications to Asynchronous Networks

In this paper, we consider solving a composite optimization problem with coupling constraints in a multi-agent network based on proximal gradient method. In this problem, all the agents jointly minimize the sum of individual cost functions composed of smooth and possibly non-smooth parts. To this end, we derive the dual problem by the concept of Fenchel conjugate, which gives rise to the dual proximal gradient algorithm by allowing for the asymmetric individual interpretations of the global constraints. Then, an asynchronous dual proximal gradient algorithm is proposed for the asynchronous networks with heterogenous step-sizes and communication delays. For both the two algorithms, if the non-smooth parts of the objective functions are simple-structured, we only need to update dual variables by some simple operations, accounting for the reduction of the overall computational complexity. Analytical convergence rate of the proposed algorithms is derived and their efficacy is verified by solving a social welfare optimization problem of electricity market in the numerical simulation.


Background and Motivation
Decentralized optimization has drawn much attention due to its prominent advantage in solving various mathematical optimization problems with large data set and decentralized decision variables in multi-agent networks. 1,2,3 In those problems, each agent usually maintains a local decision variable, and the optimal solution of the system is achieved through multiple rounds of communications and strategy-makings. 4 In this work, we consider a class of optimization problems with composite cost functions, i.e., composed of smooth (differentiable) and possibly non-smooth (non-differentiable) parts, arising from various fields, such as Lasso regressions, resource allocation problems and support vector machines. 5,6,7 To solve those problems, most existing works require the update of primal variables with some costly computations, which increase the overall computational complexity. Meanwhile, with the presence of the asynchrony of large-scale networks in various fields, more explorations on asynchronous optimization algorithms are needed. 8 As widely discussed, proximal gradient based algorithms can take the advantage of some simple-structured cost functions and are usually numerically more stable than the subgradient based counterparts. 9 With the above motivation, in this work, we aim to develop an efficient optimization algorithm for decentralized optimization problems (DOPs) based on proximal gradient method and further investigate its efficacy in asynchronous networks.

Literature Review
In this work, we focus on optimizing a class of composite DOPs subject to affine coupling constraints. To solve these problems, applicable techniques include primal-dual subgradient methods, 10 alternating direction method of multipliers, 11 and proximal gradient methods, 12 etc. DOPs with coupling constraints are actively investigated in the recent works, 13,14,15,16,17,18,19,20,21,22 where the optimal solution to the primal problems is usually achieved with the update of both primal and dual variables. An alternative solution, as discussed by Notarnicola et al., 23,24 is resorting to the dual problems, where the computation on the primal variables is not required. However, the algorithms in References 23 and 24 involve some inner-loop optimization processes, which increase the overall computational complexity if the primal cost functions possess some non-smooth characteristics. To further improve the computational efficiency, dual proximal gradient (DPG) methods for solving composite optimization problems were investigated recently, 25,6,26 where, however, no general affine coupling constraint was considered.
To explore some efficient decentralized algorithms, different from the existing works, the new features of this work are twofold. First, to the best knowledge of the authors, this is the first work that investigates DPG method with general affine constraints with specific network typologies. By the proposed DPG algorithm, the updating of the primal variables is not compulsory. Furthermore, if the proximal mapping of the non-smooth parts in the primal problem can be explicitly given, we only need to update the dual variables by some simple operations, 1 e.g., basic proximal mappings and gradient based iterations, which technically can be more efficient than the existing algorithms with some costly computations on the primal variables or other auxiliary variables. 13,14,15,16,17,18,19,20,21,22 As another feature, the asymmetric individual interpretation of the agents on the global constraints is considered, where no uniform knowledge of the global constraints is required.
Second, we propose an asynchronous dual proximal gradient (Asyn-DPG) algorithm, which can be viewed as an extension of DPG algorithm by considering heterogenous step-sizes and communication delays. Specifically, the outdated information is addressed through deterministic analysis, 28,29,30,31,32,33,34,35 which is advantageous over some stochastic models 36 in the sense that the probability distribution of random factors can be difficult to acquire in some problems and may introduce inaccuracy issues due to limited historical data. 37 However, the problem setup in References 28, 29, 31-35 either only considers certain special form of affine coupling constraints or does not incorporate any coupling constraint. In addition, the algorithms discussed in References 30 and 33 dealing with smooth cost functions will hamper their usage in non-smooth optimization problems. Different from all the aforementioned works, we will show that if the upper bound of communication delays is finite and the nonsmooth parts in the primal problem are simple-structured, we only need to update dual variables with some simple operations, which is still a distinct advantage to reduce the computational complexity.
We hereby summarize the contributions of this work as follows.
• We consider a class of composite DOPs with both local convex and affine coupling constraints. To solve these problems, a DPG algorithm is proposed by formulating the dual problems. Then, an Asyn-DPG algorithm is built upon the structure of DPG algorithm, which can be applied to asynchronous networks with heterogenous step-sizes and communication delays. In addition, the asymmetric individual interpretations of the global constraints are considered, which is more adaptive to large-scale networks in the sense that no uniform knowledge of the global constraints for the agents is required.
• Provided that the non-smooth parts of the cost functions in the primal DOPs are with some simple structures, the proposed DPG and Asyn-DPG algorithms only require the update of dual variables with some simple operations, accounting for the reduction of the overall computational complexity. In addition, our algorithms require some commonly used assumptions on the primal problems and explicit convergence rates are provided for all the discussed scenarios.

Paper Structure and Notations
The remainder of this paper is organized as follows. Section 2 presents some frequently used definitions in this work and their properties. Section 3 formulates the primal problem of interest and gives some basic assumptions. In Section 4, two proximal gradient algorithms, namely DPG and Asyn-DPG, are proposed based on different network settings. The convergence analysis of the discussed algorithms is conducted in Section 5. The efficacy of the proposed algorithms is verified by a numerical simulation in Section 6. Section 7 concludes this paper. N and N + denote the non-negative and positive integer spaces, respectively. Let notation |  | be the size of set . Operator (⋅) ⊤ represents the transpose of a matrix.  1 ×  2 denotes the Cartesian product of sets  1 and  2 .
 represents the relative interior of set . Let ⌊ ⌋ (⌈ ⌉) be the largest integer smaller than (smallest integer no smaller than) scalar . ‖ ⋅ ‖ 1 and ‖ ⋅ ‖ refer to the 1 and 2 -norms, respectively. ⟨⋅, ⋅⟩ is an inner product operator. ⊗ is the Kronecker product operator. and denote the -dimensional column vectors with all elements being 0 and 1, respectively. and × denote the -dimensional identity matrix and ( × )-dimensional zero matrix, respectively.

PRELIMINARIES
In this section, we present some fundamental definitions and properties of graph theory, proximal mapping, and Fenchel conjugate.

Graph Theory
A multi-agent network can be described by an undirected graph  = {, }, which is composed of the set of vertices  = {1, 2, ..., } and set of edges  ⊆ {( , )| , ∈  and ≠ } with ( , ) ∈  an unordered pair (no self-loop). A graph  is said connected if there exists at least one path between any two distinct vertices. A graph  is said fully connected if there is a unique edge between any two distinct vertices.  = { |( , ) ∈ } denotes the set of the neighbours of agent . Let ∈ R × denote the Laplacian matrix of . Let be the element at the cross of the th row and th column of . Thus, (1)

PROBLEM FORMULATION
The considered optimization problem and relevant assumptions are presented in this section.

DUAL PROXIMAL GRADIENT BASED ALGORITHM DEVELOPMENT
In this section, we will develop two dual proximal gradient based algorithms for solving the problem of interest under different assumptions on networks.

Dual Problem
By introducing a slack vector = [ ⊤ 1 , ..., ⊤ ] ⊤ , Problem (P2) can be equivalently written as Then, the Lagrangian function of Problem (P3) can be written as where we use .., ⊤ ] ⊤ ∈ R . and denote the Lagrangian multiplier vectors associated with constraints ( ) = ( ) and = , respectively. Therefore, the dual function can be obtained by minimizing ( , , , ) with ( , ), which gives where = [ ×( Then, the dual problem of Problem (P3) can be formulated as Define  as the set of the optimal solutions to Problem (P4).

Discussion on Constraints
Assumption 4 can be satisfied in some DOPs. See Examples 1 to 4.

Example 1.  is fully connected.
Example 2. In some applications, e.g., telecommunication and machine learning problems, ( ) = ( ) can be defined by an edge-constraint maintained by agent . 47 ( , ) ∉  and ≠ , then the constraints of Problem (P3) can be written as = with = ⊗ ∈ R × , which means Problem (P3) essentially is a consensus optimization problem. 48,49,50 Example 4. Consider a set of consensus constraints of agent : − = , ∀ ∈  . 25 Then, for any agent pair ( , ) ∈ , the individual constraints of agents and include − = and − = , respectively. Therefore, the asymmetric constraints can be viewed as a generalization of the asymmetric consensus constraints discussed in this example.

Remark 1.
In Examples 1-4, the asymmetric constraints are more adaptive to large-scale networks in the sense that establishing a global = by integrating the overall decentralized or even distributed constraints may be costly, especially when the network sizes and individual constraints vary constantly. 51,52 3 For example, when certain agent joins the network, he only needs to broadcast ( ) to neighbours such that can be augmented directly as in Problem (P3), without changing the network-wide constraint architecture seriously by rebuilding = .
In practice, the asymmetric individual constraints can be generated by interpreting some common global constraints by userdefined linear transformations. For instance, agent may interpret constraint = by transformation = , i.e., ( ) = and ( ) = . See Example 5.

Dual Proximal Gradient Algorithm
In this subsection, we propose a DPG algorithm to solve Problem (P4). The DPG algorithm is designed as which means , ..., ∇ ⊤ ] ⊤ and > 0, ∈ N. The proximal mapping for computing is omitted since is not contained by .

: end for
To apply (21), one need to derive (i) ⋄ for and and (ii) the proximal mapping of ( + I Ω ) ⋄ for , ∈ . For (i), ⋄ can be easily obtained if is simple-structured, e.g., is a quadratic function. 46, Sec. 3.3.1 For (ii), a feasible method is introduced in the following remark, which can avoid the calculation of the proximal mapping of ( + I Ω ) ⋄ .

Remark 3.
Based on Lemma 1, the updating of in Algorithm 1 can be equivalently written as with ⋄ ( ) = ( + I Ω ) ⋄⋄ ( ) = ( + I Ω )( ) due to the convexity and lower semi-continuity of + I Ω , where ( + I Ω ) ⋄⋄ is the biconjugate of + I Ω . 46, Sec. 3.3.2 4 With this arrangement, the calculation of the proximal mapping of ( + I Ω ) ⋄ is not required as shown in (25), which reduces the computational complexity when the proximal mapping of + I Ω is easier to obtain by available formulas. 40, Sec. 6.3 For example, in some 1 regularization problems (e.g., ( ) = ‖ ‖ 1 , Ω = R ), the proximal mapping of 1 -norm is known as the soft thresholding operator with analytical solution. 40,Sec. 6.3 In addition, if = 0 (i.e., smooth cost functions with local constraints), the proximal mapping of I Ω is an Euclidean projection onto Ω . 12, Sec. 1.2 Additional to the method in Remark 3, the following remark explains how to implement DPG algorithm for certain general form of + I Ω .
(26) can be solved with gradient descent method by computing the gradient of with the help of Lemma 2, i.e., which can be completed with local information. In this case, the DPG algorithm can adapt to general nonsmooth + I with a compromise on an inner-loop optimization process.

Asynchronous Dual Proximal Gradient Algorithm
In the following, we propose an Asyn-DPG algorithm by extending the usage of DPG algorithm to asynchronous networks.
In synchronous networks, the information accessed by the agents is assumed to be up-to-date, which requires efficient data transmission and can be restrictive for some large-scale networks. 53 To address this issue, we propose an Asyn-DPG algorithm for asynchronous networks by considering communication delays. To this end, based on the setup of Problem (P4), we define ( ) as the time instant previous to instant with − ( ) ≥ 0. 5 Therefore, the accessed dual information at instant may not be the latest version ( ) but a historical version ( ( )). It is reasonable to assume that certain agent always knows the latest information of itself. The upper bound of delays is a commonly used assumption in asynchronous networks. 55,28 By allowing for the heterogenous steps-sizes, the proposed Asyn-DPG algorithm is designed as The computation mechanism of the Asyn-DPG algorithm is shown in Algorithm 2 and Fig. 2. Receive ∇ ( ( ( ))) from neighbour ∈  .

: end for
Note that (28) can be decomposed as indicated in (22) and (23), i.e., Remark 5. Similar to the discussion in Remark 3, the updating of in Algorithm 2 can be rewritten as to reduce the computational complexity.

CONVERGENCE ANALYSIS AND DISCUSSION
The convergence analysis of the proposed DPG and Asyn-DPG algorithms is conducted in this section.

Lemma 3. With Assumption 2, the Lipschitz constant of ∇ ( ) is given by
See the proof in Appendix A.

Theorem 1.
Suppose that Assumptions 1-4 hold. Let 1 = ℎ. By Algorithm 1, for any * ∈  and ∈ N + , we have Note that the structure of (19) is consistent with the ISTA algorithm with a constant step-size. 56 Therefore, the result of Theorem 1 can be deduced with the existing proof by employing the Lipschitz constant ℎ. 56,Thm. 3.1 Hence, detailed proof is omitted for simplicity. Lemma 4. Based on Assumption 5, for certain ∈ N + , we have See the proof in Appendix B.

NUMERICAL RESULT
In this section, we will verify the feasibility of Algorithms 1 and 2 by considering a social welfare optimization problem in an electricity market with 2 utility companies (UCs) and 3 energy users.

Simulation Setup
The social welfare optimization problem of the market is formulated as follows.
where , , , , are parameters, ∀ ∈  UC , ∀ ∈  user . The values of the parameters are set in Table I. 57 To apply the DPG algorithm, we define ( ),UC and ( ),user as the asymmetric constraint matrices of UC and user , respectively. Then, by following the derivation of (4), the Lagrangian function of Problem (P5) can be obtained as ( , , , )

Simulation 1
To apply Algorithm 1, we consider a fully connected network since all the agents are involved in supply-demand balance constraint.
With the same asymmetric constraints in Simulation 1, the simulation result is shown in Fig. 5. It can be seen that, with different delays, the minimum of Ψ( ), i.e., Ψ * , is achieved asymptotically, which implies the optimal solution to the primal problem is achieved since Simulations 1 and 2 are based on the same setup of Problem (P4). In Fig. 5, one can also note that a larger delay can slower the convergence speed, which is consistent with result (37), i.e., a larger value of can produce a larger error bound in certain step.

CONCLUSION
In this work, we focused on optimizing a class of composite DOPs with both local convex and affine coupling constraints. With different network settings, two dual proximal gradient based algorithms were proposed. As the key feature, all the discussed algorithms resort to the dual problem. Provided that the non-smooth parts of the cost functions are simple-structured, we only need to update dual variables with some simple operations, which leads to the reduction of the overall computational complexity.

D MATRICES AND LAGRANGIAN FUNCTION IN SECTION 6
The asymmetric constraint matrices of UC and user are given by