Bound Constrained Optimization

From NEOS

Jump to: navigation, search

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

minimize f(x)
subject to l \leq x \leq u

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 x * of f(x). The standard first-order necessary condition for a local minimizer x * can be expressed in terms of the binding set

B(x^*) = \{ i : x_i^* = l_i, \partial_i f(x^*) \geq 0 \} \cup \{ i : x_i^* = u_i, \partial_i f(x^*) \leq 0 \}

at x * by requiring that

\partial_i f(x^*) = 0, \quad \forall i \not \in B(x^*).

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 x * to be a local minimizer of the bound-constrained problem is that the first-order condition hold and that

s^T \nabla^2 f(x^) s > 0

for all vectors s \not = 0 with s_i=0, \; i \in B_s(x^*) where

B_s(x^*) = B(x^*) \cap \{i : \partial_i f(x^*) \not = 0 \}

is the strictly binding set at x * .

Given any set of free variables F, we can define the reduced gradient and the reduced Hessian matrix, respectively, as the gradient and the Hessian matrix of f(x) 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 F of free variables consists of all the variables that are not strictly binding at x * . 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 Fk 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 solvers for bound-constrained optimization to solve these problems remotely over the Internet.

Retrieved from "http://wiki.mcs.anl.gov/NEOS/index.php/Bound_Constrained_Optimization"
Personal tools