×

A decomposition-coordination approach for large scale optimization. (English) Zbl 0836.65077

Bailey, David H. (ed.) et al., Proceedings of the seventh SIAM conference on parallel processing for scientific computing, San Francisco, CA (USA), February 15-17, 1995. Philadelphia, PA: SIAM. 78-83 (1995).
We outline a general approach to solving distributed optimization problems of a certain type. First we duplicate some (or all) of the problem variables, so as to decompose the constraints into purely local subsets. This produces an artificial decomposition and an increase in the number of variables. In order to make sure the solutions of the new problem and the original one coincide, we introduce consistency constraints which force all duplicated copies of a variable to be equal at the solution. These equality constraints are the only non-local constraints in the resulting transformed problem.
We describe an iterative algorithm to find the saddle-point of this new problem. The central step of this iterative algorithm decomposes into independent parallel minimizations, followed by Lagrange multiplier updates which involve only local information transfers. After each step, the processing elements exchange coordination information and re-solve the subproblems. The idea is that several steps of this distributed iterative algorithm may produce a solution faster than a more traditional centralized algorithm.
For the entire collection see [Zbl 0829.00031].

MSC:

65K05 Numerical mathematical programming methods
90C06 Large-scale problems in mathematical programming
90C25 Convex programming
65Y05 Parallel numerical computation
PDFBibTeX XMLCite