Global optimization is a branch of operations research, applied mathematics, and numerical analysis that attempts to find the global 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 g ( x ) {\displaystyle g(x)} is equivalent to the minimization of the function f ( x ) := ( − 1 ) ⋅ g ( x ) {\displaystyle f(x):=(-1)\cdot g(x)} . Given a possibly nonlinear and non-convex continuous function f : Ω ⊂ R n → R {\displaystyle f:\Omega \subset \mathbb {R} ^{n}\to \mathbb {R} } with the global minimum f ∗ {\displaystyle f^{*}} and the set of all global minimizers X ∗ {\displaystyle X^{*}} in Ω {\displaystyle \Omega } , the standard minimization problem can be given as
min x ∈ Ω f ( x ) , {\displaystyle \min _{x\in \Omega }f(x),}
that is, finding f ∗ {\displaystyle f^{*}} and a global minimizer in X ∗ {\displaystyle X^{*}} ; where Ω {\displaystyle \Omega } is a (not necessarily convex) compact set defined by inequalities g i ( x ) ⩾ 0 , i = 1 , … , r {\displaystyle g_{i}(x)\geqslant 0,i=1,\ldots ,r} . 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 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, biology, economics, finance, medicine, astronomy, engineering. IMRT radiation therapy planning
Deterministic methods
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
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
Branch and bound (BB or B&B) is an algorithm design paradigm for 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 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
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 errors and measurement errors in 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
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 fields and ordered rings (in particular real closed fields) and their applications to the study of positive polynomials and sums-of-squares of polynomials. It can be used in convex optimization.
Stochastic methods
Several exact or inexact Monte-Carlo-based algorithms exist:
Direct Monte-Carlo sampling
… excerpt ends here. Continue reading the full article.
