Interval Methods
Overview
Global optimization methods that use interval techniques provide
rigorous guarantees that a global minimizer is found. Interval
techniques are used to compute global information about functions over
large regions (box-shaped), e.g., strict bounds on function values,
Lipschitz constants, higher derivatives. Most global optimization
methods using interval techniques employ a branch and bound strategy. These
algorithms decompose the search domain into a collection of boxes for
which the lower bound on the objective function is calculated by an
interval technique.
Application Domains
Interval methods require that the objective function be formulated by
an analytic expression that is provided to the algorithm; this
expression is used by an interval technique to compute the
bounds. The basic design for interval methods does not require the
calculation of the derivative information, though the efficiency of
these algorithms can be improved if the derivative or Hessians are
available. The application of interval methods to high dimensional
problems remains an open problem. Present techniques are practically
limited to problems with several hundreds of variables.
Interval methods have been applied to a variety of challenging
optimization problems. Recent conferences on
interval methods describe a variety of successful applications.
Software
Several global optimization packages using interval methods
are listed here.
References
Eldon Hansen, Global Optimization Using Interval Analysis.
Dekker, New York 1992.
A good introduction to interval techniques for the solution of global
optimization problems and of nonlinear systems of equations with several solutions.
A bibliography of interval methods for global optimization
is maintained by Baker Kearfott.
Reliable Computing (formerly Interval Computations) contains a variety of articles relating the application
of interval methods to global optimization.
Miscellaneous Links
The web page on interval
computations provides a comprehensive collection of pointers to interval methods.
Some online introductions to interval methods are given
here