Preprint A25/2001
Parallel variable distribution for constrained optimization

Mikhail Solodov | Sagastizábal, Claudia

**Keywords: **
parallel optimization; distributed computing

In the parallel variable distribution framework for solving
optimization problems (PVD), the variables are distributed among
parallel processors with each processor having the primary responsibility for
updating its block of variables while allowing the remaining
``secondary'' variables to
change in a restricted fashion along some easily computable directions.
For constrained nonlinear programs convergence theory for PVD
algorithms was previously available only for the
case of convex feasible set. Additionally, one either had to assume that
constraints are block-separable, or to use exact
projected gradient directions for the change of secondary variables.
In this paper, we propose
two new variants of PVD for the constrained case.
Without assuming convexity of constraints, but assuming block-separable
structure, we show that PVD subproblems can be solved inexactly
by solving their quadratic programming approximations.
This extends PVD to nonconvex (separable) feasible sets, and provides
a constructive way of solving the parallel subproblems.
For inseparable constraints, but assuming convexity,
we develop a PVD method based on suitable approximate projected
gradient directions. The approximation criterion is based on a certain
error bound result, and it is readily implementable. Using such approximate
directions may be especially useful
when the projection operation is computationally expensive.