Interval FAQ: [ Entry page | Contents | Search ]

About Sun's f95 with Interval Support

Volker Claus Falk -- Global Optimization?

Please take a look at the "Decision Tree for Optimization Software" http://plato.la.asu.edu/guide.html

On what kind of optimization problems do you have ?

Lionel Juillen

See also an excellent discussion at http://solon.cma.univie.ac.at/~neum/glopt.html

I am an advocate of interval or validated methods. Instead of floating point computations, we compute with intervals of real numbers, and arrange to enclose both roundoff and truncation errors to that the correct answer is guaranteed to belong to the interval answer we get. Often, we are able to prove rigorously on a computer that the problem has a unique solution, or that it has no solution at all.

For rigorous global optimization, we use a combination of rigorous bounds for the ranges of objective and constraint functions, as well as their gradients and Hessians, interval Newton variants, constraint propagation, and other strategies in a rigorous branch and bound. The result is that (subject to programming error) a global minimum is never discarded and feasibility is guaranteed.

For non-smooth surfaces, strategies using derivatives may not be applicable, but guaranteed range bounding still drives a branch and bound algorithm.

The advantage is that interval global optimization routine
returns a box *[X]* (or a set of boxes) in which the global
minimizer must lie and *[F]* tight lower and upper bounds for
the minimum value. If there are constraints, we guarantee
that *[X]* contains at least one feasible point. We guarantee
that no other feasible point x not in *[X]* yields a lower objective.

The cost varies in a highly problem dependent manner.
Sometimes, interval techniques are faster than approximate
techniques, because they may discard rapidly large portions
of the search space in which no global minimum may appear.
In the worst case (which does appear), execution is O(n^2)
in the number of variables. We have solved toy problems
of dimension 256 and a few meaningful problems of dimension
100. Typically, we quit in the range of 10-40 variables.
If you are still reading, one of the top world's experts and
author of a publicly available C++ code is
Dietmar Ratz
(www.aifb.uni-karlsruhe.de/~dra/)

Institut für Angewandte Informatik und Formale Beschreibungsverfahren

at your own University in Karlsruhe

His software appears in *C++ Toolbox for Verified Computing
- Basic Numerical Problems,* Springer-Verlag, Heidelberg
(ISBN 3-540-59110-9) and is available at
www.uni-karlsruhe.de/~iam/html/literatur/c-toolbox.html

Another good package is VerGo by Ronald Van Iwaarden (www-math.cudenver.edu/~rvan/). Ron's work is described in his thesis available from links on that page. The software is available at www-math.cudenver.edu/~rvan/VerGO/VerGO.html

A third excellent package is from Inst. f. Informatik III, TU Harburg. See www.ti3.tu-harburg.de/ Especially follow the links [Software] ==> [PROFIL/BIAS] ==> [Globales Optimierungsverfahren]

I work with Baker Kearfott on GlobSol www.mscs.mu.edu/~globsol/, but that is a Fortran 90 package.

George F. Corliss

Interval FAQ: [ Entry page | Contents | Search ]

About Sun's f95 with Interval Support

If *you* have a question related to validated computing, interval
analysis, or related matters, I recommend

- Vladik Kreinovich's Interval Computation web site, or
- Submit it to the interval computations listserv: reliable_computing@interval.louisiana.edu

Last modified June 8, 1999. Send comments to (

Access count since 20 Apr 1999 :