On Dual Convergence of the Distributed Newton Method for Network Utility Maximization
The existing distributed algorithms for Network Utility Maximization (NUM) problems mostly rely on dual decomposition and first-order (gradient or subgradient) methods, which suffer from slow rate of convergence. Recent works [17] and [18] proposed an alternative distributed Newton-type second-order...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72677 https://orcid.org/0000-0002-1827-1285 |
| _version_ | 1811085121423409152 |
|---|---|
| author | Wei, Ermin Zargham, Michael Ozdaglar, Asuman E. Jadbabaie, Ali |
| 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 Zargham, Michael Ozdaglar, Asuman E. Jadbabaie, Ali |
| author_sort | Wei, Ermin |
| collection | MIT |
| description | The existing distributed algorithms for Network Utility Maximization (NUM) problems mostly rely on dual decomposition and first-order (gradient or subgradient) methods, which suffer from slow rate of convergence. Recent works [17] and [18] proposed an alternative distributed Newton-type second-order algorithm for solving NUM problems with self-concordant utility functions. This algorithm is implemented in the primal space and involves for each primal iteration computing the dual variables using a finitely terminated iterative scheme obtained through novel matrix splitting techniques. These works presented a convergence rate analysis for the primal iterations and showed that if the error level in the Newton direction (resulting from finite termination of dual iterations) is below a certain threshold, then the algorithm achieves local quadratic convergence rate to an error neighborhood of the optimal solution. This paper builds on these works and presents a convergence rate analysis for the dual iterations that enables us to explicitly compute at each primal iteration the number of dual steps that can satisfy the error level. This yields for the first time a fully distributed second order method for NUM problems with local quadratic convergence guarantee. Simulation results demonstrate significant convergence rate improvement of our algorithm, even when only one dual update is implemented per primal iteration, relative to the existing first-order methods based on dual decomposition. |
| first_indexed | 2024-09-23T13:03:14Z |
| format | Article |
| id | mit-1721.1/72677 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:03:14Z |
| publishDate | 2012 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/726772022-09-28T11:45:10Z On Dual Convergence of the Distributed Newton Method for Network Utility Maximization Wei, Ermin Zargham, Michael Ozdaglar, Asuman E. Jadbabaie, Ali Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Ozdaglar, Asuman E. Wei, Ermin Ozdaglar, Asuman E. The existing distributed algorithms for Network Utility Maximization (NUM) problems mostly rely on dual decomposition and first-order (gradient or subgradient) methods, which suffer from slow rate of convergence. Recent works [17] and [18] proposed an alternative distributed Newton-type second-order algorithm for solving NUM problems with self-concordant utility functions. This algorithm is implemented in the primal space and involves for each primal iteration computing the dual variables using a finitely terminated iterative scheme obtained through novel matrix splitting techniques. These works presented a convergence rate analysis for the primal iterations and showed that if the error level in the Newton direction (resulting from finite termination of dual iterations) is below a certain threshold, then the algorithm achieves local quadratic convergence rate to an error neighborhood of the optimal solution. This paper builds on these works and presents a convergence rate analysis for the dual iterations that enables us to explicitly compute at each primal iteration the number of dual steps that can satisfy the error level. This yields for the first time a fully distributed second order method for NUM problems with local quadratic convergence guarantee. Simulation results demonstrate significant convergence rate improvement of our algorithm, even when only one dual update is implemented per primal iteration, relative to the existing first-order methods based on dual decomposition. National Science Foundation (U.S.). (Career) (Grant number DMI-0545910) United States. Air Force Office of Scientific Research. Multidisciplinary University Research Initiative (R6756-G2) United States. Office of Naval Research. Multidisciplinary University Research Initiative (Grant N0001408107474) United States. Army Research Office. Multidisciplinary University Research Initiative. Scalable United States. Air Force Office of Scientific Research. Complex Networks Program 2012-09-13T13:10:20Z 2012-09-13T13:10:20Z 2011-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-61284-799-3 978-1-61284-800-6 0743-1546 http://hdl.handle.net/1721.1/72677 Wei, Ermin et al. “On Dual Convergence of the Distributed Newton Method for Network Utility Maximization.” 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC), 2011. 6612–6617. https://orcid.org/0000-0002-1827-1285 en_US http://dx.doi.org/10.1109/CDC.2011.6161134 Proceedings on the 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC), 2011 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 (IEEE) MIT web domain |
| spellingShingle | Wei, Ermin Zargham, Michael Ozdaglar, Asuman E. Jadbabaie, Ali On Dual Convergence of the Distributed Newton Method for Network Utility Maximization |
| title | On Dual Convergence of the Distributed Newton Method for Network Utility Maximization |
| title_full | On Dual Convergence of the Distributed Newton Method for Network Utility Maximization |
| title_fullStr | On Dual Convergence of the Distributed Newton Method for Network Utility Maximization |
| title_full_unstemmed | On Dual Convergence of the Distributed Newton Method for Network Utility Maximization |
| title_short | On Dual Convergence of the Distributed Newton Method for Network Utility Maximization |
| title_sort | on dual convergence of the distributed newton method for network utility maximization |
| url | http://hdl.handle.net/1721.1/72677 https://orcid.org/0000-0002-1827-1285 |
| work_keys_str_mv | AT weiermin ondualconvergenceofthedistributednewtonmethodfornetworkutilitymaximization AT zarghammichael ondualconvergenceofthedistributednewtonmethodfornetworkutilitymaximization AT ozdaglarasumane ondualconvergenceofthedistributednewtonmethodfornetworkutilitymaximization AT jadbabaieali ondualconvergenceofthedistributednewtonmethodfornetworkutilitymaximization |