Decision Tree for Optimization Software

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, 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.

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:

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

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

For more information on global optimization, see GLOBOPT