Global optimization is a branch of applied mathematics and numerical analysis that deals with the optimization of a function or a set of functions according to some criteria. Typically, a set of bound and more general constraints is also present, and the decision variables are optimized considering also the constraints.
Contents |
General [edit]
A common (standard) model form is the minimization of one real-valued function 
in the parameter-space 
, or its specified subset 
: here 
denotes the set defined by the constraints.
(The maximization of a real-valued function 
is equivalent to the minimization of the function 
.)
In many nonlinear optimization problems, the objective function has a large number of local minima and maxima. Finding an arbitrary local optimum is relatively straightforward by using classical local optimization methods. Finding the global minimum (or maximum) of a function is far more difficult: symbolic (analytical) methods are frequently not applicable, and the use of numerical solution strategies often leads to very hard challenges.
Applications of global optimization [edit]
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 electrical 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)
- Object packing (configuration design) problems
- 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 and of many other models in the sciences and engineering
- Curve fitting like Non-linear least squares analysis and other generalizations, used in fitting model parameters to experimental data in chemistry, physics, medicine, astronomy, engineering.
Approaches [edit]
Deterministic methods [edit]
The most successful general strategies are:
- Inner approximation
- Outer approximation
- Cutting plane methods
- Branch and bound methods
- Interval methods / Interval algebra (see interalg from OpenOpt and GlobSol) / Interval branch and bound methods.
- Methods based on real algebraic geometry
Stochastic methods [edit]
- Main page: Stochastic optimization
Several Monte-Carlo-based algorithms exist:
- Simulated annealing
- Direct Monte-Carlo sampling
- Stochastic tunneling
- Parallel tempering
Heuristics and metaheuristics [edit]
- 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, Multi-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
Response surface methodology based approaches [edit]
- IOSO Indirect Optimization based on Self-Organization
Global optimization software [edit]
1. Free and opensource:
| Name | Source code language |
License | Brief info |
|---|---|---|---|
| PaGMO/PyGMO | Python,C++ | GPL3 | Numerical optimization framework with emphasis on parallel computing, see the list of algorithms implemented and problems |
| OpenOpt | Python | BSD | Universal cross-platform numerical optimization framework, see its global optimization page and other problems involved |
| OPTI Toolbox | MATLAB | BSD | Free MATLAB Toolbox for solving linear, nonlinear, continuous and discrete optimization problems.
See the OPTI GNLP Examples page for several examples. |
2. Commercial:
- LIONsolver
- TOMLAB for Matlab
- Optimus platform
- The NAG Numerical Library contains routines for both global and local optimization.
- Global Optimization Toolbox for MATLAB
- Demo global optimization software versions are available also for a number of commercial software products.
See also [edit]
References [edit]
Deterministic global optimization:
- R. Horst, H. Tuy, Global Optimization: Deterministic Approaches, Springer, 1996.
- 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.
- J.D. Pintér, Global Optimization in Action - Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications. Kluwer Academic Publishers, Dordrecht, 1996. Now distributed by Springer Science and Business Media, New York. This book also discusses stochastic global optimization methods.
- L. Jaulin, M. Kieffer, O. Didrit, E. Walter (2001). Applied Interval Analysis. Berlin: Springer.
- E.R. Hansen (1992), Global Optimization using Interval Analysis, Marcel Dekker, New York.
For simulated annealing:
- S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi. Science, 220:671–680, 1983.
For reactive search optimization:
- Roberto 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 methods:
- A. Zhigljavsky. Theory of Global Random Search. Mathematics and its applications. Kluwer Academic Publishers. 1991.
- 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.
External links [edit]
- A. Neumaier’s page on Global Optimization
- Introduction to global optimization by L. Liberti
- Global optimization algorithms for MATLAB
- MIDACO-Solver Global optimization software based on evolutionary computing (Matlab,Python, C/C++ and Fortran)
- Free e-book by Thomas Weise
A portion of the proceeds from advertising on Digplanet goes to supporting Wikipedia.
