Problems/
Software

Benchmarks

Testcases

Books/
Tutorials

Tools

Websub-
mission

Other
Sources

 
              

Global Optimization

The occurrence of multiple extrema makes problem solving in nonlinear optimization even harder. Usually the user dreams of the global (best) minimizer, which might be difficult to obtain without supplying global information, which in turn is usually unavailable for a nontrivial case. The following picture shows the function

f(x,y)=x^2*(4-2.1*x^2+x^4/3)+x*y+y^2*(-4+4*y^2)

which has two global minima at (0.09,-0.71) and (-0.09,0.71) and four additional local minima.

The Unconstrained NLO-Problem:

min f(x), n=dim(x).

Global optimization is a difficult area, at least for larger n, since there is no easy algebraic characterization of global optimality. Most of the codes designed for minimization simply restrict themself to solve the equation grad(f(x))=0, which is only necessary of course. Methods using interval-arithmetic and branch&bound will in principle solve these problems, but the branch tree might become excessively large for difficult functions. Hence for higher dimensions and without special structure only stochastic or pseudostochastic methods will apply.
See however the books of Kearfott Rigorous Global Search: Continuous Problems Kluwer, Dordrecht 1996 and Floudas Deterministic Global Optimization: Theory, Algorithms and Applications, Kluwer, Dordrecht 1999. See A. Neumaier's paper on methods and software as well as J. Pinter's survey on available software and Sandia's survey on methods.
Mainly stochastic or heuristic search methods are available as PD:

BTRK Derivative-Free Boender-Timmer-Rinnoy Kan Algorithm, a stochastic optimization algorithm f90-version from Alan Miller
netlib/toms/667method of Zirilli et al (stochastic differential equation approach)
netlib/opt/simann simulated annealing, bound constraints may be prescribed
simannf90 f90-version from Alan Miller
ASA C, simulated annealing, bound constraints may be prescribed Matlab Interface
Fortran-GA genetic algorithm
PGAPack genetic algorithm, C, callable from Fortran
PIKAIA genetic algorithm f90 version
More GA codes

These methods are simple to use, but require a high number of function evaluations if you desire acceptable final precision. Here are codes which determine the global minimum of a Lipschitz continuous function on a finite box:
(DIRECT ( f77 , Matlab) using a bound for the Lipschitz constant of f and subdivision
gblSolve.m another Matlab implementation of DIRECT
glbFast Faster Matlab version of DIRECT using Fortran MEX
MCSHuyer&Neumaier's Multilevel Coordinate search, local search by SQP, Matlab
StoGOMadsen's hybrid method, Matlab
The following code fits a surrogate model to an expensive to evaluate function of few variables and analyzes/minimizes that:
SPACE global optimization through meta-modeling: fitting, cross -validation, prediction, minimization (C++)

 An important and challenging problem is that of computing minimal energy states of atom clusters. The following code is especially designed for these problems.
LJ computing Lenard-Jones clusters, Win/Solaris binaries

The Constrained NLO-Problem:

min f(x) subject to h(x)=0, g(x)>=0,
n=dim(x), m=dim(g), p=dim(h).

Few codes are available but this is an area of current research and more links will be added. See also the book by Eldon Hansen, Global Optimization Using Interval Analysis, Dekker, New York, 1992. For a good introduction into the theory see the book by Horst et al. For the state of the art until 1994, see the Horst&Pardalos handbook. A recent application-oriented overview is given in this book by Floudas.

GloptiPolyPolynomial objective and constraints, integer variables, needs SeDuMi (Matlab, GPL)
SOSTOOLSMatlab toolbox to solve sum of squares polynomial problems; needs SeDuMi and Matlab's symbolic toolbox (GPL)
glcFastMatlab/Fortran MEX version of Jones' new constrained DIRECT
INTOPT_90Interval software, f90, book, exhaustive search, automatic differentiation, bound and equality constraints, nonlinear systems, sources, binaries for SunOS and Win95, needs several local optimizers and linear algebra routines plus the author's interval package, superseded by GlobSol
VerGOC++, interval branch&bound, bound constraints, automatic differentiation, self-contained
genocopC, genetic algorithm, nonlinear inequality constraints, feasible starting point desirable
BARONsolves variety of global problems including discrete, binaries for HP, IBM, Sun, modeling language, websubmission
For more information on global optimization, see GLOBOPT
 Back to the top!

Date last revised: 10-23-2003