Global optimization

Global optimization is a branch of applied mathematics and numerical analysis that deals with the optimization of a function or a set of functions according to some criteria. Typically, a set of bound and more general constraints is also present, and the decision variables are optimized considering also the constraints.

General

A common (standard) model form is the minimization of one real-valued function $f$ in the parameter-space ${\vec {x}}\in P$ , or its specified subset ${\vec {x}}\in D$ : here $D$ denotes the set defined by the constraints.

(The maximization of a real-valued function $g(x)$ is equivalent to the minimization of the function $f(x):=(-1)\cdot g(x)$ .)

In many nonlinear optimization problems, the objective function $f$ has a large number of local minima and maxima. Finding an arbitrary local optimum is relatively straightforward by using classical local optimisation methods. Finding the global minimum (or maximum) of a function is far more difficult: symbolic (analytical) methods are frequently not applicable, and the use of numerical solution strategies often leads to very hard challenges.

Applications of global optimization

Typical examples of global optimization applications include:

Protein structure prediction (minimize the energy/free energy function)
Computational phylogenetics (e.g., minimize the number of character transformations in the tree)
Traveling salesman problem and electrical circuit design (minimize the path length)
Chemical engineering (e.g., analyzing the Gibbs free energy)
Safety verification, safety engineering (e.g., of mechanical structures, buildings)
Worst case analysis
Mathematical problems (e.g., the Kepler conjecture)
Object packing (configuration design) problems
The starting point of several molecular dynamics simulations consists of an initial optimization of the energy of the system to be simulated.
Spin glasses
Calibration of radio propagation models and of many other models in the sciences and engineering
Curve fitting like Non-linear least squares analysis and other generalizations, used in fitting model parameters to experimental data in chemistry, physics, medicine, astronomy, engineering.

Approaches

Deterministic methods

The most successful general strategies are:

Inner approximation
Outer approximation
Cutting plane methods
Branch and bound methods
Interval methods / Interval algebra (see interalg from OpenOpt and GlobSol
Methods based on real algebraic geometry

Stochastic methods

Main page: Stochastic optimization

Several Monte-Carlo-based algorithms exist:

Simulated annealing
Direct Monte-Carlo sampling
Basin hopping technique (aka Monte-Carlo with minimization)
Stochastic tunneling
Parallel tempering
Continuation methods

Heuristics and metaheuristics

Main page: Metaheuristic

Other approaches include heuristic strategies to search the search space in a more or less intelligent way, including:

Evolutionary algorithms (e.g., genetic algorithms and evolution strategies)
Swarm-based optimization algorithms (e.g., particle swarm optimization, Multi-swarm optimization and ant colony optimization)
Memetic algorithms, combining global and local search strategies
Reactive search optimization (i.e. integration of sub-symbolic machine learning techniques into search heuristics)
Differential evolution
Graduated optimization

Response surface methodology based approaches

Efficient Global Optimization
IOSO Indirect Optimization based on Self-Organization