Global optimization

This article includes a list of general references but lacks sufficient corresponding inline citations. Please help improve this article by introducing more precise citations. (December 2013) (Learn how and when to remove this message)

Global optimization is a branch of operations research, applied mathematics, and numerical analysis that attempts to find the global minimum or maximum of a function or a set of functions on a given set. It is usually described as a minimization problem because the maximization of the real-valued function ${\displaystyle g(x)}$ is equivalent to the minimization of the function ${\displaystyle f(x):=(-1)\cdot g(x)}$.

Given a possibly nonlinear and non-convex continuous function ${\displaystyle f:\Omega \subset \mathbb {R} ^{n}\to \mathbb {R} }$ with the global minimum ${\displaystyle f^{*}}$ and the set of all global minimizers ${\displaystyle X^{*}}$ in ${\displaystyle \Omega }$, the standard minimization problem can be given as

${\displaystyle \min _{x\in \Omega }f(x),}$

that is, finding ${\displaystyle f^{*}}$ and a global minimizer in ${\displaystyle X^{*}}$; where ${\displaystyle \Omega }$ is a (not necessarily convex) compact set defined by inequalities ${\displaystyle g_{i}(x)\geqslant 0,i=1,\ldots ,r}$.

Global optimization is distinguished from local optimization by its focus on finding the minimum or maximum over the given set, as opposed to finding local minima or maxima. Finding an arbitrary local minimum is relatively straightforward by using classical local optimization methods. Finding the global minimum of a function is far more difficult: analytical methods are frequently not applicable, and the use of numerical solution strategies often leads to very hard challenges.

Applications

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 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, biology, economics, finance, medicine, astronomy, engineering.
• IMRT radiation therapy planning

Deterministic methods

The most successful general exact strategies are:

Stochastic methods

Several exact or inexact Monte-Carlo-based algorithms exist:

Heuristics and metaheuristics

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

• Ant colony optimization (ACO)
• Simulated annealing, a generic probabilistic metaheuristic
• Tabu search, an extension of local search capable of escaping from local minima
• Evolutionary algorithms (e.g., genetic algorithms and evolution strategies)
• Differential evolution, a method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality
• Swarm-based optimization algorithms (e.g., particle swarm optimization, social cognitive 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)
• Graduated optimization, a technique that attempts to solve a difficult optimization problem by initially solving a greatly simplified problem, and progressively transforming that problem (while optimizing) until it is equivalent to the difficult optimization problem.^[6][7][8]

Response surface methodology-based approaches

• IOSO Indirect Optimization based on Self-Organization
• Bayesian optimization, a sequential design strategy for global optimization of black-box functions using Bayesian statistics^[9]

See also

• Deterministic global optimization
• Multidisciplinary design optimization
• Multiobjective optimization
• Optimization (mathematics)

Footnotes

References

External links

• A. Neumaier’s page on Global Optimization
• Introduction to global optimization by L. Liberti
• Free e-book by Thomas Weise