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


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

Cinque Terre

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, Floudas Deterministic Global Optimization: Theory, Algorithms and Applications , Kluwer, Dordrecht 1999, and Hansen&Walster Global Optimization Using Interval Analysis , Marcel Dekker 2003. See A. Neumaier's paper on methods and softwares

Mostly stochastic or heuristic search methods have been available freely, but this has changed, see below for constrained optimization.

DFL A library of algorithms for derivative free (global) optimization (f90, C, Julia)
PANMIN Two stochastic methods, one MPI parallelized; uses Merlin/MCL
BTRK f90-version of the derivative-free Boender-Timmer-Rinnoy Kan algorithm
PSwarm Hybrid derivative-free solver (particle swarm & direct search), AMPL interface (C (also parallel), Matlab)
MEMPSODE Hybrid derivative-free solver (particle swarm & local search); uses Merlin/MCL
MLOCPSOA particle swarm paradigm, AMPL interface (C source, binaries)
netlib/toms/667 method of Zirilli et al (stochastic differential equation approach)
GANSO several methods for global&nonsmooth problems (C/C++)
netlib/opt/simann simulated annealing (f77)
simannf90 f90-version from Alan Miller
simann.m Matlab version
Java-SA Java implementation of SA
Simanneal Python implementation of SA
CSA Python implementation of coupled SA
ASA C, adaptive simulated annealing, Python interface
CMA-ES Evolution Strategy with Covariance Matrix Adaptation (Matlab)
PGSL A direct stochastic algorithm for global search incl constraints (C)
Fortran-GA genetic algorithm
PIKAIA genetic algorithm; IDL, f90, parallel versions Excel version
DGPF Distributed Genetic Programming Framework. needs Eclipse for compile
SIGOA Simple Interface for Global Optimization Algorithms, Java source

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, C, Julia) using a bound for the Lipschitz constant of f and subdivision
MCS Huyer&Neumaier's Multilevel Coordinate search, local search by SQP, Matlab

The following codes fit a surrogate model to an expensive to evaluate function of few variables and analyze/minimize that:

SPACE global optimization through meta-modeling: fitting, cross-validation, prediction, minimization (C++)
Spacemap Optimization using Surrogate Models (Matlab)

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. An application-oriented overview is given in this book by Floudas. An introduction is given by Liberti and recent survey papers on the mixed-integer case are Burer et al and Belotti et al

Black Box Opt Black box functions and constraints, expensive evaluations, no derivatives needed (C, GPL)
GloptiPoly Polynomial objective and constraints, integer variables, needs SeDuMi (Matlab, GPL)
SOSTOOLS Matlab toolbox to solve sum of squares polynomial problems; needs SeDuMi and Matlab's symbolic toolbox (GPL)
INTLAB Matlab toolbox for self-validating algorithms
DIRECT version of DIRECT that handles general constraints using L1 penalty (Matlab)
GlobSol Interval software, f90, book, exhaustive search, automatic differentiation, bound and equality constraints, nonlinear systems, sources, needs several local optimizers and linear algebra routines plus the author's interval package
VerGO C++, interval branch&bound, bound constraints, automatic differentiation, self-contained
Genocop various versions, including for nonlinear constraints (C)
PGSL A direct stochastic algorithm for global search incl constraints (C)
BARON solves variety of global problems deterministically including discrete, free demo version from GAMS
COUENNE solves continuous and discrete global problems deterministically, C++
SCIP solves continuous and discrete global problems deterministically, C
Maple GOT toolbox containing both B&B and random methods

For more information on global optimization, see GLOBOPT