A Large-Scale Quadratic Programming Solver Based on Block-Lu Updates of the KKT System

Quadratic programming QP problems arise naturally in a variety of applications. In many cases, a good estimate of the solution may be available. It is desirable to be able to utilize such information in order to reduce the computational cost of finding the solution. Active-set methods for solving QP problems differ from interior-point methods in being able to take full advantage of such warm-start situations. QPBLU is a new Fortran 95 package for minimizing a convex quadratic function with linear constraints and bounds. QPBLU is an active-set method that uses block-LU updates of an initial KKT system to handle active-set changes as well as low-rank Hessian updates. It is intended for convex QP problems in which the linear constraint matrix is sparse and many degrees of freedom are expected at the solution. Warm start capabilities allow the solver to take advantage of good estimates of the optimal active set or solution. A key feature of the method is the ability to utilize a variety of sparse linear system packages to solve the KKT systems. QPBLU has been tested on QP problems derived from linear programming problems from the University of Florida Sparse Matrix Collection using each of the sparse direct solvers LUSOL, MA57, PARDISO, SuperLU, and UMFPACK. We emphasize the desirability of such solvers to permit separate access to the factors they compute in order to improve the sparsity of the updates. Further comparisons are made between QPBLU and SQOPT on problems with many degrees of freedom at the solution.