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.