A distributed Newton method for Network Utility Maximization
Most existing work uses dual decomposition and subgradient methods to solve Network Utility Maximization (NUM) problems in a distributed manner, which suffer from slow rate of convergence properties. This work develops an alternative distributed Newton-type fast converging algorithm for solving netw...
| 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/62146 https://orcid.org/0000-0002-1827-1285 |
| _version_ | 1811083845979602944 |
|---|---|
| author | Wei, Ermin 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 Ozdaglar, Asuman E. Jadbabaie, Ali |
| author_sort | Wei, Ermin |
| collection | MIT |
| description | Most existing work uses dual decomposition and subgradient methods to solve Network Utility Maximization (NUM) problems in a distributed manner, which suffer from slow rate of convergence properties. This work develops an alternative distributed Newton-type fast converging algorithm for solving network utility maximization problems with self-concordant utility functions. By using novel matrix splitting techniques, both primal and dual updates for the Newton step can be computed using iterative schemes in a decentralized manner with limited scalar information exchange. Similarly, the stepsize can be obtained via an iterative consensus-based averaging scheme. We show that even when the Newton direction and the stepsize in our method are computed within some error (due to finite truncation of the iterative schemes), the resulting objective function value still converges superlinearly to an explicitly characterized error neighborhood. Simulation results demonstrate significant convergence rate improvement of our algorithm relative to the existing subgradient methods based on dual decomposition. |
| first_indexed | 2024-09-23T12:40:17Z |
| format | Article |
| id | mit-1721.1/62146 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:40:17Z |
| publishDate | 2011 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/621462022-10-01T10:24:11Z A distributed Newton method for Network Utility Maximization Wei, Ermin Ozdaglar, Asuman E. Jadbabaie, Ali Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Ozdaglar, Asuman E. Wei, Ermin Ozdaglar, Asuman E. Most existing work uses dual decomposition and subgradient methods to solve Network Utility Maximization (NUM) problems in a distributed manner, which suffer from slow rate of convergence properties. This work develops an alternative distributed Newton-type fast converging algorithm for solving network utility maximization problems with self-concordant utility functions. By using novel matrix splitting techniques, both primal and dual updates for the Newton step can be computed using iterative schemes in a decentralized manner with limited scalar information exchange. Similarly, the stepsize can be obtained via an iterative consensus-based averaging scheme. We show that even when the Newton direction and the stepsize in our method are computed within some error (due to finite truncation of the iterative schemes), the resulting objective function value still converges superlinearly to an explicitly characterized error neighborhood. Simulation results demonstrate significant convergence rate improvement of our algorithm relative to the existing subgradient methods based on dual decomposition. National Science Foundation (U.S.) (CAREER grant DMI-0545910) United States. Defense Advanced Research Projects Agency (DARPA). ITMANET program United States. Office of Naval Research (MURI N000140810747) United States. Air Force Office of Scientific Research (Complex Networks Program) 2011-04-06T15:43:52Z 2011-04-06T15:43:52Z 2010-12 2010-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-7745-6 0743-1546 http://hdl.handle.net/1721.1/62146 Wei, E., A. Ozdaglar, and A. Jadbabaie. “A distributed Newton method for Network Utility Maximization.” Decision and Control (CDC), 2010 49th IEEE Conference on. 2010. 1816-1821. © Copyright 2010 IEEE https://orcid.org/0000-0002-1827-1285 en_US http://dx.doi.org/10.1109/CDC.2010.5718026 Proceedings of the 2010 49th IEEE Conference on Decision and Control (CDC) 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 | Wei, Ermin Ozdaglar, Asuman E. Jadbabaie, Ali A distributed Newton method for Network Utility Maximization |
| title | A distributed Newton method for Network Utility Maximization |
| title_full | A distributed Newton method for Network Utility Maximization |
| title_fullStr | A distributed Newton method for Network Utility Maximization |
| title_full_unstemmed | A distributed Newton method for Network Utility Maximization |
| title_short | A distributed Newton method for Network Utility Maximization |
| title_sort | distributed newton method for network utility maximization |
| url | http://hdl.handle.net/1721.1/62146 https://orcid.org/0000-0002-1827-1285 |
| work_keys_str_mv | AT weiermin adistributednewtonmethodfornetworkutilitymaximization AT ozdaglarasumane adistributednewtonmethodfornetworkutilitymaximization AT jadbabaieali adistributednewtonmethodfornetworkutilitymaximization AT weiermin distributednewtonmethodfornetworkutilitymaximization AT ozdaglarasumane distributednewtonmethodfornetworkutilitymaximization AT jadbabaieali distributednewtonmethodfornetworkutilitymaximization |