An interior point method for general large-scale quadratic programming problems

In this paper, the authors present an interior point algorithm for solving both convex and nonconvex quadratic programs. The method, which is an extension of the present interior point work on linear programming problems, efficiently solves a wide class of large-scale problems and forms the basis for a sequential quadratic programming solver for general large scale nonlinear programs. The key to the algorithm is a three-dimensional cost improvement subproblem, which is solved at every iteration. The authors have developed an approximate recentering procedure and a novel, adaptive big-ℳ Phase I procedure that are essential to the success of the algorithm. They describe the basic method along with the recentering and big-ℳ Phase I procedures. Details of the implementation and computational results are also presented.