An Interior-Point Method for Large Scale Network Utility Maximization

Argyrios Zymnis(azymnisstanford.edu)
Nikolaos Trichakis(nitricmit.edu)
Stephen Boyd(boydstanford.edu)
Daniel O' Neill(dconeillstanford.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