Parallel algorithms for constrained optimization

Some fundamental properties of parallel computing and theoretical speedup are discussed, and a specific application of parallel computing to the multiple-cost-row linear programming problem is analyzed. An example of this problem which exhibits superlinear speedup for a specific instance, as well as a theoretical analysis of a problem in which superlinear speedup is possible on the average, is provided.; Many of the well-known methods for solving difficult constrained global optimization problems are reviewed. The specific problem of finding the global minimum of a concave or indefinite quadratic function which is restricted to a bounded polyhedral set is described, and the theoretical difficulty and solution characteristics are presented.; A parallel branch and bound approach is applied to the problem of finding the global minimum of large-scale concave and indefinite quadratic functions restricted to bounded polyhedral sets. The objective functions consist of both a nonlinear part (concave or indefinite) and a strictly linear part, which are coupled by the linear constraints. Underestimators of the objective function are easily constructed and minimized over the feasible domain to get both upper and lower bounds on the global minimum function value. At each minor iteration of the algorithm, the feasible domain is divided into subregions and underestimating problems over each subregion are solved in parallel. Branch and bound techniques can then be used to eliminate parts of the feasible domain from consideration and improve the upper and lower bounds. It is shown that the algorithms guarantee that a solution is obtained to within any specified tolerance in a finite number of steps. An extensive set of computational results are presented for problems with up to 125 nonlinear variables and up to 400 linear variables. These results were obtained on a four processor CRAY 2 supercomputer using both sequential and parallel implementations of the algorithm.; Finally, a new formulation of the Linear Complementarity Problem (LCP) as a concave quadratic function subject to linear constrains is presented. This equivalence allows the parallel algorithm presented for finding the global minimum of concave quadratic functions to be applied directly to solve the LCP.