An Algorithm for Large-Scale Quadratic Programming

We are particularly concerned in solving (1.1) when n is large and the vectors a, and matrix H are sparse. We do not restrict H to being positive (semi-)definite and consequently are content with finding local solutions to (1.1). Of course, for many classes of problem, it is known a priori that any local solution is a global one. Our method is fundamentally related to that proposed by Fletcher (1971), but makes use of sparse matrix technology (in particular, linear programming basis handling techniques) to exploit the nature of the problem. In Section 2, we describe a general framework for our method. Linear algebraic issues are considered in Section 3 together with a description of how these issues relate to solving more specific quadratic programming problems of the form