Parallel computational issues for box constrained quadratic programming

This paper deals with the solution of Box-Constrained Quadratic Programming problems on MIMD distributed-memory computers. We focus on the dense case and consider a Projected Gradient (PG) algorithm that alternates gradient projection steps, in order to identify a candidate active set, and Newton steps, in order to explore the face determined by such active set. The concurrent version of the PG algorithm is based on the parallelization of the Linear Algebra operations occurring in the algorithm. The crucial point is that all such operations are restricted to the variables that are not in the working set. Moreover, the most critical operation is the update of the Cholesky factor of the Hessian matrix in Newton steps. Since the working set can drastically change, such update is much more complicated than in the usual active set strategy, where only rank-one updates occur. We present first experiences in the development of effective parallel routines that perform reduced Linear Algebra operations in ScaLAPACK environment, showing also some results from implementations carried out on an Intel iPSC/860.