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.