Recently the alternating direction method of multipliers (ADMM) has been widely used for various applications arising in scientific computing areas. Most of these application models are, or can be easily reformulated as, linearly constrained convex minimization models with separable nonlinear objective functions. In this note we show that ADMM can also be easily used for the canonical linear programming model; and the resulting complexity is O(mn) where m is the constraint number and n is the variable dimension. Moreover, at each iteration there are m subproblems that are eligible for parallel computation; and each of them only requires O(n) flops. This ADMM application provides a new approach to linear programming, which is completely different from the major simplex and interior point approaches in the literature.
Article
View Alternating Direction Method of Multipliers for Linear Programming