An Alternating Direction Method for Linear Programming
Jonathan Eckstein, Dimitri P. Bertsekas, Decision Systems. · 1990
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.
Cited by 58 works.
Authors
References
- Parallel and Distributed Computation: Numerical Methods
- Constrained Optimization and Lagrange Multiplier Methods
- Monotone Operators and the Proximal Point Algorithm
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operators
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problèmes de Dirichlet non linéaires
- NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
- Numerical Analysis of Variational Inequalities.