A distributed newton method for network utility maximization - Part II: Convergence

Ermin Wei, Asuman Ozdaglar, Ali Jadbabaie

Research output: Contribution to journalArticle

33 Scopus citations

Abstract

The existing distributed algorithms for network utility maximization (NUM) problems are mostly constructed using dual decomposition and first-order (gradient or subgradient) methods, which suffer from a slow rate of convergence. Part I of this paper proposed an alternative distributed Newton-type algorithm for solving NUM problems with self-concordant utility functions. For each primal iteration, this algorithm features distributed exact stepsize calculation with finite termination and decentralized computation of the dual variables using a finitely truncated iterative scheme obtained through novel matrix splitting techniques. This paper analyzes the convergence properties of a broader class of algorithms with potentially different stepsize computation schemes. In particular, we allow for errors in the stepsize computation. We show that if the error levels in the Newton direction (resulting from finite termination of dual iterations) and stepsize calculation are below a certain threshold, then the algorithm achieves local quadratic convergence rate in primal iterations to an error neighborhood of the optimal solution, where the size of the neighborhood can be explicitly characterized by the parameters of the algorithm and the error levels.

Original languageEnglish (US)
Article number6482178
Pages (from-to)2176-2188
Number of pages13
JournalIEEE Transactions on Automatic Control
Volume58
Issue number9
DOIs
StatePublished - Aug 30 2013

Keywords

  • Distributed Newton method
  • distributed optimization
  • network utility maximization (NUM)
  • superlinear rate of convergence

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A distributed newton method for network utility maximization - Part II: Convergence'. Together they form a unique fingerprint.

  • Cite this