[ Marquette | MSCS | Corliss | Vladik's Intervals ]
Interval FAQ: [ Entry page | Contents | Search ]
About Sun's f95 with Interval Support

Interval FAQ
Volker Claus Falk -- Global Optimization?

From Volker Claus Falk (Volker-Claus.Falk@bau-verm.uni-karlsruhe.de), Universitaet Karlsruhe:

I search for OO optimization algorithms (C++, open source) for use in extrema search (nonsmooth surfaces) and sensitivity analysis for multivariate problems

Response by Lionel Juillen:

(Lionel.Juillen@renault.fr), Renault, France.

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

Response by George Corliss:

(georgec@mscs.mu.edu), Marquette University.

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

[ Marquette | MSCS | Corliss | Vladik's Intervals ]
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

This page URL: http://www.mscs.mu.edu/~georgec/IFAQ/glopt.html
Last modified June 8, 1999. Send comments to (georgec@mscs.mu.edu)
Access count since 20 Apr 1999 : Graphical counter