Global optimization is a branch of applied mathematics and numerical analysis that deals with the optimization of a function or a set of functions to some criteria.

General

---

The most common form is the minimization of one real-valued function $f$ in the parameter-space $\backslash vec\{x\}\backslash in\; P$. There may be several constraints on the solution vectors $\backslash vec\{x\}\_\{min\}$.

In real-life problems, functions of many variables have a large number of local minima and maxima. Finding an arbitrary local optimum is relatively straightforward by using local optimisation methods. Finding the global maximum or minimum of a function is a lot more challenging and has been impossible for many problems so far.

The maximization of a real-valued function $g(x)$ can be regarded as the minimization of the transformed function $f(x):=(-1)\backslash cdot\; g(x)$.

Applications of global optimization

---

Typical examples of global optimization applications include:

• Protein structure prediction (minimize the energy/free energy function)
• Traveling salesman problem and 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)
• The starting point of several molecular dynamics simulations consists of an initial optimization of the energy of the system to be simulated.
• Spin glasses

Approaches

---

Deterministic

The most successful are:

• Branch and bound methods
• Methods based on real algebraic geometry

Stochastic, thermodynamics

Several Monte-Carlo-based algorithms exist:

• Simulated annealing
• Direct Monte-Carlo sampling
• Stochastic tunneling
• Parallel tempering
• Monte-Carlo with minimization

Heuristics and metaheuristics

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

• Evolutionary algorithms (e.g., genetic algorithms)
• Swarm-based optimization algorithms (e.g., particle swarm optimization and ant colony optimization)
• Memetic algorithms, combining global and local search strategies

See also

---

• multidisciplinary design optimization

References

---

Deterministic global optimization:

• R. Horst, P.M. Pardalos and N.V. Thoai, Introduction to Global Optimization, Second Edition. Kluwer Academic Publishers, 2000.

• A.Neumaier, Complete Search in Continuous Global Optimization and Constraint Satisfaction, pp. 271-369 in: Acta Numerica 2004 (A. Iserles, ed.), Cambridge University Press 2004.

For simulated annealing:

• S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi. Science, 220:671–680, 1983.

For stochastic tunneling:

• K. Hamacher and W. Wenzel. The Scaling Behaviour of Stochastic Minimization Algorithms in a Perfect Funnel Landscape. Phys. Rev. E, 59(1):938-941, 1999.
• W. Wenzel and K. Hamacher. A Stochastic tunneling approach for global minimization. Phys. Rev. Lett., 82(15):3003-3007, 1999.

For parallel tempering:

• U. H. E. Hansmann. Chem.Phys.Lett., 281:140, 1997.

External links

---

• A. Neumaier’s page on Global Optimization

Optimization