The sequential quadratic programming (sequential QP) algorithm is a
generalization of Newton's method for unconstrained optimization in that it finds a step
away from the current point by minimizing a quadratic model of the problem. A number of
packages, including NPSOL, NLPQL, OPSYC, OPTIMA, MATLAB, and SQP, are founded on this approach. In
its purest form, the sequential QP algorithm replaces the objective function with the
quadratic approximation
and replaces
the constraint functions by linear approximations. For the formulation (1.1), the step 
is calculated by solving the quadratic subprogram
The local convergence properties of the sequential QP approach are well
understood when 
satisfies the
second-order sufficiency conditions. If the starting point 
is sufficiently close to 
, and the Lagrange multiplier estimates 
remain sufficiently close to 
, then the sequence generated by
setting 
converges to at a
second-order rate. These assurances cannot be made in other cases. Indeed, codes based on
this approach must modify the subproblem (1.3) when
the quadratic 
is unbounded below
on the feasible set or when the feasible region is empty.
The Lagrange multiplier estimates that are needed to set up the second-order term in can be
obtained by solving an auxiliary problem or by simply using the optimal multipliers for
the quadratic subproblem at the previous iteration. Although the first approach can lead
to more accurate estimates, most codes use the second approach.
The strategy based on (1.3) makes the decision
about which of the inequality constraints appear to be active at the solution internally
during the solution of the quadratic program. A somewhat different algorithm is obtained
by making this decision prior to formulating the quadratic program. This variant
explicitly maintains a working set 
of apparently active indices and solves the quadratic
programming problem
to find the step . The contents of 
are updated at each iteration by
examining the Lagrange multipliers for the subproblem (1.4)
and by examining the values of 
at the new iterate 
for 
. This approach is usually called the
EQP (equality-based QP) variant of sequential QP, to distinguish it from the IQP
(inequality-based QP) variant described above.
The sequential QP approach outlined above requires the computation of 
. Most codes replace this matrix with
the BFGS approximation 
, which is
updated at each iteration. An obvious update strategy (consistent with the BFGS update for
unconstrained optimization) would be to define
and update the matrix by using the BFGS formula
However, one of the properties that make Broyden-class methods appealing
for unconstrained problems-its maintenance of positive definiteness in -is no longer assured, since 
is usually positive definite only in
a subspace. This difficulty may be overcome by modifying 
. Whenever 
is not sufficiently positive, is reset to
where 
is the
number closest to 1 such that 
for some 
. The SQP and NLPQL codes use an approach of this
type.
The convergence properties of the basic sequential QP algorithm can be improved by
using a line search. The choice of distance to move along the direction generated by the
subproblem is not as clear as in the unconstrained case, where we simply choose a step
length that approximately minimizes 
along the search direction. For constrained problems we
would like the next iterate not only to decrease but also to come closer to
satisfying the constraints. Often these two aims conflict, so it is necessary to weigh
their relative importance and define a merit or penalty function, which
we can use as a criterion for determining whether or not one point is better than another.
The 
merit function
where 
are
penalty parameters, is used in the NLPQL,
MATLAB, and SQP codes, while the augmented
Lagrangian merit function
where
is used in the NLPQL,
NPSOL, and OPTIMA codes. The OPSYC code for
equality-constrained problems (for which 
) uses the merit function
which combines features of 
and 
.
An important property of the merit function is that if satisfies the second-order
sufficiency condition, then is a local minimizer of , provided the penalty parameters
are chosen so that 
. Although
this is an attractive property, the use of requires care. The main
difficulty is that is not differentiable at any 
with 
. Another difficulty is that although is a local minimizer of , it is still
possible for the function to be unbounded below. Thus, minimizing does not always lead to a
solution of the constrained problem.
The merit function 
has
similar properties. If satisfies the second-order sufficiency condition and 
, then is a local minimizer of , provided the
penalty parameters 
are
sufficiently large. If 
, then we
can say only that has a minimizer 
near and
that
approaches
as 
converges to . Note that in
contrast to , the merit function is differentiable. The Hessian matrix of is discontinuous at any with 
for 
, but, at least in the case 
, these points tend to occur far from the solution.
The use of these merit functions by NLPQL is typical of other codes.
Given an iterate 
and the search
direction ,
NLPQL sets 
, where the step length 
approximately minimizes 
. If the merit function is selected, the step length is chosen to
approximately minimize 
where is a solution
of the quadratic programming subproblem (1.3) and 
is the associated Lagrange
multiplier.
Up To:
Nonlinearly Constrained Optimization.
[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]
Updated 28 March 1996
