Reduced-Gradient Methods
Reduced-gradient algorithms avoid the use of penalty parameters by searching
along curves that stay near the feasible set. Essentially, these methods take the
formulation (1.2) and use the equality constraints to
eliminate a subset of the variables, thereby reducing the original problem to a
bound-constrained problem in the space of the remaining variables. If 
is the vector of eliminated or basic
variables, and 
is the vector of nonbasic
variables, then
,
where the mapping 
is defined implicitly by the equation
(We have assumed that the components of 
have been arranged so that the basic variables come
first.) In practice,
can be recalculated using Newton's method whenever 
changes. Each Newton iteration has the form
where 
is the
Jacobian matrix of 
with respect
to the basic variables. The original constrained problem is now transformed into the
bound-constrained problem
Algorithms for this reduced subproblem subdivide the nonbasic variables
into two categories. These are the fixed variables 
, which usually include most of the variables that are at
either their upper or lower bounds and that are to be held constant on the current
iteration, and the superbasic variables 
, which are free to move on this iteration. The standard
reduced-gradient algorithm, implemented in CONOPT , searches along the
steepest-descent direction in the superbasic variables. The generalized reduced-gradient
codes GRG2 and LSGRG2 use more sophisticated
approaches. They either maintain a dense BFGS approximation of the Hessian of 
with respect to or use limited-memory
conjugate gradient techniques. MINOS
also uses a dense approximation to the superbasic Hessian matrix. The main difference
between MINOS and the other
three codes is that MINOS does
not apply the reduced-gradient algorithm directly to problem (1.1),
but rather uses it to solve a linearly constrained subproblem to find the next step. The
overall technique is known as a projected augmented Lagrangian algorithm.
Operations involving the inverse of 
are frequently required in reduced-gradient algorithms.
These operations are facilitated by an 
factorization of the matrix. GRG2 performs a dense factorization,
while CONOPT, MINOS, and LSGRG2 use sparse factorization
techniques, making them more suitable for large-scale problems.
When some of the components of the constraint functions are linear, most algorithms aim
to retain feasibility of all iterates with respect to these constraints. The optimization
problem becomes easier in the sense that there is no curvature term corresponding to these
constraints that must be accounted for and, because of feasibility, these constraints make
no contribution to the merit function. Numerous codes, such as NPSOL, MINOS and some routines from the
NAG ( NAG Fortran or NAG C ) library, are able to take
advantage of linearity in the constraint set. Other codes, such as those in the IMSL, PORT 3, and PROC NLP libraries, are
specifically designed for linearly constrained problems. The IMSL codes are based on a sequential
quadratic programming algorithm that combines features of the EQP and IQP variants. At
each iteration, this algorithm determines a set 
of near-active indices defined by
where the tolerances 
tend to decrease on later iterations. The step 
is obtained by solving the subproblem
where
and 
is a BFGS
approximation to 
. This algorithm
is designed to avoid the short steps that EQP methods sometimes produce, without taking
many unnecessary constraints into account, as IQP methods do.
Up To:
Nonlinearly Constrained Optimization.
[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]
Updated 28 March 1996