| After reviewing both Shor's Ellipsoid Algorithm and Ferris and Mangasarian's Parallel Variable Distribution scheme, the Ellipsoid Algorithm is placed within the outer framework of the Parallel Variable Distribution scheme to form the Parallel Variable Distribution Ellipsoid Algorithm. In this new algorithm, the variables of an optimization problem are distributed among p parallel processors, each processor is responsible for using the Ellipsoid Algorithm to update its assigned block of variables while holding the variables assigned to the other processors fixed at their current values, the p optimal subproblem solutions are then recombined to form the next iterate for the overall problem, and this point is possibly recentered to move it away from the boundary of the feasible region. Various methods of decomposing the problem into subproblems, synchronizing the subproblem solutions, and recentering the synchronized point are investigated. Several algorithms are presented for determining whether a given optimization problem can be equivalently expressed as a problem with block separable constraints. Convergence criteria are established for unconstrained problems and problems with block separable constraints, and simulated parallel computational results are presented for unconstrained problems, problems with block separable constraints, and problems with more general constraints. A general improvement to Shor's Ellipsoid Algorithm is also discussed and implemented, one which may allow the algorithm to work around the situation of encountering a violated constraint with a zero gradient vector. |
