An Interior-Point Method for Large Scale Network Utility Maximization

The authors 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. Their method is not decentralized, but easily scales to problems with 106 flows and links. They compare their method to a standard decentralized algorithm based on dual decomposition, and show by example that their method converges significantly faster for problems with congested networks or long routes. They describe an extension to problems that take into account delay or latency in the objective.