Eckstein, Jonathan; Fukushima, Masao Some reformulations and applications of the alternating direction method of multipliers. (English) Zbl 0816.90109 Hager, W. W. (ed.) et al., Large scale optimization. State of the art. Papers presented at the conference, held February 15-17, 1993 at the University of Florida, Gainesville, FL, USA. Dordrecht: Kluwer Academic Publishers. 115-134 (1994). Summary: We consider the alternating direction method of multipliers decomposition algorithm for convex programming, as recently generalized by the first author and D. P. Bertsekas [Math. Program. 55A, No. 3, 293-318 (1992; Zbl 0765.90073)]. We give some reformulations of the algorithm, and discuss several alternative means for deriving time. 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 D. P. Bertsekas and J. N. Tsitsiklis [‘Parallel and distributed computation: numerical methods’ (1989; Zbl 0743.65107)]. 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.For the entire collection see [Zbl 0795.00025]. Cited in 53 Documents MSC: 90C25 Convex programming 90B10 Deterministic network models in operations research 65Y05 Parallel numerical computation 90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) 90C06 Large-scale problems in mathematical programming Keywords:alternating direction method; multipliers decomposition algorithm; minimum convex-cost transportation; multicommodity flow; data-parallel implementation; sparse quadratic-cost transportation Citations:Zbl 0765.90073; Zbl 0743.65107 Software:NETGEN PDFBibTeX XMLCite \textit{J. Eckstein} and \textit{M. Fukushima}, in: Large scale optimization. State of the art. Papers presented at the conference, held February 15-17, 1993 at the University of Florida, Gainesville, FL, USA. Dordrecht: Kluwer Academic Publishers. 115--134 (1994; Zbl 0816.90109)