Editing Global optimization (section)

== 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]].