Optimization Online


An Interior-Point Method for Large Scale Network Utility Maximization

Argyrios Zymnis(azymnis***at***stanford.edu)
Nikolaos Trichakis(nitric***at***mit.edu)
Stephen Boyd(boyd***at***stanford.edu)
Daniel O' Neill(dconeill***at***stanford.edu)

Abstract: We describe a specialized truncated-Newton primal-dual interior-point method that solves large scale network utility maximization problems, with concave utility functions, efficiently and reliably. Our method is not decentralized, but easily scales to problems with a million flows and links. We compare our method to a standard decentralized algorithm based on dual decomposition, and show by example that our method converges significantly faster for problems with congested networks or long routes. We describe an extension to problems that take into account delay or latency in the objective.

Keywords: network utility maximization, interior point methods, conjugate gradients

Category 1: Network Optimization

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Stanford University Electrical Engineering Department, Stanford, CA, USA, September 2007

Download: [PDF]

Entry Submitted: 09/30/2007
Entry Accepted: 10/01/2007
Entry Last Modified: 09/30/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society