Global optimization
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.
of one real
-valued function
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
can be regarded as the minimization of the transformed function 
.
Several Monte-Carlo-based algorithms exist:
Other approaches include heuristic strategies to search the search space in a (more or less) intelligent way, including:
2. Commercial:
Applied mathematics
Applied mathematics is a branch of mathematics that concerns itself with mathematical methods that are typically used in science, engineering, business, and industry. Thus, "applied mathematics" is a mathematical science with specialized knowledge...
and numerical analysis
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
that deals with the optimization
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
of a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
or a set of functions to some criteria.
General
The most common form is the minimizationMaxima and minima
In mathematics, the maximum and minimum of a function, known collectively as extrema , are the largest and smallest value that the function takes at a point either within a given neighborhood or on the function domain in its entirety .More generally, the...
of one real
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
-valued function
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
can be regarded as the minimization of the transformed function .Applications of global optimization
Typical examples of global optimization applications include:- Protein structure predictionProtein structure predictionProtein structure prediction is the prediction of the three-dimensional structure of a protein from its amino acid sequence — that is, the prediction of its secondary, tertiary, and quaternary structure from its primary structure. Structure prediction is fundamentally different from the inverse...
(minimize the energy/free energy function) - Computational phylogeneticsComputational phylogeneticsComputational phylogenetics is the application of computational algorithms, methods and programs to phylogenetic analyses. The goal is to assemble a phylogenetic tree representing a hypothesis about the evolutionary ancestry of a set of genes, species, or other taxa...
(e.g., minimize the number of character transformations in the tree) - Traveling salesman problem and circuit design (minimize the path length)
- Chemical engineeringChemical engineeringChemical engineering is the branch of engineering that deals with physical science , and life sciences with mathematics and economics, to the process of converting raw materials or chemicals into more useful or valuable forms...
(e.g., analyzing the Gibbs free energyGibbs free energyIn thermodynamics, the Gibbs free energy is a thermodynamic potential that measures the "useful" or process-initiating work obtainable from a thermodynamic system at a constant temperature and pressure...
) - Safety verification, safety engineeringSafety engineeringSafety engineering is an applied science strongly related to systems engineering / industrial engineering and the subset System Safety Engineering...
(e.g., of mechanical structures, buildings) - Worst case analysisWorst CaseWorst Case is the 3rd book in the Michael Bennett series from James Patterson and Michael Ledwidge.-Plot summary:NYPD Detective Mike Bennett and his new partner FBI Special Agent Emily Parker are on the trail of Francis Mooney, a Manhattan trusts and estates lawyer with terminal lung cancer...
- Mathematical problems (e.g., the Kepler conjectureKepler conjectureThe Kepler conjecture, named after the 17th-century German astronomer Johannes Kepler, is a mathematical conjecture about sphere packing in three-dimensional Euclidean space. It says that no arrangement of equally sized spheres filling space has a greater average density than that of the cubic...
) - The starting point of several molecular dynamicsMolecular dynamicsMolecular dynamics is a computer simulation of physical movements of atoms and molecules. The atoms and molecules are allowed to interact for a period of time, giving a view of the motion of the atoms...
simulations consists of an initial optimization of the energy of the system to be simulated. - Spin glassSpin glassA spin glass is a magnet with frustrated interactions, augmented by stochastic disorder, where usually ferromagnetic and antiferromagnetic bonds are randomly distributed...
es - Calibration of radio propagation models
- Curve fittingCurve fittingCurve fitting is the process of constructing a curve, or mathematical function, that has the best fit to a series of data points, possibly subject to constraints. Curve fitting can involve either interpolation, where an exact fit to the data is required, or smoothing, in which a "smooth" function...
like Non-linear least squaresNon-linear least squaresNon-linear least squares is the form of least squares analysis which is used to fit a set of m observations with a model that is non-linear in n unknown parameters . It is used in some forms of non-linear regression. The basis of the method is to approximate the model by a linear one and to...
analysis and other generalizations, used in fitting model parameters to experimental data in chemistry, physics, medicine, astronomy, engineering.
Deterministic
The most successful are:- Inner approximation
- Outer approximation
- Cutting methods.
- Branch and boundBranch and boundBranch and bound is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization...
methods - Interval Optimization / Interval Algebra (see interalg from OpenOptOpenOptOpenOpt is an open-source framework for numerical optimization, nonlinear equations and systems of them. It is licensed under the BSD license, making it available to be used in both open- and closed-code software. The package already has some essential ....
, Maple global optimization toolbox, TOMLABTOMLABThe TOMLAB Optimization Environment is a modeling platform for solving applied optimization problems in MATLAB.-Description:TOMLAB is a general purpose development and modeling environment in MATLAB for research, teaching and practical solution of optimization problems...
for Matlab or GlobSol) - Methods based on real algebraic geometryReal algebraic geometryIn mathematics, real algebraic geometry is the study of real algebraic sets, i.e. real-number solutions to algebraic equations with real-number coefficients, and mappings between them ....
Stochastic, thermodynamics
- Main page: Stochastic optimizationStochastic optimizationStochastic optimization methods are optimization methods that generate and use random variables. For stochastic problems, the random variables appear in the formulation of the optimization problem itself, which involve random objective functions or random constraints, for example. Stochastic...
Several Monte-Carlo-based algorithms exist:
- Simulated annealingSimulated annealingSimulated annealing is a generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete...
- Direct Monte-CarloMonte Carlo methodMonte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulations of physical and mathematical systems...
sampling - Basin hopping technique (aka Monte-Carlo with minimization)
- Stochastic tunnelingStochastic tunnelingStochastic tunneling is an approach to global optimization based on the Monte Carlo method-sampling of the function to be minimized.- Idea :...
- Parallel temperingParallel temperingParallel tempering, also known as replica exchange MCMC sampling, is a simulation method aimed at improving the dynamic properties of Monte Carlo method simulations of physical systems, and of Markov chain Monte Carlo sampling methods more generally...
- Continuation methods
Heuristics and metaheuristics
- Main page: MetaheuristicMetaheuristicIn computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Metaheuristics make few or no assumptions about the problem being optimized and can search very large spaces...
Other approaches include heuristic strategies to search the search space in a (more or less) intelligent way, including:
- Evolutionary algorithmEvolutionary algorithmIn artificial intelligence, an evolutionary algorithm is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses some mechanisms inspired by biological evolution: reproduction, mutation, recombination, and selection...
s (e.g., genetic algorithms and evolution strategies) - Swarm-based optimization algorithmsSwarm intelligenceSwarm intelligence is the collective behaviour of decentralized, self-organized systems, natural or artificial. The concept is employed in work on artificial intelligence...
(e.g., particle swarm optimizationParticle swarm optimizationIn computer science, particle swarm optimization is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality...
and ant colony optimizationAnt colony optimizationIn computer science and operations research, the ant colony optimization algorithm ' is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs....
) - Memetic algorithmMemetic algorithmMemetic algorithms represent one of the recent growing areas of research in evolutionary computation. The term MA is now widely used as a synergy of evolutionary or any population-based approach with separate individual learning or local improvement procedures for problem search...
s, combining global and local search strategies - Reactive search optimizationReactive search optimizationReactive search optimization defines local-search heuristics based on machine learning, a family of optimization algorithms based on the local search techniques...
(i.e. integration of sub-symbolic machine learning techniques into search heuristics) - Differential evolutionDifferential evolutionIn computer science, differential evolution is a method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Such methods are commonly known as metaheuristics as they make few or no assumptions about the problem being optimized...
- Graduated optimizationGraduated optimizationGraduated optimization is a global optimization technique that attempts to solve a difficult optimization problem by initially solving a greatly simplified problem, and progressively transforming that problem until it is equivalent to the difficult optimization problem.-Technique...
Response surface methodology based approaches
- Efficient Global Optimization
- IOSOIOSOIOSO is a multiobjective, multidimensional nonlinear optimization technology.-IOSO approach:IOSO Technology is based on the response surface methodology approach....
Indirect Optimization based on Self-Organization
Global optimization software
1. Free and opensource:| Name | Source code language |
License | Brief info |
|---|---|---|---|
| NLopt | C | LGPL | free/open-source optimization library with several global optimization algorithms |
| EvA2 | Java | LGPL | an extensive open-source Java framework for global optimization |
| OpenOpt OpenOpt OpenOpt is an open-source framework for numerical optimization, nonlinear equations and systems of them. It is licensed under the BSD license, making it available to be used in both open- and closed-code software. The package already has some essential .... |
Python | BSD BSD licenses BSD licenses are a family of permissive free software licenses. The original license was used for the Berkeley Software Distribution , a Unix-like operating system after which it is named.... |
Universal cross-platform numerical optimization framework, see its global optimization page and other problems involved |
| PSwarm | C | LGPL | a global optimization solver for bound and linear constrained problems |
2. Commercial:
See also
- Multidisciplinary design optimizationMultidisciplinary design optimizationMulti-disciplinary design optimization is a field of engineering that uses optimization methods to solve design problems incorporating a number of disciplines. As defined by Prof. Carlo Poloni, MDO is "the art of finding the best compromise"...
- Multiobjective optimizationMultiobjective optimizationMulti-objective optimization , also known as multi-criteria or multi-attribute optimization, is the process of simultaneously optimizing two or more conflicting objectives subject to certain constraints....
- Optimization (mathematics)Optimization (mathematics)In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....