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


Global Optimization Survey - Main Page
Sandia National Laboratories

This page maintained by wehart@cs.sandia.gov
Last modified: March 10, 1997