A primal-dual algorithm for monotropic programming and its application to network optimization

This paper presents a new primal-dual algorithm for solving a class of mono tropic programming problems. This class involves many problems arising in a number of important applications in telecommunications networks, transport ation and water distribution. The proposed algorithm is inspired by Kallio and Ruszczynski approach for linear programming [M. Kallio and A. Ruszczyns ki, WP-94-15, IIASA, 1994]. The problem is replaced by a game using two dif ferent augmented Lagrangian functions defined for the primal and the dual p roblems. It is then possible to develop a block-wise Gauss-Seidel method to reach an equilibrium of the game with alternating steps made in each compo nent of the primal and dual variables. Finally, we show how this algorithm may be applied to some important problems in Network Optimization such as t he minimum quadratic cost single flow problems and convex multicommodity fl ow problems.