Some Reformulations and Applications of the Alternating Direction Method of Multipliers

Jonathan Eckstein and Masao Fukushima
Additional contact information
Jonathan Eckstein: Thinking Machines Corporation, Mathematical Sciences Research Group
Masao Fukushima: Nara Institute of Science and Technology, Graduate School of Information Science

A chapter in Large Scale Optimization, 1994, pp 115-134 from Springer

Abstract: Abstract We consider the alternating direction method of multipliers decomposition algorithm for convex programming, as recently generalized by Eckstein and Bert- sekas. We give some reformulations of the algorithm, and discuss several alternative means for deriving them. We then apply these reformulations to a number of optimization problems, such as the minimum convex-cost transportation and multicommodity flow. The convex transportation version is closely related to a linear-cost transportation algorithm proposed earlier by Bertsekas and Tsitsiklis. Finally, we construct a simple data-parallel implementation of the convex-cost transportation algorithm for the CM-5 family of parallel computers, and give computational results. The method appears to converge quite quickly on sparse quadratic-cost transportation problems, even if they are very large; for example, we solve problems with over a million arcs in roughly 100 iterations, which equates to about 30 seconds of run time on a system with 256 processing nodes. Substantially better timings can probably be achieved with a more careful implementation.

Keywords: Convex programming; decomposition; multiplier methods; network flows; parallel algorithms (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4613-3632-7_7

Ordering information: This item can be ordered from
http://www.springer.com/9781461336327

DOI: 10.1007/978-1-4613-3632-7_7

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().