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 monotropic programming problems. This class involves many problems arising in a number of important applications in telecommunications networks, transportation and water distribution. The proposed algorithm is inspired by Kallio and Ruszczynski approach for linear programming. The problem is replaced by a game using two different augmented Lagrangian functions defined for the primal and the dual problems. It is then possible to develop a block-wise Gauss-Siedel method to reach an equilibrium of the game with alternative steps made in each component of the primal and dual variables.