On the O(1/k) convergence of asynchronous distributed alternating Direction Method of Multipliers
We consider a network of agents that are cooperatively solving a global optimization problem, where the objective function is the sum of privately known local objective functions of the agents and the decision variables are coupled via linear constraints. Recent literature focused on special cases o...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/90493 https://orcid.org/0000-0002-1827-1285 |
| _version_ | 1811069650690113536 |
|---|---|
| author | Wei, Ermin Ozdaglar, Asuman E. |
| 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 Wei, Ermin Ozdaglar, Asuman E. |
| author_sort | Wei, Ermin |
| collection | MIT |
| description | We consider a network of agents that are cooperatively solving a global optimization problem, where the objective function is the sum of privately known local objective functions of the agents and the decision variables are coupled via linear constraints. Recent literature focused on special cases of this formulation and studied their distributed solution through either subgradient based methods with O(1/√k) rate of convergence (where k is the iteration number) or Alternating Direction Method of Multipliers (ADMM) based methods, which require a synchronous implementation and a globally known order on the agents. In this paper, we present a novel asynchronous ADMM based distributed method for the general formulation and show that it converges at the rate O (1=k). |
| first_indexed | 2024-09-23T08:13:45Z |
| format | Article |
| id | mit-1721.1/90493 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:13:45Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/904932022-09-23T11:44:49Z On the O(1/k) convergence of asynchronous distributed alternating Direction Method of Multipliers Wei, Ermin Ozdaglar, Asuman E. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Wei, Ermin Ozdaglar, Asuman E. We consider a network of agents that are cooperatively solving a global optimization problem, where the objective function is the sum of privately known local objective functions of the agents and the decision variables are coupled via linear constraints. Recent literature focused on special cases of this formulation and studied their distributed solution through either subgradient based methods with O(1/√k) rate of convergence (where k is the iteration number) or Alternating Direction Method of Multipliers (ADMM) based methods, which require a synchronous implementation and a globally known order on the agents. In this paper, we present a novel asynchronous ADMM based distributed method for the general formulation and show that it converges at the rate O (1=k). National Science Foundation (U.S.) (Career Grant DMI-0545910) United States. Air Force Office of Scientific Research. Multidisciplinary University Research Initiative (FA9550-09-1-0538) United States. Office of Naval Research (Basic Research Challenge N000141210997) 2014-09-30T18:48:19Z 2014-09-30T18:48:19Z 2013-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-4799-0248-4 http://hdl.handle.net/1721.1/90493 Wei, Ermin, and Asuman Ozdaglar. “On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers.” 2013 IEEE Global Conference on Signal and Information Processing (December 2013). https://orcid.org/0000-0002-1827-1285 en_US http://dx.doi.org/10.1109/GlobalSIP.2013.6736937 Proceedings of the 2013 IEEE Global Conference on Signal and Information Processing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Wei, Ermin Ozdaglar, Asuman E. On the O(1/k) convergence of asynchronous distributed alternating Direction Method of Multipliers |
| title | On the O(1/k) convergence of asynchronous distributed alternating Direction Method of Multipliers |
| title_full | On the O(1/k) convergence of asynchronous distributed alternating Direction Method of Multipliers |
| title_fullStr | On the O(1/k) convergence of asynchronous distributed alternating Direction Method of Multipliers |
| title_full_unstemmed | On the O(1/k) convergence of asynchronous distributed alternating Direction Method of Multipliers |
| title_short | On the O(1/k) convergence of asynchronous distributed alternating Direction Method of Multipliers |
| title_sort | on the o 1 k convergence of asynchronous distributed alternating direction method of multipliers |
| url | http://hdl.handle.net/1721.1/90493 https://orcid.org/0000-0002-1827-1285 |
| work_keys_str_mv | AT weiermin ontheo1kconvergenceofasynchronousdistributedalternatingdirectionmethodofmultipliers AT ozdaglarasumane ontheo1kconvergenceofasynchronousdistributedalternatingdirectionmethodofmultipliers |