A Distributed Newton Method for Network Optimization
Most existing work uses dual decomposition and subgradient methods to solve network optimization problems in a distributed manner, which suffer from slow convergence rate properties. This paper proposes an alternative distributed approach based on a Newton-type method for solving minimum cost networ...
| 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/61969 https://orcid.org/0000-0002-1827-1285 |
| _version_ | 1811070799074820096 |
|---|---|
| author | Jadbabaie, Ali Ozdaglar, Asuman E. Zargham, Michael |
| 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 Jadbabaie, Ali Ozdaglar, Asuman E. Zargham, Michael |
| author_sort | Jadbabaie, Ali |
| collection | MIT |
| description | Most existing work uses dual decomposition and subgradient methods to solve network optimization problems in a distributed manner, which suffer from slow convergence rate properties. This paper proposes an alternative distributed approach based on a Newton-type method for solving minimum cost network optimization problems. The key component of the method is to represent the dual Newton direction as the solution of a discrete Poisson equation involving the graph Laplacian. This representation enables using an iterative consensus-based local averaging scheme (with an additional input term) to compute the Newton direction based only on local information. We show that even when the iterative schemes used for computing the Newton direction and the stepsize in our method are truncated, the resulting iterates converge superlinearly within an explicitly characterized error neighborhood. Simulation results illustrate the significant performance gains of this method relative to subgradient methods based on dual decomposition. |
| first_indexed | 2024-09-23T08:41:25Z |
| format | Article |
| id | mit-1721.1/61969 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:41:25Z |
| publishDate | 2011 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/619692022-09-23T13:53:28Z A Distributed Newton Method for Network Optimization Jadbabaie, Ali Ozdaglar, Asuman E. Zargham, Michael Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Ozdaglar, Asuman E. Ozdaglar, Asuman E. Most existing work uses dual decomposition and subgradient methods to solve network optimization problems in a distributed manner, which suffer from slow convergence rate properties. This paper proposes an alternative distributed approach based on a Newton-type method for solving minimum cost network optimization problems. The key component of the method is to represent the dual Newton direction as the solution of a discrete Poisson equation involving the graph Laplacian. This representation enables using an iterative consensus-based local averaging scheme (with an additional input term) to compute the Newton direction based only on local information. We show that even when the iterative schemes used for computing the Newton direction and the stepsize in our method are truncated, the resulting iterates converge superlinearly within an explicitly characterized error neighborhood. Simulation results illustrate the significant performance gains of this method relative to subgradient methods based on dual decomposition. National Science Foundation (U.S.) (Career grant DMI-0545910) United States. Defense Advanced Research Projects Agency. Information Theory for Mobile Ad-Hoc Networks Program (Flows project under Grant W911NF-07-10029) U.S. Army Research Laboratory (MAST Collaborative Technology Alliance) 2011-03-25T16:11:18Z 2011-03-25T16:11:18Z 2009-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-3871-6 0191-2216 INSPEC Accession Number: 11148971 http://hdl.handle.net/1721.1/61969 Jadbabaie, A., A. Ozdaglar, and M. Zargham. “A Distributed Newton Method For Network Optimization.” Decision and Control, 2009 Held Jointly With the 2009 28th Chinese Control Conference. CDC/CCC 2009. Proceedings Of the 48th IEEE Conference On. 2009. 2736-2741. https://orcid.org/0000-0002-1827-1285 en_US http://dx.doi.org/10.1109/CDC.2009.5400289 Proceedings of the 48th IEEE Conference on Decision and Control, 2009 held jointly with the 2009 28th Chinese Control Conference. CDC/CCC 2009 Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers MIT web domain |
| spellingShingle | Jadbabaie, Ali Ozdaglar, Asuman E. Zargham, Michael A Distributed Newton Method for Network Optimization |
| title | A Distributed Newton Method for Network Optimization |
| title_full | A Distributed Newton Method for Network Optimization |
| title_fullStr | A Distributed Newton Method for Network Optimization |
| title_full_unstemmed | A Distributed Newton Method for Network Optimization |
| title_short | A Distributed Newton Method for Network Optimization |
| title_sort | distributed newton method for network optimization |
| url | http://hdl.handle.net/1721.1/61969 https://orcid.org/0000-0002-1827-1285 |
| work_keys_str_mv | AT jadbabaieali adistributednewtonmethodfornetworkoptimization AT ozdaglarasumane adistributednewtonmethodfornetworkoptimization AT zarghammichael adistributednewtonmethodfornetworkoptimization AT jadbabaieali distributednewtonmethodfornetworkoptimization AT ozdaglarasumane distributednewtonmethodfornetworkoptimization AT zarghammichael distributednewtonmethodfornetworkoptimization |