Active set methods have been criticized because the working set changes slowly; at each
iteration at most one constraint is added to or dropped from the working set. If there are
constraints active at the
initial
, but
constraints active at the solution, then at least
iterations are required for
convergence. This property can be a serious disadvantage in large problems if the working
set at the starting point is vastly different from the active set at the solution.
Consequently, recent investigations have led to algorithms that allow the working set to
undergo radical changes at each iteration and to interior-point algorithms that do not
explicitly maintain a working set.
The gradient-projection algorithm is the prototypical method
that allows large changes in the working set at each iteration. Given , this algorithm searches along the piecewise linear
path
where is the projection onto
the feasible set. A new point
is obtained when a suitable is found. For bound-constrained problems, the projection
can be easily computed by setting
where is the
middle (median) element of a set. The search for
has to be done carefully since the function
is only piecewise differentiable.
If properly implemented, the gradient-projection method is guaranteed to identify the active set at a solution in a finite number of iterations. After it has identified the correct active set, the gradient-projection algorithm reduces to the steepest-descent algorithm on the subspace of free variables. As a result, this method is invariably used in conjunction with other methods with faster rates of convergence.
Trust-region algorithms can be extended to bound-constrained problems. The main
difference between the unconstrained and the bound-constrained version is that we now
require the step to be an
approximate solution of the subproblem
where
An accurate solution to this subproblem is not necessary, at least on
early iterations. Instead, we use the gradient-projection algorithm to predict a step (the Cauchy step) and then
require merely that our step,
, satisfies the constraints in the trust-region subproblem with
. An approach along these lines is
used by VE08 and PORT 3. In the bound-constrained
code in LANCELOT the trust
region is defined by the
-norm
and
, yielding the equivalent
subproblem
where is the
vector of all ones.
The advantage of strategies that combine the gradient-projection method with
trust-region methods is that the working set is allowed to change rapidly, and yet
eventually settle into the working set for the solution. LANCELOT uses this approach,
together with special data structures that exploit the (group) partially separable
structure of , to solve large
bound-constrained problems.
Up To:
Bound Constrained Optimization.
[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]
Updated 28 March 1996