Volker,
> I search for OO optimization algorithms (C++, open source) for use in
> extrema search (nonsmooth surfaces) and sensitivity analysis for
> multivariate problems.
Sorry to be late in catching up.
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 encluse 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 publically available C++ code is
Dietmar Ratz, http://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
http://www.uni-karlsruhe.de/~iam/html/literatur/c-toolbox.html
Another good package is VerGo by
Ronald Van Iwaarden, http://www-math.cudenver.edu/~rvan/
Ron's work is described in his thesis available from links
on that page. The software is available at
http://www-math.cudenver.edu/~rvan/VerGO/VerGO.html
A third excellent package is from Inst. f. Informatik III,
TU Harburg. See
http://www.ti3.tu-harburg.de/index.html
Especially follow the links [Software] ==> [PROFIL/BIAS]
==> [Globales Optimierungsverfahren]
I work with Baker Kearfott on GlobSol
http://www.mscs.mu.edu/~globsol/
but that is a Fortran 90 package.
Hope this is some help. This answer is also at
http://www.mscs.mu.edu/~georgec/IFAQ/glopt.html
George F. Corliss
Dept. Math, Stat, Comp Sci
Marquette University
P.O. Box 1881
Milwaukee, WI 53201-1881 USA
georgec@mscs.mu.edu; CorlissG@Marquette.edu
http://www.mscs.mu.edu/~georgec/
Office: 414-288-6599; Dept: 288-7375; Fax: 288-5472
--------------------- Object Oriented Numerics List --------------------------
* To subscribe/unsubscribe: use the handy web form at
http://oonumerics.org/oon/
* If this doesn't work, please send a note to owner-oon-list@oonumerics.org
This archive was generated by hypermail 2b29 : Wed Feb 20 2002 - 03:20:08 EST