This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(December 2013) (Learn how and when to remove this message)

Global optimization is a branch ofoperations research,applied mathematics, andnumerical analysis that attempts to find the globalminimum 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${\displaystyle g(x)}$ is equivalent to the minimization of the function${\displaystyle f(x):=(-1)\cdot g(x)}$.

Given a possibly nonlinear and non-convex continuous function${\displaystyle f:\mathrm{\Omega }\subset {\mathbb{R}}^n\to \mathbb{R}}$ with the global minimum${\displaystyle f^{\ast }}$ and the set of all global minimizers${\displaystyle X^{\ast }}$ in${\displaystyle \mathrm{\Omega }}$, the standard minimization problem can be given as

${\displaystyle \underset{x\in \mathrm{\Omega }}{min}f(x),}$

that is, finding${\displaystyle f^{\ast }}$ and a global minimizer in${\displaystyle X^{\ast }}$; where${\displaystyle \mathrm{\Omega }}$ is a (not necessarily convex) compact set defined by inequalities${\displaystyle g_i(x)⩾0,i=1,\dots ,r}$.

Global optimization is distinguished from local optimization by its focus on finding the minimum or maximum over the given set, as opposed to findinglocal minima or maxima. Finding an arbitrary local minimum is relatively straightforward by using classicallocal 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.

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 theGibbs energy)
• Safety verification,safety engineering (e.g., of mechanical structures, buildings)
• Worst-case analysis
• Mathematical problems (e.g., theKepler conjecture)
• Object packing (configuration design) problems
• The starting point of severalmolecular dynamics simulations consists of an initial optimization of the energy of the system to be simulated.
• Spin glasses
• Calibration ofradio propagation models and of many other models in the sciences and engineering
• Curve fitting likenon-linear least squares analysis and other generalizations, used in fitting model parameters to experimental data in chemistry, physics, biology, economics, finance, medicine, astronomy, engineering.
• IMRT radiation therapy planning

The most successful general exact strategies are:

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.

Thecutting-plane method is an umbrella term for optimization methods which iteratively refine afeasible set or objective function by means of linear inequalities, termedcuts. Such procedures are popularly used to findinteger solutions tomixed integer linear programming (MILP) problems, as well as to solve general, not necessarily differentiableconvex optimization problems. The use of cutting planes to solve MILP was introduced byRalph E. Gomory andVáclav Chvátal.

Branch and bound (BB orB&B) is analgorithm design paradigm fordiscrete andcombinatorial optimization problems. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means ofstate space search: the set of candidate solutions is thought of as forming arooted tree with the full set at the root. The algorithm exploresbranches 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 estimatedbounds 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 arithmetic,interval mathematics,interval analysis, orinterval computation, is a method developed by mathematicians since the 1950s and 1960s as an approach to putting bounds onrounding errors andmeasurement errors inmathematical computation and thus developingnumerical methods that yield reliable results. Interval arithmetic helps find reliable and guaranteed solutions to equations and optimization problems.

Real algebra is the part of algebra which is relevant to real algebraic (and semialgebraic) geometry. It is mostly concerned with the study ofordered fields andordered rings (in particularreal closed fields) and their applications to the study ofpositive polynomials andsums-of-squares of polynomials. It can be used inconvex optimization.

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

In this method, random simulations are used to find an approximate solution.

Example: Thetraveling 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 (STUN) is an approach to global optimization based on theMonte Carlo method-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, also known asreplica exchange MCMC sampling, is asimulation method aimed at improving the dynamic properties ofMonte Carlo method simulations of physical systems, and ofMarkov chain Monte Carlo (MCMC) sampling methods more generally. The replica exchange method was originally devised by Swendsen,^[1] then extended by Geyer^[2] and later developed, among others, byGiorgio Parisi.,^[3][4]Sugita and Okamoto formulated amolecular dynamics version of parallel tempering:^[5] this is usually known as replica-exchange molecular dynamics or REMD.

Essentially, one runsN 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 methodis 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.

Other approaches include heuristic strategies to search the search space in a more or less intelligent way, including:

• Ant colony optimization (ACO)
• Simulated annealing, a generic probabilistic metaheuristic
• Tabu search, an extension oflocal search capable of escaping from local minima
• Evolutionary algorithms (e.g.,genetic algorithms andevolution strategies)
• Differential evolution, a method thatoptimizes a problem byiteratively trying to improve acandidate solution with regard to a given measure of quality
• Swarm-based optimization algorithms (e.g.,particle swarm optimization,social cognitive optimization,multi-swarm optimization andant 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)
• 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.^[6][7][8]

• IOSO Indirect Optimization based on Self-Organization
• Bayesian optimization, a sequential design strategy for globaloptimization of black-box functions usingBayesian statistics^[9]

• Deterministic global optimization
• Multidisciplinary design optimization
• Multiobjective optimization
• Optimization (mathematics)

• A. Neumaier’s page on Global Optimization
• Introduction to global optimization by L. Liberti
• Free e-book by Thomas Weise

• Deterministic global optimization

• Wikipedia articles needing page number citations from October 2011
• Articles with short description
• Short description matches Wikidata
• Articles lacking in-text citations from December 2013
• All articles lacking in-text citations