Parallel Variable Distribution

An approach is presented here for solving optimization problems in which the variables are distributed among p processors. Each processor has primary responsibility for updating its own block of variables in parallel while allowing the remaining variables to change in a restricted fashion, e.g., along a steepest descent, quasi-Newton, or any arbitrary direction. This “forget-me-not” approach is a distinctive feature of the algorithm that has not been analyzed before. The parallelization step is followed by a fast synchronization step wherein the affine hull of the points computed by the parallel processors and the current point is searched for an optimal point. Convergence to a stationary point under continuous differentiability is established for the unconstrained case, as well as a linear convergence rate under the additional assumption of a Lipschitzian gradient and strong convexity. For problems constrained to lie in the Cartesian product of closed convex sets, convergence is established to a point satisfying a necessary optimality condition under Lipschitz continuous differentiability of the objective function. For problems with more general constraints, convergence is established under stronger conditions. Encouraging computational results on the Thinking Machines CM-5 multiprocessor are given on a subset of the publicly available CUTE set of nonlinear programming test problems.