Global optimization

From Wikipedia, the free encyclopedia

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.

Contents 1 General 2 Applications of global optimization 3 Approaches 3.1 Deterministic 3.2 Stochastic, thermodynamics 3.3 Heuristics and metaheuristics 3.4 Response surface methodology based approaches 4 See also 5 References 6 External links

[edit] 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 .

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 much more challenging and has been practically 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 .

[edit] 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 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
• Calibration of radio propagation models

[edit] Approaches

[edit] Deterministic

The most successful are:

• Interval Optimization / Interval Algebra. (see Maple global optimization toolbox , tomlab for Matlab or GlobSol)
• Branch and bound methods
• Methods based on real algebraic geometry

[edit] Stochastic, thermodynamics

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

[edit] 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 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

[edit] Response surface methodology based approaches

• IOSO Indirect Optimization based on Self-Organization

[edit] See also

• Multidisciplinary design optimization
• Optimization (mathematics)

[edit] 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.

• M. Mongeau, H. Karsenty, V. Rouzé and J.-B. Hiriart-Urruty, Comparison of public-domain software for black box global optimization. Optimization Methods & Software 13(3), pp. 203-226, 2000.

For simulated annealing:

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

For reactive search optimization:

• R. Battiti, M. Brunato and F. Mascia, Reactive Search and Intelligent Optimization, Operations Research/Computer Science Interfaces Series, Vol. 45, Springer, November 2008. ISBN: 978-0-387-09623-0

For stochastic tunneling:

• K. Hamacher. Adaptation in Stochastic Tunneling Global Optimization of Complex Potential Energy Landscapes, Europhys.Lett. 74(6):944, 2006.
• 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.

For general considerations on the dimensionality of the domain of definition of the objective function:

• K. Hamacher. On Stochastic Global Optimization of one-dimensional functions. Physica A 354:547-557, 2005.

[edit] External links

• A. Neumaier’s page on Global Optimization
• Free e-book by Thomas Weise
• Some implementations of global optimization algorithms (SIMPSA, SCA, PSO) in MATLAB
• NLopt - free/open-source optimization library with several global optimization algorithms
• EvA2, an extensive open-source Java framework for global optimization