Optimization Online


Alternating Direction Method of Multipliers for Linear Programming

Bingsheng He(hebma***at***nju.edu.cn)
Xiaoming Yuan(xmyuan***at***hkbu.edu.hk)

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

Keywords: Linear programming, Alternating direction method of multipliers, Parallel computation

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )


Download: [PDF]

Entry Submitted: 06/07/2015
Entry Accepted: 06/07/2015
Entry Last Modified: 06/07/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society