### Active-Set methods for Convex Quadratic Programming

Computational methods are proposed for solving a convex quadratic
program (QP). Active-set methods are defined for a particular primal and
dual formulation of a QP with general equality constraints and simple
lower bounds on the variables. In the first part of the paper, two
methods are proposed, one primal and one dual. These methods generate a
sequence of iterates that are feasible with respect to the equality
constraints associated with the optimality conditions of the primal-dual
form. The primal method maintains feasibility of the primal inequalities
while driving the infeasibilities of the dual inequalities to zero. In
contrast, the dual method maintains feasibility of the dual inequalities
while moving to satisfy the infeasibilities of the primal inequalities.
In each of these methods, the search directions satisfy a KKT system of
equations formed from Hessian and constraint components associated with
an appropriate column basis. The composition of the basis is specified
by an active-set strategy that guarantees the nonsingularity of each set
of KKT equations. Each of the proposed methods is a conventional
active-set method in the sense that an initial primal- or dual-feasible
point is required. In the second part of the paper, it is shown how the
quadratic program may be solved as coupled pair of primal and dual
quadratic programs created from the original by simultaneously shifting
the simple-bound constraints and adding a penalty term to the objective
function. Any conventional column basis may be made optimal for such a
primal-dual pair of shifted-penalized problems. The shifts are then
updated using the solution of either the primal or the dual shifted
problem. An obvious application of this approach is to solve a shifted
dual QP to define an initial feasible point for the primal (or \emph{vice
versa}). The computational performance of each of the proposed methods
is evaluated on a set of convex problems from the CUTEst test
collection.

Return To PEG's
Home Page.