Bound-constrained optimization problems play an important role in the development of software for the general constrained problem because many constrained codes reduce the solution of the general problem to the solution of a sequence of bound-constrained problems. The development of software for this problem, which we state as
is also important in applications because parameters that describe physical quantities are often constrained to lie in a given range.
Algorithms for the solution of bound-constrained problems seek a local minimizer of
. The standard first-order necessary condition for a
local minimizer
can be expressed in terms of the binding set
at by requiring that
There are other ways to express this condition, but this form brings out
the importance of the binding constraints. A second-order sufficient condition for to be a local
minimizer of the bound-constrained problem is that the first-order condition hold and that
for all vectors
with
where
is the strictly binding set at .
Given any set of free variables , we can define the reduced gradient and the reduced
Hessian matrix, respectively, as the gradient of
and the Hessian matrix of
with respect to
the free variables. In this terminology, the second-order condition requires that the
reduced gradient be zero and that the reduced Hessian matrix be positive definite when the
set
of free variables consists
of all the variables that are not strictly binding at
. As we shall see, algorithms for
the solution of bound-constrained problems use unconstrained minimization techniques to
explore the reduced problem defined by a set
of free variables. Once this exploration is complete, a
new set of free variables is chosen with the aim of driving the reduced gradient to zero.
The NEOS SERVER also has a bound-constrained minimization facility to solve these problems remotely over the Internet.
Up To:
[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]
Updated 28 March 1996
