Abstract:

Linear programming is the core problem of various operational research
problems. The dominant approaches for linear programming are simplex and interior
point methods. In this paper, we showthat the alternating direction method of multipliers
(ADMM), which was proposed long time ago while recently found more and more
applications in a broad spectrum of areas, can also be easily used to solve the canonical
linear programming model. The resulting per-iteration complexity is O(mn) where m
is the constraint number and n the variable dimension. At each iteration, there are m
subproblems that are eligible for parallel computation; each requiring only O(n) flops.
There is no inner iteration as well.We thus introduce the newADMMapproach to linear
programming, which may inspire deeper research for more complicated scenarios
with more sophisticated results.

Key words: Continuous optimization ·, Linear programming ·, Alternating direction
method of multipliers