A direct active set algorithm for large sparse quadratic programs with simple bounds

The authors show how a direct active set method for solving definite and indefinite quadratic programs with simple bounds can be efficiently implemented for large sparse problems. All of the necessary factorizations can be carried out in a static data structure that is set up before the numeric computation begins. The space required for these factorizations is no larger than that required for a single sparse Cholesky factorization of the Hessian of the quadratic. The authors propose several improvements to this basic algorithm: a new way to find a search direction in the indefinite case that allows the freeing of more than one variable at a time and a new heuristic method for finding a starting point. These ideas are motivated by the two-norm trust region problem. Additionally, the authors also show how projection techniques can be used to add several constraints to the active set at each iteration. The present experimental results show that an algorithm with these improvements runs much faster than the basic algorithm for positive definite problems and finds local minima with lower function values for indefinite problems.