The general constrained optimization problem is to minimize a nonlinear function subject to nonlinear constraints. Two equivalent formulations of this problem are useful for describing algorithms. They are
where each 
is
a mapping from 
to 
, and 
and 
are index sets for inequality and equality constraints,
respectively; and
where 
maps to 
, and the lower- and upper-bound
vectors, 
and 
, may contain some infinite components.
The main techniques that have been proposed for solving constrained optimization problems are reduced-gradient methods, sequential linear and quadratic programming methods, and methods based on augmented Lagrangians and exact penalty functions. Fundamental to the understanding of these algorithms is the Lagrangian function, which for formulation (1.1) is defined as
The Lagrangian is used to express first-order and second-order conditions for a local minimizer. We simplify matters by stating just first-order necessary and second-order sufficiency conditions without trying to make the weakest possible assumptions.
The first-order necessary conditions for the existence of a local
minimizer 
of the constrained
optimization problem (1.1) require the existence of
Lagrange multipliers 
, such that
where
is the active set at , and 
if 
. This result requires a constraint
qualification to ensure that the geometry of the feasible set is adequately captured
by a linearization of the constraints about . A standard constraint
qualification requires the constraint normals, 
for 
, to be linearly independent.
The second-order sufficiency condition requires that 
satisfies the first-order condition and that the
Hessian of the Lagrangian
satisfies the condition
for all nonzero 
in the set
where
The previous condition guarantees that the optimization problem is well behaved near ; in
particular, if the second-order sufficiency condition holds, then is a strict local minimizer of
the constrained problem (1.1). An important ingredient in
the convergence analysis of a constrained algorithm is its behavior in the vicinity of a
point
that satisfies the second-order sufficiency condition.
Up To:
[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]
Updated 28 March 1996
