Alternating Direction Method of Multipliers for Linear Programming

Bing Sheng He, Xiao Ming Yuan*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

6 Citations (Scopus)

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 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.

Original languageEnglish
Pages (from-to)425-436
Number of pages12
JournalJournal of the Operations Research Society of China
Volume4
Issue number4
DOIs
Publication statusPublished - 1 Dec 2016

Scopus Subject Areas

  • Management Science and Operations Research

User-Defined Keywords

  • Alternating direction method of multipliers
  • Continuous optimization
  • Linear programming

Fingerprint

Dive into the research topics of 'Alternating Direction Method of Multipliers for Linear Programming'. Together they form a unique fingerprint.

Cite this