Global optimization
From Free net 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 |
General
The most common form is the minimization of one real-valued function <math>f</math> in the parameter-space <math>\vec{x}\in P</math>. There may be several constraints on the solution vectors <math>\vec{x}_{min}</math>.
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 <math>g(x)</math> can be regarded as the minimization of the transformed function <math>f(x):=(-1)\cdot g(x)</math>.
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.
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.