Gradient Projection for General Quadratic Programs (Replaced by TR-2007-16)

We present a hybrid algorithm for solving large-scale quadratic programs (QPs) that is based on a combination of techniques from gradient projection, augmented Lagrangian, and filter methods. The resulting algorithm is globally and finitely convergent. The method efficiently accommodates a matrix-free implementation and is suitable for large-scale problems with many degrees of freedom. The algorithm is based on two main phases. First, gradient projection iterations approximately minimize the augmented Lagrangian function and provide an estimate of the optimal active set. Second, an equality-constrained QP is approximately minimized on this subspace in order to generate a second-order search direction. Numerical experiments on a subset of the CUTEr QP test problems demonstrate the effectiveness of the proposed approach.