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. Applied mathematics is a branch of mathematics that concerns itself with the mathematical techniques typically used in the application of mathematical knowledge to other domains. ... Numerical analysis is the study of algorithms for the problems of continuous mathematics (as distinguished from discrete mathematics). ... In mathematics, the term optimization refers to the study of problems that have the form Given: a function f : A R from some set A to the real numbers Sought: an element x0 in A such that f(x0) ≤ f(x) for all x in A (minimization) or such that... Partial plot of a function f. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ...

General

The most common form is the minimization of one real-valued function f in the parameter-space . There may be several constraints on the solution vectors . A graph illustrating local min/max and global min/max points In mathematics, maxima and minima, also known as extrema, are points in the domain of a function at which the function takes the largest (maximum), or smallest (minimum) value either within a given neighbourhood (local extrema), or on the... In mathematics, the real numbers are intuitively defined as numbers that are in one-to-one correspondence with the points on an infinite line—the number line. ...

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 .

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

Protein structure prediction is one of the most significant technologies pursued by computational structural biology and theoretical chemistry. ... The traveling salesman problem (TSP), is a problem in discrete or combinatorial optimization. ... Chemical engineering is the application of science, in particular chemistry, physics and mathematics, to the process of converting raw materials or chemicals into more useful or valuable forms. ... In thermodynamics, the Gibbs free energy is the energy portion of a thermodynamic system available to do work. ... Safety engineering is an applied science strongly related to systems engineering. ... In computer science, best and worst cases in a given algorithm express what the resource usage is at least and at most, respectively. ... In mathematics, the Kepler conjecture is a conjecture about sphere packing in three dimensional Euclidean space. ... Molecular dynamics (MD) simulation is a special discipline of molecular modelling. ... A spin glass is a disordered material exhibiting high magnetic frustration. ...

Approaches

Deterministic

The most successful are:

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

Branch and bound is a general algorithmic method for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. ... Algebraic geometry is a branch of mathematics which, as the name suggests, combines abstract algebra, especially commutative algebra, with geometry. ...

Stochastic, thermodynamics

Several Monte-Carlo-based algorithms exist:

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

Simulated annealing (SA) is a generic probabilistic meta-algorithm for the global optimization problem, namely locating a good approximation to the global optimum of a given function in a large search space. ... Monte Carlo methods are a widely used class of computational algorithms for simulating the behavior of various physical and mathematical systems. ... Stochastic tunneling (STUN) is one approach to global optimization among several others and is based on the Monte Carlo method-sampling of the function to be minimized. ... Parallel tempering is a simulation method aimed at improving the dynamic properties of Monte Carlo method simulations. ...

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

A genetic algorithm (GA) is an algorithm used to find approximate solutions to difficult-to-solve problems through application of the principles of evolutionary biology to computer science. ... Particle swarm optimization (PSO) is form of swarm intelligence. ... The ant colony optimization algorithm (ACO), introduced by Moyson and Manderick [MoMa88] and widely developped by Marco Dorigo [CMD91,Dor92,DoSt04], is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. ... Memetic algorithms is a population-based approach for heuristic search in optimization problems. ...

See also

• multidisciplinary design optimization

Multidisciplinary design optimization (MDO) is a field of engineering that uses optimization methods to solve design problems incorporating a number of disciplines. ...

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.

For continuation methods:

• Zhijun Wu. The effective energy transformation scheme as a special continuation approach to global optimization with application to molecular conformation. Technical Report, Argonne National Lab., IL (United States), November 1996.

External links

• A. Neumaier’s page on Global Optimization