Editing Global optimization

{{Short description|Branch of mathematics}}
{{more footnotes needed|date=December 2013}}

'''Global optimization''' is a branch of [[operations research]], [[applied mathematics]], and [[numerical analysis]] that attempts to find the global [[maximum and minimum|minimum or maximum]] of a function or a set of functions on a given set. It is usually described as a minimization problem because the maximization of the real-valued function <math>g(x)</math> is equivalent to the minimization of the function <math>f(x):=(-1)\cdot g(x)</math>.

Given a possibly nonlinear and non-convex continuous function <math>f:\Omega\subset\mathbb{R}^n\to\mathbb{R}</math> with the global minimum <math>f^*</math> and the set of all global minimizers <math>X^*</math> in <math>\Omega</math>, the standard minimization problem can be given as 
:<math>\min_{x\in\Omega}f(x),</math>
that is, finding <math>f^*</math> and a global minimizer in <math>X^*</math>; where <math>\Omega</math> is a (not necessarily convex) compact set defined by inequalities <math>g_i(x)\geqslant0, i=1,\ldots,r</math>.

Global optimization is distinguished from local optimization by its focus on finding the minimum or maximum over the given set, as opposed to finding ''local'' minima or maxima. Finding an arbitrary local minimum is relatively straightforward by using classical ''local optimization'' methods. Finding the global minimum of a function is far more difficult: analytical methods are frequently not applicable, and the use of numerical solution strategies often leads to very hard challenges.

== Applications ==
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|Gibbs energy]])
* Safety verification, [[safety engineering]] (e.g., of mechanical structures, buildings)
* [[Worst case|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 glass]]es
* 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, biology, economics, finance, medicine, astronomy, engineering.
*[[Radiation therapy#Intensity-modulated radiation therapy (IMRT)|IMRT]] radiation therapy planning

== Deterministic methods ==
{{main|Deterministic global optimization}}
The most successful general exact strategies are:

===Inner and outer approximation===
In both of these strategies, the set over which a function is to be optimized is approximated by polyhedra. In inner approximation, the polyhedra are contained in the set, while in outer approximation, the polyhedra contain the set.

===Cutting-plane methods===
{{main|Cutting plane}}
The '''cutting-plane method''' is an umbrella term for optimization methods which iteratively refine a [[feasible set]] or objective function by means of linear inequalities, termed ''cuts''.  Such procedures are popularly used to find [[integer]] solutions to [[mixed integer linear programming]] (MILP) problems, as well as to solve general, not necessarily differentiable [[convex optimization]] problems.  The use of cutting planes to solve MILP was introduced by [[Ralph E. Gomory]] and [[Václav Chvátal]].

===Branch and bound methods===
{{main|Branch and bound}}
'''Branch and bound''' ('''BB''' or '''B&B''') is an [[algorithm]] design paradigm for [[discrete optimization|discrete]] and [[combinatorial optimization]] problems. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of [[state space search]]: the set of candidate solutions is thought of as forming a [[Tree (graph theory)|rooted tree]] with the full set at the root. The algorithm explores ''branches'' of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated ''bounds'' on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.

===Interval methods===
{{main|Interval arithmetic|Set inversion}}
'''Interval arithmetic''', '''interval mathematics''', '''interval analysis''', or '''interval computation''', is a method developed by mathematicians since the 1950s and 1960s as an approach to putting bounds on [[rounding error]]s and [[measurement error]]s in [[numerical analysis|mathematical computation]] and thus developing [[numerical methods]] that yield reliable results. Interval arithmetic helps find reliable and guaranteed solutions to equations and optimization problems.

===Methods based on real algebraic geometry===
{{main|Real algebraic geometry}}
'''Real algebra''' is the part of algebra which is relevant to real algebraic (and semialgebraic) geometry. It is mostly concerned with the study of [[ordered field]]s and [[ordered ring]]s (in particular [[real closed field]]s) and their applications to the study of [[positive polynomial]]s and [[Polynomial SOS|sums-of-squares of polynomials]]. It can be used in [[convex optimization]].

== Stochastic methods ==
{{Main|Stochastic optimization}}

Several exact or inexact Monte-Carlo-based algorithms exist:

===Direct Monte-Carlo sampling===
{{Main|Monte Carlo method}}
In this method, random simulations are used to find an approximate solution.

Example: The [[traveling salesman problem]] is what is called a conventional optimization problem. That is, all the facts (distances between each destination point) needed to determine the optimal path to follow are known with certainty and the goal is to run through the possible travel choices to come up with the one with the lowest total distance. However, let's assume that instead of wanting to minimize the total distance traveled to visit each desired destination, we wanted to minimize the total time needed to reach each destination. This goes beyond conventional optimization since travel time is inherently uncertain (traffic jams, time of day, etc.). As a result, to determine our optimal path we would want to use simulation - optimization to first understand the range of potential times it could take to go from one point to another (represented by a probability distribution in this case rather than a specific distance) and then optimize our travel decisions to identify the best path to follow taking that uncertainty into account.

===Stochastic tunneling===
{{Main|Stochastic tunneling}}
'''Stochastic tunneling''' (STUN) is an approach to global optimization based on the [[Monte Carlo method]]-[[Sampling (signal processing)|sampling]] of the function to be objectively minimized in which the function is nonlinearly transformed to allow for easier tunneling among regions containing function minima. Easier tunneling allows for faster exploration of sample space and faster convergence to a good solution.

===Parallel tempering===
{{main|Parallel tempering}}
'''Parallel 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]] (MCMC) sampling methods more generally.  The replica exchange method was originally devised by Swendsen,<ref>Swendsen RH and Wang JS (1986) [https://www.researchgate.net/profile/Robert_Swendsen/publication/13255490_Replica_Monte_Carlo_Simulation_of_Spin-Glasses/links/0046352309b5f54715000000.pdf Replica Monte Carlo simulation of spin glasses] Physical Review Letters 57 : 2607–2609</ref> then extended by Geyer<ref>C. J. Geyer, (1991) in ''Computing Science and Statistics'', Proceedings of the 23rd Symposium on the Interface, American Statistical Association, New York, p. 156.</ref> and later developed, among others, by [[Giorgio Parisi]].,<ref>{{cite journal
 |author = Marco Falcioni and Michael W. Deem
 |year=1999
 |title = A Biased Monte Carlo Scheme for Zeolite Structure Solution
 |journal = J. Chem. Phys.
 |volume = 110 |issue = 3 |pages = 1754–1766
 |doi=10.1063/1.477812
|arxiv = cond-mat/9809085|bibcode = 1999JChPh.110.1754F|s2cid=13963102
 }}</ref><ref>David J. Earl and Michael W. Deem (2005) [http://www.rsc.org/Publishing/Journals/CP/article.asp?doi=b509983h "Parallel tempering: Theory, applications, and new perspectives"],  ''Phys. Chem. Chem. Phys.'',  7, 3910</ref>
Sugita and Okamoto formulated a [[molecular dynamics]] version of parallel tempering:<ref>{{cite journal
 |author = Y. Sugita and Y. Okamoto
 |year=1999
 |title = Replica-exchange molecular dynamics method for protein folding
 |journal = Chemical Physics Letters
 |volume = 314 |issue=1–2
 |pages = 141–151
 |doi=10.1016/S0009-2614(99)01123-9
|bibcode=1999CPL...314..141S}}</ref> this is usually known as replica-exchange molecular dynamics or REMD.

Essentially, one runs ''N'' copies of the system, randomly initialized, at different temperatures. Then, based on the Metropolis criterion  one exchanges configurations at different temperatures. The idea of this method
is to make configurations at high temperatures available to the simulations at low temperatures and vice versa.
This results in a very robust ensemble which is able to sample both low and high energy configurations.
In this way, thermodynamical properties such as the specific heat, which is in general not well computed in the canonical ensemble, can be computed with great precision.

==Heuristics and metaheuristics ==
{{main|Metaheuristic}}

Other approaches include heuristic strategies to search the search space in a more or less intelligent way, including:
* [[Ant colony optimization algorithms|Ant colony optimization]] (ACO)
* [[Simulated annealing]], a generic probabilistic metaheuristic
* [[Tabu search]], an extension of [[Local search (optimization)|local search]] capable of escaping from local minima
* [[Evolutionary algorithm]]s (e.g., [[genetic algorithms]] and [[evolution strategies]])
* [[Differential evolution]], a method that [[optimization (mathematics)|optimizes]] a problem by [[iterative method|iteratively]] trying to improve a [[candidate solution]] with regard to a given measure of quality
* [[Swarm intelligence|Swarm-based optimization algorithms]] (e.g., [[particle swarm optimization]], [[social cognitive optimization]], [[multi-swarm optimization]] and [[ant colony optimization]])
* [[Memetic algorithm]]s, combining global and local search strategies
* Reactive search optimization (i.e. integration of sub-symbolic machine learning techniques into search heuristics)
* [[Graduated optimization]], a technique that attempts to solve a difficult optimization problem by initially solving a greatly simplified problem, and progressively transforming that problem (while optimizing) until it is equivalent to the difficult optimization problem.<ref>{{cite book |first1=Neil |last1=Thacker |first2=Tim |last2=Cootes |chapter-url=http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/BMVA96Tut/node29.html |chapter=Graduated Non-Convexity and Multi-Resolution Optimization Methods |title=Vision Through Optimization |year=1996}}</ref><ref>{{cite book |first1=Andrew |last1=Blake |first2=Andrew |last2=Zisserman |url=http://research.microsoft.com/en-us/um/people/ablake/papers/VisualReconstruction/ |title=Visual Reconstruction |publisher=MIT Press |year=1987 |isbn=0-262-02271-0}}{{page needed|date=October 2011}}</ref><ref name="mobahi2015">Hossein Mobahi, John W. Fisher III. 
[http://people.csail.mit.edu/hmobahi/pubs/gaussian_convenv_2015.pdf On the Link Between Gaussian Homotopy Continuation and Convex Envelopes], In Lecture Notes in Computer Science (EMMCVPR 2015), Springer, 2015.</ref>

== Response surface methodology-based approaches ==
* [[IOSO]] Indirect Optimization based on Self-Organization
* [[Bayesian optimization]], a sequential design strategy for global [[optimization]] of black-box functions using [[Bayesian statistics]]<ref>Jonas Mockus (2013). [https://books.google.com/books?id=VuKoCAAAQBAJ&dq=%22Bayesian+approach+to+global+optimization%3A+theory+and+applications%22&pg=PR11 Bayesian approach to global optimization: theory and applications]. Kluwer Academic.</ref>

==See also==
* [[Deterministic global optimization]]
* [[Multidisciplinary design optimization]]
* [[Multiobjective optimization]]
* [[Optimization (mathematics)]]

==Footnotes==
{{reflist}}

== References ==
{{refbegin}}
Deterministic global optimization:
* R. Horst, H. Tuy, [https://books.google.com/books?id=Pe_1CAAAQBAJ&dq=%22Global+Optimization%3A+Deterministic+Approaches%22&pg=PA2 Global Optimization: Deterministic Approaches], Springer, 1996.
* R. Horst, [[Panos M. Pardalos|P.M. Pardalos]] and N.V. Thoai, [https://books.google.com/books?id=dbu02-1JbLIC&dq=%22Introduction+to+Global+Optimization%22&pg=PR11 Introduction to Global Optimization], Second Edition.  Kluwer Academic Publishers, 2000.
*[https://www.mat.univie.ac.at/~neum/ms/glopt03.pdf 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, [https://www.tandfonline.com/doi/abs/10.1080/10556780008805783 Comparison of public-domain software for black box global optimization]. Optimization Methods & Software 13(3), pp.&nbsp;203–226, 2000.
* J.D. Pintér, [https://books.google.com/books?id=uv7lBwAAQBAJ&dq=%22+Continuous+and+Lipschitz+Optimization%22&pg=PR18 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:
* {{cite journal | last1=Kirkpatrick | first1=S. | last2=Gelatt | first2=C. D. | last3=Vecchi | first3=M. P. | title=Optimization by Simulated Annealing | journal=Science | publisher=American Association for the Advancement of Science (AAAS) | volume=220 | issue=4598 | date=1983-05-13 | issn=0036-8075 | doi=10.1126/science.220.4598.671 | pmid=17813860 | pages=671–680| bibcode=1983Sci...220..671K | s2cid=205939 }}
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:
* [[Anatoly Zhigljavsky|A. Zhigljavsky]].  Theory of Global Random Search.  Mathematics and its applications. Kluwer Academic Publishers. 1991.
* {{cite journal | last=Hamacher | first=K | title=Adaptation in stochastic tunneling global optimization of complex potential energy landscapes | journal=Europhysics Letters | publisher=IOP Publishing | volume=74 | issue=6 | year=2006 | issn=0295-5075 | doi=10.1209/epl/i2006-10058-0 | pages=944–950| bibcode=2006EL.....74..944H | s2cid=250761754 }}
* {{cite journal | last1=Hamacher | first1=K. | last2=Wenzel | first2=W. | title=Scaling behavior of stochastic minimization algorithms in a perfect funnel landscape | journal=Physical Review E | volume=59 | issue=1 | date=1999-01-01 | issn=1063-651X | doi=10.1103/physreve.59.938 | pages=938–941|arxiv=physics/9810035| bibcode=1999PhRvE..59..938H | s2cid=119096368 }}
* {{cite journal | last1=Wenzel | first1=W. | last2=Hamacher | first2=K. | title=Stochastic Tunneling Approach for Global Minimization of Complex Potential Energy Landscapes | journal=Physical Review Letters | publisher=American Physical Society (APS) | volume=82 | issue=15 | date=1999-04-12 | issn=0031-9007 | doi=10.1103/physrevlett.82.3003 | pages=3003–3007|arxiv=physics/9903008| bibcode=1999PhRvL..82.3003W | s2cid=5113626 }}
For parallel tempering:
* {{cite journal | last=Hansmann | first=Ulrich H.E. | title=Parallel tempering algorithm for conformational studies of biological molecules | journal=Chemical Physics Letters | publisher=Elsevier BV | volume=281 | issue=1–3 | year=1997 | issn=0009-2614 | doi=10.1016/s0009-2614(97)01198-6 | arxiv=physics/9710041 | pages=140–150| bibcode=1997CPL...281..140H | s2cid=14137470 }}
For continuation methods:
* Zhijun Wu.  [https://www.osti.gov/servlets/purl/395617 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:
* {{cite journal | last=Hamacher | first=Kay | title=On stochastic global optimization of one-dimensional functions | journal=Physica A: Statistical Mechanics and Its Applications | publisher=Elsevier BV | volume=354 | year=2005 | issn=0378-4371 | doi=10.1016/j.physa.2005.02.028 | pages=547–557| bibcode=2005PhyA..354..547H }}
For strategies allowing one to compare deterministic and stochastic global optimization methods
{{refend}}

== External links ==
*[https://arnold-neumaier.at/glopt.html A. Neumaier’s page on Global Optimization]
*[http://www.lix.polytechnique.fr/~liberti/teaching/dix/inf572-09/nonconvex_optimization.pdf Introduction to global optimization by L. Liberti]
*[https://archive.org/download/Thomas_Weise__Global_Optimization_Algorithms_Theory_and_Application/book.pdf Free e-book by Thomas Weise]
{{Industrial and applied mathematics}}
{{Mathematical optimization software}}
{{Authority control}}

[[Category:Deterministic global optimization]]