Relaxation methods for monotropic programs

The authors propose a dual descent method for the problem of minimizing a convex, possibly nondifferentiable, separable cost subject to linear constraints. The method has properties reminiscent of the Gauss-Seidel method in numerical analysis and uses the •-complementary slackness mechanism introduced in Bertsekas, Hosein and Tseng to ensure finite convergence to near optimality. As special cases the authors obtain the methods in Bertsekas, Hosein and Tseng for network flow programs and the methods in Tseng and Bertsekas for linear programs.