Constrained Consensus and Optimization in Multi-Agent Networks
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 optimiz...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2011
|
| Online Access: | http://hdl.handle.net/1721.1/62224 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0003-1132-8477 |
| _version_ | 1811091263267536896 |
|---|---|
| author | Nedic, Angelia Ozdaglar, Asuman E. Parrilo, Pablo A. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Nedic, Angelia Ozdaglar, Asuman E. Parrilo, Pablo A. |
| author_sort | Nedic, Angelia |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T14:59:42Z |
| format | Article |
| id | mit-1721.1/62224 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:59:42Z |
| publishDate | 2011 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/622242022-10-01T23:49:08Z Constrained Consensus and Optimization in Multi-Agent Networks Nedic, Angelia Ozdaglar, Asuman E. Parrilo, Pablo A. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Parrilo, Pablo A. Ozdaglar, Asuman E. Parrilo, Pablo A. 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. National Science Foundation (U.S.) (CAREER grant CMMI 07-42538) National Science Foundation (U.S.) (CAREER grant DMI-0545910, under grant ECCS-0621922) United States. Defense Advanced Research Projects Agency (DARPA). ITMANET program 2011-04-19T14:55:54Z 2011-04-19T14:55:54Z 2010-04 2008-03 Article http://purl.org/eprint/type/JournalArticle 0018-9286 INSPEC Accession Number: 11208161 http://hdl.handle.net/1721.1/62224 Nedic, A., A. Ozdaglar, and P.A. Parrilo. “Constrained Consensus and Optimization in Multi-Agent Networks.” Automatic Control, IEEE Transactions on 55.4 (2010): 922-938. © Copyright 2010 IEEE https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0003-1132-8477 en_US http://dx.doi.org/10.1109/TAC.2010.2041686 IEEE Transactions on Automatic Control Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Nedic, Angelia Ozdaglar, Asuman E. Parrilo, Pablo A. Constrained Consensus and Optimization in Multi-Agent Networks |
| title | Constrained Consensus and Optimization in Multi-Agent Networks |
| title_full | Constrained Consensus and Optimization in Multi-Agent Networks |
| title_fullStr | Constrained Consensus and Optimization in Multi-Agent Networks |
| title_full_unstemmed | Constrained Consensus and Optimization in Multi-Agent Networks |
| title_short | Constrained Consensus and Optimization in Multi-Agent Networks |
| title_sort | constrained consensus and optimization in multi agent networks |
| url | http://hdl.handle.net/1721.1/62224 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0003-1132-8477 |
| work_keys_str_mv | AT nedicangelia constrainedconsensusandoptimizationinmultiagentnetworks AT ozdaglarasumane constrainedconsensusandoptimizationinmultiagentnetworks AT parrilopabloa constrainedconsensusandoptimizationinmultiagentnetworks |