Inertia-Controlling Methods for General Quadratic Programming
Active-set quadratic programming (QP) methods use a working set to define
the search direction and multiplier estimates. In the method proposed by
Fletcher in 1971, and in several subsequent mathematically equivalent
methods, the working set is chosen to control the inertia of the reduced
Hessian, which is never permitted to have more than one nonpositive
eigenvalue. (We call such methods inertia-controlling.) This
paper presents an overview of a generic inertia-controlling QP method,
including the equations satisfied by the search direction when the reduced
Hessian is positive definite, singular and indefinite. Recurrence
relations are derived that define the search direction and Lagrange
multiplier vector through equations related to the Karush-Kuhn-Tucker
system. We also discuss connections with inertia-controlling methods that
maintain an explicit factorization of the reduced Hessian matrix.