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
This paper presents distributed algorithms for multiple agents to align their estimates with a common value over a time-varying network. The framework applies to both consensus problems and constrained optimization, where each agent's estimate is restricted to a local constraint set. The key algorithms are the "projected consensus algorithm" for consensus and the "projected subgradient algorithm" for optimization. The projected consensus algorithm combines local averaging with projection on individual constraint sets, effectively implementing an alternating projection method with time-varying weights. It is shown to converge to a common estimate that lies in the intersection of all constraint sets. The projected subgradient algorithm involves local averaging, subgradient steps, and projection on individual constraint sets. It converges to the same optimal solution when weights are constant or time-varying but all agents share the same constraint set. The analysis of convergence relies on decomposing the dynamics into linear and nonlinear parts. The linear part involves time-varying averaging, while the nonlinear part involves projection errors. The projection errors diminish over time, leading to "almost linear" dynamics. The convergence of the projected consensus algorithm is established using properties of projection and transition matrices, which converge to a uniform steady state. For the projected subgradient algorithm, convergence is analyzed under the assumption that the constraint sets are the same or have uniform weights. The projection errors are shown to converge to zero, reducing the problem to an unconstrained one. The analysis also involves an error bound that relates the distance of the averaged vector to the intersection set with the distances to individual constraint sets. The paper also discusses related work on distributed computation and consensus algorithms, highlighting the differences between the current approach and previous methods. The key contributions are the development of distributed algorithms for constrained consensus and optimization, and the analysis of their convergence properties under varying network conditions and constraint sets.This paper presents distributed algorithms for multiple agents to align their estimates with a common value over a time-varying network. The framework applies to both consensus problems and constrained optimization, where each agent's estimate is restricted to a local constraint set. The key algorithms are the "projected consensus algorithm" for consensus and the "projected subgradient algorithm" for optimization. The projected consensus algorithm combines local averaging with projection on individual constraint sets, effectively implementing an alternating projection method with time-varying weights. It is shown to converge to a common estimate that lies in the intersection of all constraint sets. The projected subgradient algorithm involves local averaging, subgradient steps, and projection on individual constraint sets. It converges to the same optimal solution when weights are constant or time-varying but all agents share the same constraint set. The analysis of convergence relies on decomposing the dynamics into linear and nonlinear parts. The linear part involves time-varying averaging, while the nonlinear part involves projection errors. The projection errors diminish over time, leading to "almost linear" dynamics. The convergence of the projected consensus algorithm is established using properties of projection and transition matrices, which converge to a uniform steady state. For the projected subgradient algorithm, convergence is analyzed under the assumption that the constraint sets are the same or have uniform weights. The projection errors are shown to converge to zero, reducing the problem to an unconstrained one. The analysis also involves an error bound that relates the distance of the averaged vector to the intersection set with the distances to individual constraint sets. The paper also discusses related work on distributed computation and consensus algorithms, highlighting the differences between the current approach and previous methods. The key contributions are the development of distributed algorithms for constrained consensus and optimization, and the analysis of their convergence properties under varying network conditions and constraint sets.
Reach us at info@study.space
[slides] Constrained Consensus and Optimization in Multi-Agent Networks | StudySpace