On Distributed Convex Optimization Under Inequality and Equality Constraints

By Minghui Zhu, Sonia Martínez. IEEE Transactions on Automatic Control, 2010

744 citations recorded by the source corpus.

We consider a general multi-agent convex optimization problem where the agents are to collectively minimize a global objective function subject to a global inequality constraint, a global equality constraint, and a global constraint set. The objective function is defined by a sum of local objective functions, while the global constraint set is produced by the intersection of local constraint sets. In particular, we study two cases: one where the equality constraint is absent, and the other where the local constraint sets are identical. We devise two distributed primal-dual subgradient algorithms based on the characterization of the primal-dual optimal solutions as the saddle points of the Lagrangian and penalty functions. These algorithms can be implemented over networks with dynamically changing topologies but satisfying a standard connectivity property, and allow the agents to asymptotically agree on optimal solutions and optimal values of the optimization problem under the Slater's condition.

Subfields: Computer Networks and Communications, Public Health, Environmental and Occupational Health

View Paper: https://www.semanticscholar.org/paper/4360c0f7c650e671c6e6ba0e9ec443bd1462cbc9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

1. Angelia Nedić
2. Alexander Olshevsky
3. Wei Shi
4. Wotao Yin
5. Ali H. Sayed
6. Qing Ling
7. Na Li
8. Guannan Qu

In Public Health, Environmental and Occupational Health

1. Angelia Nedić
2. Wei Shi
3. Alexander Olshevsky
4. Yiguang Hong
5. Na Li
6. Guannan Qu
7. Ziyang Meng
8. Soomin Lee

Citations in the corpus

• Fast Distributed Gradient Methods (2011, neutral): “2298712 also [9]–[11]); [12] (see also [13]); [14] (see also [3], [15]); and [16].”
• Multi-Agent Distributed Optimization via Inexact Consensus ADMM (2014, neutral): “There is an extensive literature on distributed consensus o ptimization methods, such as the consensus subgradient methods; see [6], [7] and the recent developmen ts in [8], [9], [15], [16].”
• A Decentralized Bilateral Energy Trading System for Peer-to-Peer Electricity Markets (2020, methodology): “ing direction method of multipliers (ADMM) [10], primal-dual gradient methods [11], [12], and consensus-based methods [13],”
• Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication (2014, neutral): “Literature review : In distributed convex optimiza-(cid:63) tion, most coordination algorithms are time-varying, consensus-based dynamics [Boyd et al., 2010, Duchi et al., 2012, Johansson et al., 2009, Nedi´c and Ozdaglar, 2009, Zhu and Mart´ınez, 2012] implemented in discrete time.”
• EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2014, background): “1) has additional constraints that force x into a bounded set, which also leads to bounded (sub)gradients and a Hessian, projected first-order algorithms are applicable [27, 37].”
• Control-Theoretic Methods for Cyberphysical Security: Geometric Principles for Optimal Cross-Layer Resilient Control Systems (2015, background): “Finally, security issues of specific cyberphysical systems have received considerable attention, such as power networks [22]–[27], linear networks with misbehaving components [28]–[30], and water networks [31]–[33].”
• A survey of distributed optimization (2019, background): “The constrained optimization problem (15) then reduces to: where the function h : R n → R p is defined as h For the case where local constraint sets are identical, the authors of Zhu and Martínez (2012) developed a distributed penalty primal-dual subgradient algorithm with a diminishing step-size.”
• When does a digraph admit a doubly stochastic adjacency matrix? (2010, background): “Examples include distributed averaging [1], [2] [3], [4], distributed convex optimization [5], [6], [7], an d gossip algorithms [8], [9].”
• Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, background): “Other works on distributed algorithms that also require the use of diminishing step-sizes include [19, 40, 78].”
• Designing games for distributed optimization (2011, methodology): “g, subgradient methods [21]–[26], consensus based methods [1], [2], [27], or two-step consensus based approaches [9], [28], is predicated on the structure of the system level objective.”
• EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2014, background): “When (1.1) has additional constraints that force x in a bounded set, which also leads to bounded (sub)gradients and Hessian, projected first-order algorithms are applicable [27,37].”
• Distributed optimization for multi-task learning via nuclear-norm approximation (2015, background): “Literature review: The increasing body of literature on cooperative strategies for distributed convex optimization, see (Nedic and Ozdaglar, 2009; Boyd et al., 2011; Zhu and Mart́ınez, 2012; Gharesifard and Cortés, 2014) and references therein, renders itself naturally to large-scale problems like d”
• Distributed dual averaging method for multi-agent optimization with quantized communication (2012, methodology): “More recently, in the work [7], to take the inequality and equality constraints into consideration, the authors propose two methods, namely, the distributed Lagrangian primal–dual subgradient method and the distributed penalty primal–dual subgradient method, in which the basic ideas are to character”