An Alternating Direction Method for Linear Programming

Abstract

This paper presents a new, simple, massively parallel algorithm for linear programming, called the alternating step method. The algorithm is unusual in that it does not maintain primal feasibility, dual feasibility, or complementary slackness; rather, all these conditions are gradually met as the method proceeds. We derive the algorithm from an extension of the alternating direction method of multipliers for convex programming, giving a new algorithm for monotropic programming in the course of the development. Concentrating on the linear programming case, we give a proof that, under a simple condition on the algorithm parameters, the method converges at a globally linear rate. Finally, we give some preliminary computational results.