Academic
Publications
Constrained Consensus and Optimization in Multi-Agent Networks

Constrained Consensus and Optimization in Multi-Agent Networks,10.1109/TAC.2010.2041686,IEEE Transactions on Automatic Control,Angelia Nedic ´,Asuman

Constrained Consensus and Optimization in Multi-Agent Networks   (Citations: 35)
BibTex | RIS | RefWorks Download
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.
Journal: IEEE Transactions on Automatic Control - IEEE TRANS AUTOMAT CONTR , vol. 55, no. 4, pp. 922-938, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...The following lemma on the infinite sum of products of the components of two sequences will also be used in establishing our convergence results (see Lemma 7 in [15] for the proof)...

    Ilan Lobelet al. Distributed Subgradient Methods for Convex Optimization Over Random Ne...

    • ...Recently, Nedic et al. [9] studied constrained consensus problems and develop a projected-consensus algorithm where the nodes combine local estimates along with a projection onto their constraintset.Inthispriorwork,theemphasisisonformulatingand solving a single global optimization problem with distributed data through gossip-based approaches...

    Naveen Ramakrishnanet al. Gossip-Based Algorithm for Joint Signature Estimation and Node Calibra...

    • ...In [9], the authors proposed a constrained consensus method for convex optimization problems, however it is restricted to the consistent cases and can not be used for source localization which is usually inconsistent...
    • ...If the source localization problem fall in the consistent case, in the literature, there already has a diffusion based method can be used which is proposed by A. Nedi´ c and A. Ozdaglarin [9]...
    • ...Theorem 3: [9](Consensus) Let the intersection set D =...
    • ...Fig. 6 presents the convergence result by using protocol in [9] and the proposed protocol, where each curve denotes the convergence result of one sensor and distance (y-coordinate) denotes Euclidean distance between the estimated and true source location, i.e., � ˆ θ i − θ�, ∀i. From the figure, we can see...
    • ...However, in most of the cases, the protocol (10) in [9] will diverge or oscillate at some point...
    • ...Distance (a) Protocol of [9] 0 20 40 60 80 100 0 0.5 1 1.5 2 2.5...

    Wei Menget al. Diffusion based projection method for distributed source localization ...

    • ...Relevant extensions of the consensus problem were done by Ren and Beard [16], by Moreau in [11] or, more recently, by Nedic and Ozdaglar in [14], [13]...

    Ion Mateiet al. The geometry of a probabilistic consensus of opinion algorithm

    • ...While several interior point algorithms were proposed to solve quadratic programs and other convex programs [3], [4], [5], [6], to the best of our knowledge a theory for distributed linear programming is missing...

    Mathias Burgeret al. A distributed simplex algorithm and the multi-agent assignment problem

Sort by: