A distributed newton method for network utility maximization-i: Algorithm

Ermin Wei, Asuman Ozdaglar, Ali Jadbabaie

Research output: Contribution to journalArticlepeer-review

114 Scopus citations

Abstract

Most existing works use dual decomposition and first-order methods to solve Network Utility Maximization (NUM) problems in a distributed manner, which suffer from slow rate of convergence properties. This paper develops an alternative distributed Newton-type fast converging algorithm for solving NUM problems. 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. We propose a stepsize rule and provide a distributed procedure to compute it in finitely many iterations. The key feature of our direction and stepsize computation schemes is that both are implemented using the same distributed information exchange mechanism employed by first order methods. We describe the details of the inexact algorithm here and in part II of this paper , we show that under some assumptions, 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 in terms of primal iterations to an explicitly characterized error neighborhood. Simulation results demonstrate significant convergence rate improvement of our algorithm relative to the existing first-order methods based on dual decomposition.

Original languageEnglish (US)
Article number6482177
Pages (from-to)2162-2175
Number of pages14
JournalIEEE Transactions on Automatic Control
Volume58
Issue number9
DOIs
StatePublished - Aug 30 2013

Keywords

  • Distributed optimization
  • Network Utility Maximization (NUM)
  • distributed Newton method
  • 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-i: Algorithm'. Together they form a unique fingerprint.

Cite this