Constrained Consensus and Optimization in Multi-Agent Networks

Constrained Consensus and Optimization in Multi-Agent Networks

February 15, 2013 | Angelia Nedić, Asuman Ozdaglar, and Pablo A. Parrilo
The paper presents distributed algorithms for multiple agents to align their estimates with a specific value over a time-varying connectivity network. The value can represent a consensus among agents or an optimal solution of an optimization problem, where the global objective function is a combination of local agent objective functions. The focus is on constrained problems where each agent's estimate is restricted to a different constraint set. The authors first consider a constrained consensus problem and propose a distributed "projected consensus algorithm" that combines local averaging with projection onto individual constraint sets. This algorithm is shown to converge to the intersection of the constraint sets, with a convergence rate analysis provided. Next, they study a constrained optimization problem and present a "projected subgradient algorithm" that involves local averaging, subgradient steps, and projection onto constraint sets. The algorithm is shown to converge to the optimal solution under appropriate stepsize rules, regardless of whether the constraint sets are the same or different. The paper also includes a review of related literature and introduces notation and terminology, establishing basic results on projection and convex sets. The analysis of the algorithms relies on the properties of projection and the assumptions on the multi-agent model, including connectivity and information exchange rules. The convergence behavior of the agent estimates is analyzed, and the paper concludes with a discussion of future directions.The paper presents distributed algorithms for multiple agents to align their estimates with a specific value over a time-varying connectivity network. The value can represent a consensus among agents or an optimal solution of an optimization problem, where the global objective function is a combination of local agent objective functions. The focus is on constrained problems where each agent's estimate is restricted to a different constraint set. The authors first consider a constrained consensus problem and propose a distributed "projected consensus algorithm" that combines local averaging with projection onto individual constraint sets. This algorithm is shown to converge to the intersection of the constraint sets, with a convergence rate analysis provided. Next, they study a constrained optimization problem and present a "projected subgradient algorithm" that involves local averaging, subgradient steps, and projection onto constraint sets. The algorithm is shown to converge to the optimal solution under appropriate stepsize rules, regardless of whether the constraint sets are the same or different. The paper also includes a review of related literature and introduces notation and terminology, establishing basic results on projection and convex sets. The analysis of the algorithms relies on the properties of projection and the assumptions on the multi-agent model, including connectivity and information exchange rules. The convergence behavior of the agent estimates is analyzed, and the paper concludes with a discussion of future directions.
Reach us at info@study.space
[slides and audio] Constrained Consensus and Optimization in Multi-Agent Networks