DATA-PARALLEL QUADRATIC-PROGRAMMING ON BOX-CONSTRAINED PROBLEMS

We develop designs for the data parallel solution of quadratic programming problems subject to box constraints. In particular, we consider the class of algorithms that iterate between projection steps that identify candidate active sets and conjugate gradient steps that explore the working space. Using the algorithm of More and Toraldo [Report MCS-p77-05 89, Argonne National Laboratory, Illinois, 1989] as a specific instance of this class of algorithms we show how its components can be implemented efficiently on a data-parallel SIMD computer architecture. Alternative designs are developed for both arbitrary, unstructured Hessian matrices and for structured problems. Implementations are carried out on a Connection Machine CM-2. They are shown to be very efficient, achieving a peak computing rate over 2 Chops. Problems with several hundred thousand variables are solved within one minute of solution time on the 8K CM-2. Extremely large test problems, with up to 2.89 million variables, are also solved efficiently. The data parallel implementation outperforms a benchmark implementation of interior point algorithms on an IBM 3090-6009 vector supercomputer and a successive overrelaxation algorithm on an Intel iPSC/860 hypercube.