Alternating Direction Method of Multipliers for Linear Programming

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 show that the alternating direction method of multipliers (ADMM), which was proposed long time ago while recently...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the Operations Research Society of China (Internet) 2016-12, Vol.4 (4), p.425-436
Main Authors: He, Bing-Sheng, Yuan, Xiao-Ming
Format: Article
Language:English
Subjects:
Iterative methods
Lagrange multiplier
Linear programming
Multipliers
Operations research
Parallel processing
Variables
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 show that 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 new ADMM approach to linear programming, which may inspire deeper research for more complicated scenarios with more sophisticated results.
ISSN:2194-668X
2194-6698
DOI:10.1007/s40305-016-0136-0