On dual convergence of the distributed Newton method for Network Utility Maximization

Ermin Wei*, Michael Zargham, Asuman Ozdaglar, Ali Jadbabaie

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages6612-6617
Number of pages6
ISBN (Print)9781612848006
DOIs
StatePublished - 2011
Event2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011 - Orlando, FL, United States
Duration: Dec 12 2011Dec 15 2011

Publication series

NameProceedings of the IEEE Conference on Decision and Control
ISSN (Print)0743-1546
ISSN (Electronic)2576-2370

Other

Other2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011
Country/TerritoryUnited States
CityOrlando, FL
Period12/12/1112/15/11

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint

Dive into the research topics of 'On dual convergence of the distributed Newton method for Network Utility Maximization'. Together they form a unique fingerprint.

Cite this