An Interior-Point Method for Large Scale Network Utility Maximization

Proceedings of the Allerton Conference on Communication, Control, and Computing, September 2007.

• ls_num.pdf

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.