### Methods for Convex and General Quadratic Programming

Computational methods are considered for finding a point that satisfies
the second-order necessary conditions for a general (possibly
nonconvex) quadratic program (QP). The first part of the paper
considers the formulation and analysis of an active-set method for a
generic QP with both equality and inequality constraints. The method
uses a search direction that is the solution of an equality-constrained
subproblem involving a "working set" of linearly independent
constraints. The method is a reformulation of a method for general QP
first proposed by Fletcher, and modified subsequently by Gould. The
reformulation facilitates a simpler analysis and has the benefit that
the algorithm reduces to a variant of the simplex method when the QP is
a linear program. The search direction is computed from a KKT system
formed from the QP Hessian and the gradients of the working-set
constraints. 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.

The second part of the paper focuses on the solution of QP problems
with constraints in so-called standard form. We describe how the
constituent KKT systems are solved, and discuss how an initial basis is
defined. Numerical results are presented for all quadratic programs in
the CUTEr test collection.

Return To PEG's
Home Page.