An O(1/k) gradient method for network resource allocation problems

Amir Beck, Angelia Nedic, Asuman Ozdaglar, Marc Teboulle

Research output: Contribution to journalArticlepeer-review

145 Scopus citations


We present a fast distributed gradient method for a convex optimization problem with linear inequalities, with a particular focus on the network utility maximization (NUM) problem. Most existing works in the literature use (sub)gradient methods for solving the dual of this problem which can be implemented in a distributed manner. However, these (sub)gradient methods suffer from an O(1/√k) rate of convergence (where k is the number of iterations). In this paper, we assume that the utility functions are strongly concave, an assumption satisfied by most standard utility functions considered in the literature. We develop a completely distributed fast gradient method for solving the dual of the NUM problem. We show that the generated primal sequences converge to the unique optimal solution of the NUM problem at rate O(1/k).

Original languageEnglish (US)
Article number6756941
Pages (from-to)64-73
Number of pages10
JournalIEEE Transactions on Control of Network Systems
Issue number1
StatePublished - Mar 1 2014
Externally publishedYes


  • Gradient methods
  • convex functions
  • network utility maximization

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Signal Processing
  • Computer Networks and Communications
  • Control and Optimization


Dive into the research topics of 'An O(1/k) gradient method for network resource allocation problems'. Together they form a unique fingerprint.

Cite this