### Methods for Convex and General Quadratic Programming

This paper considers computational methods for finding a point satisfying
the second-order necessary conditions for a general (possibly nonconvex)
quadratic program (QP). The first part of the paper defines a framework
for the formulation and analysis of feasible-point active-set methods for
QP. This framework defines a class of methods in which a primal-dual
search pair is the solution of an equality-constrained subproblem
involving a "working set" of linearly independent constraints. This
framework is discussed in the context of two broad classes of active-set
method for quadratic programming: *binding-direction methods* and
*nonbinding-direction methods*. We recast a binding-direction
method for general QP first proposed by Fletcher, and subsequently
modified by Gould, as a nonbinding-direction method. This reformulation
gives the primal-dual search pair as the solution of a KKT-system formed
from the QP Hessian and the working-set constraint gradients. It is
shown that, under certain circumstances, the solution of this KKT-system
may be updated using a simple recurrence relation, thereby giving a
significant reduction in the number of KKT systems that need to be
solved.

In the second part of the paper, the nonbinding-direction framework
is applied to QP problems with constraints in standard form, and
to the dual of a convex QP. A linearly constrained augmented
Lagrangian method is proposed that obviates the need for a separate
procedure for finding a feasible point. Finally, two approaches are
considered for solving the constituent KKT systems. The first
approach uses a variable-reduction technique requiring the
calculation of the Cholesky factor of the reduced Hessian. The
second approach uses a symmetric indefinite factorization of a fixed
KKT matrix in conjunction with the factorization of a smaller
matrix that is updated at each iteration.

Return To PEG's
Home Page.