Constrained Consensus and Optimization in Multi-Agent Networks

By Angelia Nedić, Asuman E. Ozdaglar, Pablo A. Parrilo. 2008

2,041 citations recorded by the source corpus.

We present distributed algorithms that can be used by multiple agents to align their estimates with a particular value over a network with time-varying connectivity. Our framework is general in that this value can represent a consensus value among multiple agents or an optimal solution of an optimization problem, where the global objective function is a combination of local agent objective functions. Our main focus is on constrained problems where the estimates of each agent are restricted to lie in different convex sets. To highlight the effects of constraints, we first consider a constrained consensus problem and present a distributed "projected consensus algorithm" in which agents combine their local averaging operation with projection on their individual constraint sets. This algorithm can be viewed as a version of an alternating projection method with weights that are varying over time and across agents. We establish convergence and convergence rate results for the projected consensus algorithm. We next study a constrained optimization problem for optimizing the sum of local objective functions of the agents subject to the intersection of their local constraint sets. We present a distributed "projected subgradient algorithm" which involves each agent performing a local averaging operation, taking a subgradient step to minimize its own objective function, and projecting on its constraint set. We show that, with an appropriately selected stepsize rule, the agent estimates generated by this algorithm converge to the same optimal solution for the cases when the weights are constant and equal, and when the weights are time-varying but all agents have the same constraint set.

Subfields: Computer Networks and Communications

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

Citations in the corpus

An Overview of Recent Progress in the Study of Distributed Multi-Agent Coordination (2012, background): “Further results on this topic can be found in [111]–[113], where a similar distributed multi-agent optimization problem was studied within various scenarios, under constraints [111], over random networks [112], and with broadcast-based communications in an asynchronous setting [113].”
Distributed Alternating Direction Method of Multipliers (2012, background): “The computation at each step can be very inexpensive and lead to distributed implementations [4], [9], [8], [11], [13], [14].”
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization (2017, methodology): “nalysis in this case is more involved, as it requires some form of error bound results (also known as set regularity conditions). This algorithm, including random set-selections, have been studied in [55]–[58] for synchronous updates over time-varying graphs and for gossip-based asynchronous updates”
Fast Distributed Gradient Methods (2011, background): “ distributed optimization studies basically two types of algorithms with inherent tradeoffs: 1) The ﬁrst type correspond to distributed gradient-like methods, namely, primal (sub) gradient [9], [10], [11], [12], [13], [14], [15], dual averaging [16], [17], [18], and primal-dual (sub)gradient [19]. T”
On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers (2013, neutral): “3 Several follow-up papers considered variants of this method for problems with local and global constraints [26], [36] randomly varying networks [29], [30], [31] and random gradient errors [42], [34].”
Accelerating the Convergence Rates of Distributed Subgradient Methods with Adaptive Quantization (2018, methodology): “1b for absolute loss, Algorithm 1 performs almost as well as the one without quantization [24], and signiﬁcantly better than the algorithms in [7,8]”
Recent Advances in Consensus of Multi-Agent Systems: A Brief Survey (2017, background): “[84], consensus with delays [10], [59], [61], [78], [91], [100], [104], optimal consensus [32], [50], [79], sampled-data consensus [61], adaptive consensus [17], [119], quantized consensus”
Minibatch vs Local SGD for Heterogeneous Distributed Learning (2020, background): “[16] Angelia Nedic, Asuman Ozdaglar, and Pablo A Parrilo.”
Multi-Agent Distributed Optimization via Inexact Consensus ADMM (2014, positive): “Unlike (P1) , in (P2) , each agent i owns a local control variable x i , and these variables are coupled together through the linear constraint.”
Primal-Dual Algorithm for Distributed Reinforcement Learning: Distributed GTD (2018, background): “We first establish the convergence of Algorithm 1 to the stationary points of (12) under the standard diminishing step size rule [24]”
Distributed Control Strategies for Microgrids: An Overview (2020, background): “The application of other types of consensus protocols has also been discussed in the literature [85]–[88], such as second-order consensus [89]–[91], adaptive consensus [92]–[94], consensus with constraints [95], [96], event-triggered consensus [97], [98], finite-time consensus [99], [100], delay-rob”
Secure and Privacy-Preserving Consensus (2017, background): “Since P(k) (k ≥ 1) satisfies the Assumptions 2–5 in [33], following its Proposition 1, we have”
Distributed Continuous-Time Optimization: Nonuniform Gradient Gains, Finite-Time Convergence, and Convex Constraint Set (2017, background): “Besides this aspect, most of the existing works on the distributed optimization problem (e.g., [1]–[16]), studied only the asymptotical stability of the algorithm and rare results are concerned about the ﬁnite-time convergence of the algorithms.”
Distributed dual averaging method for multi-agent optimization with quantized communication (2012, methodology): “, the states of the agents lie in some convex constraint set, the authors in [6] propose a distributed projected subgradient method, which can be viewed as an extension of the method considered in [1].”
Gossip Algorithms for Distributed Signal Processing (2010, background): “ yield some achievable bound. Numerous papers have studied the effects of intermittent or lossy links in the context of gossip algorithms (i.i.d. and correlated models, symmetric and asymmetric) [55]–[64]. In these models, lossy links correspond to masking some edges from the topology at each iterat”
Fast Convergence Rates of Distributed Subgradient Methods With Adaptive Quantization (2018, methodology): “Note that, DSG with time-varying quantization [16] achieves the same rate of convergence as the one with no quantization [37], but requires that the nodes eventually exchange an infinite number of bits.”