File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/s40305-016-0136-0
- Scopus: eid_2-s2.0-84995640022
- WOS: WOS:000391061300002
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Alternating Direction Method of Multipliers for Linear Programming
Title | Alternating Direction Method of Multipliers for Linear Programming |
---|---|
Authors | |
Keywords | Linear programming Continuous optimization Alternating direction method of multipliers |
Issue Date | 2016 |
Citation | Journal of the Operations Research Society of China, 2016, v. 4, n. 4, p. 425-436 How to Cite? |
Abstract | © 2016, Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag Berlin Heidelberg. 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. |
Persistent Identifier | http://hdl.handle.net/10722/251185 |
ISSN | 2023 Impact Factor: 0.9 2023 SCImago Journal Rankings: 0.554 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | He, Bing Sheng | - |
dc.contributor.author | Yuan, Xiao Ming | - |
dc.date.accessioned | 2018-02-01T01:54:50Z | - |
dc.date.available | 2018-02-01T01:54:50Z | - |
dc.date.issued | 2016 | - |
dc.identifier.citation | Journal of the Operations Research Society of China, 2016, v. 4, n. 4, p. 425-436 | - |
dc.identifier.issn | 2194-668X | - |
dc.identifier.uri | http://hdl.handle.net/10722/251185 | - |
dc.description.abstract | © 2016, Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag Berlin Heidelberg. 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. | - |
dc.language | eng | - |
dc.relation.ispartof | Journal of the Operations Research Society of China | - |
dc.subject | Linear programming | - |
dc.subject | Continuous optimization | - |
dc.subject | Alternating direction method of multipliers | - |
dc.title | Alternating Direction Method of Multipliers for Linear Programming | - |
dc.type | Article | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1007/s40305-016-0136-0 | - |
dc.identifier.scopus | eid_2-s2.0-84995640022 | - |
dc.identifier.volume | 4 | - |
dc.identifier.issue | 4 | - |
dc.identifier.spage | 425 | - |
dc.identifier.epage | 436 | - |
dc.identifier.eissn | 2194-6698 | - |
dc.identifier.isi | WOS:000391061300002 | - |
dc.identifier.issnl | 2194-668X | - |