×

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

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

Software:

NETGEN
PDFBibTeX XMLCite