Distributed multi-agent optimization with state-dependent communication
We study distributed algorithms for solving global optimization problems in which the objective function is the sum of local objective functions of agents and the constraint set is given by the intersection of local constraint sets of agents. We assume that each agent knows only his own local object...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73504 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0003-4047-019X |
| _version_ | 1826213099502305280 |
|---|---|
| author | Lobel, Ilan Ozdaglar, Asuman E. Feijer Rovira, Diego Francisco |
| 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 Lobel, Ilan Ozdaglar, Asuman E. Feijer Rovira, Diego Francisco |
| author_sort | Lobel, Ilan |
| collection | MIT |
| description | We study distributed algorithms for solving global optimization problems in which the objective function is the sum of local objective functions of agents and the constraint set is given by the intersection of local constraint sets of agents. We assume that each agent knows only his own local objective function and constraint set, and exchanges information with the other agents over a randomly varying network topology to update his information state. We assume a state-dependent communication model over this topology: communication is Markovian with respect to the states of the agents and the probability with which the links are available depends on the states of the agents. We study a projected multi-agent subgradient algorithm under state-dependent communication. The state-dependence of the communication introduces significant challenges and couples the study of information exchange with the analysis of subgradient steps and projection errors. We first show that the multi-agent subgradient algorithm when used with a constant stepsize may result in the agent estimates to diverge with probability one. Under some assumptions on the stepsize sequence, we provide convergence rate bounds on a “disagreement metric” between the agent estimates. Our bounds are time-nonhomogeneous in the sense that they depend on the initial starting time. Despite this, we show that agent estimates reach an almost sure consensus and converge to the same optimal solution of the global optimization problem with probability one under different assumptions on the local constraint sets and the stepsize sequence. |
| first_indexed | 2024-09-23T15:43:19Z |
| format | Article |
| id | mit-1721.1/73504 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:43:19Z |
| publishDate | 2012 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/735042022-09-29T15:43:58Z Distributed multi-agent optimization with state-dependent communication Lobel, Ilan Ozdaglar, Asuman E. Feijer Rovira, Diego Francisco Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Ozdaglar, Asuman E. Feijer Rovira, Diego Francisco We study distributed algorithms for solving global optimization problems in which the objective function is the sum of local objective functions of agents and the constraint set is given by the intersection of local constraint sets of agents. We assume that each agent knows only his own local objective function and constraint set, and exchanges information with the other agents over a randomly varying network topology to update his information state. We assume a state-dependent communication model over this topology: communication is Markovian with respect to the states of the agents and the probability with which the links are available depends on the states of the agents. We study a projected multi-agent subgradient algorithm under state-dependent communication. The state-dependence of the communication introduces significant challenges and couples the study of information exchange with the analysis of subgradient steps and projection errors. We first show that the multi-agent subgradient algorithm when used with a constant stepsize may result in the agent estimates to diverge with probability one. Under some assumptions on the stepsize sequence, we provide convergence rate bounds on a “disagreement metric” between the agent estimates. Our bounds are time-nonhomogeneous in the sense that they depend on the initial starting time. Despite this, we show that agent estimates reach an almost sure consensus and converge to the same optimal solution of the global optimization problem with probability one under different assumptions on the local constraint sets and the stepsize sequence. National Science Foundation (U.S.) (Career Grant DMI-0545910) United States. Defense Advanced Research Projects Agency. Information Theory for Mobile Ad-Hoc Networks Program United States. Air Force Office of Scientific Research. Multidisciplinary University Research Initiative 2012-10-01T15:39:30Z 2012-10-01T15:39:30Z 2011-06 2010-04 Article http://purl.org/eprint/type/JournalArticle 0025-5610 1436-4646 http://hdl.handle.net/1721.1/73504 Lobel, Ilan, Asuman Ozdaglar, and Diego Feijer. “Distributed Multi-agent Optimization with State-dependent Communication.” Mathematical Programming 129.2 (2011): 255–284. https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0003-4047-019X en_US http://dx.doi.org/10.1007/s10107-011-0467-x Mathematical Programming Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer-Verlag arXiv |
| spellingShingle | Lobel, Ilan Ozdaglar, Asuman E. Feijer Rovira, Diego Francisco Distributed multi-agent optimization with state-dependent communication |
| title | Distributed multi-agent optimization with state-dependent communication |
| title_full | Distributed multi-agent optimization with state-dependent communication |
| title_fullStr | Distributed multi-agent optimization with state-dependent communication |
| title_full_unstemmed | Distributed multi-agent optimization with state-dependent communication |
| title_short | Distributed multi-agent optimization with state-dependent communication |
| title_sort | distributed multi agent optimization with state dependent communication |
| url | http://hdl.handle.net/1721.1/73504 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0003-4047-019X |
| work_keys_str_mv | AT lobelilan distributedmultiagentoptimizationwithstatedependentcommunication AT ozdaglarasumane distributedmultiagentoptimizationwithstatedependentcommunication AT feijerroviradiegofrancisco distributedmultiagentoptimizationwithstatedependentcommunication |