Global optimization
Encyclopedia : G : GL : GLO : 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 to some criteria.
General
The most common form is the minimization of one real-valued function [f] in the parameter-space [\vec\in P]. There may be several constraints on the solution vectors [\vec_].
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)\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
References
Deterministic global optimization:
- R. Horst, P.M. Pardalos and N.V. Thoai, Introduction to Global Optimization, Second Edition. Kluwer Academic Publishers, 2000.
- S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi. Science, 220:671–680, 1983.
- 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.
- U. H. E. Hansmann. Chem.Phys.Lett., 281:140, 1997.
External links
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.