Concept in the mathematical theory of convex optimization
A separation oracle (also called a cutting-plane oracle) is a concept in the mathematical theory of convex optimization. It is a method to describe a convex set that is given as an input to an optimization algorithm. Separation oracles are used as input to ellipsoid methods. 
Definition.
Let "K" be a convex and compact set in R"n". A strong separation oracle for "K" is an oracle (black box) that, given a vector "y" in R"n", returns one of the following:
A strong separation oracle is completely accurate, and thus may be hard to construct. For practical reasons, a weaker version is considered, which allows for small errors in the boundary of "K" and the inequalities. Given a small error tolerance "d" ;0, we say that:
The weak version also considers "rational" numbers, which have a representation of finite length, rather than arbitrary real numbers. A weak separation oracle for "K" is an oracle that, given a vector "y" in Q"n" and a rational number "d" ;0, returns one of the following::
Implementation.
A special case of a convex set is a set represented by linear inequalities: "formula_3. "Such a set is called a convex "polytope". A strong separation oracle for a convex polytope can be implemented, but its run-time depends on the input format.
Representation by inequalities.
If the matrix "A" and the vector "b" are given as input, so that "formula_3", then a strong separation oracle can be implemented as follows. Given a point "y", compute "formula_5":
This oracle runs in polynomial time as long as the number of constraints is polynomial. 
Representation by vertices.
Suppose the set of vertices of "K" is given as an input, so that "formula_12" the convex hull of its vertices. Then, deciding whether "y" is in "K" requires to check whether "y" is a convex combination of the input vectors, that is, whether there exist coefficients "z"1...,"zk" such that: 
This is a linear program with "k" variables and "n" equality constraints (one for each element of "y"). If "y" is not in "K", then the above program has no solution, and the separation oracle needs to find a vector "c" such that
Note that the two above representations can be very different in size: it is possible that a polytope can be represented by a small number of inequalities, but has exponentially many vertices (for example, an "n"-dimensional cube). Conversely, it is possible that a polytope has a small number of vertices, but requires exponentially many inequalities (for example, the convex hull of the 2"n" vectors of the form (0...,±1...,0).
Problem-specific representation.
In some linear optimization problems, even though the number of constraints is exponential, one can still write a custom separation oracle that works in polynomial time. Some examples are:
Non-linear sets.
Let "f" be a convex function on R"n". The set "formula_16" is a convex set in R"n"+1. Given an evaluation oracle for "f" (a black box that returns the value of "f" for every given point), one can easily check whether a vector ("y", "t") is in "K". In order to get a separation oracle, we need also an oracle to evaluate the subgradient of "f". Suppose some vector ("y", "s") is not in "K", so "f"("y") ; "s". Let "g" be the subgradient of "f" at "y" ("g" is a vector in R"n")"." Denote "formula_17".Then, "formula_18", and for all ("x", "t") in "K": "formula_19". By definition of a subgradient: "formula_20" for all "x" in R"n". Therefore, "formula_21", so "formula_22 ," and "c" represents a separating hyperplane. 
Usage.
A strong separation oracle can be given as an input to the ellipsoid method for solving a linear program. Consider the linear program "formula_23". The ellipsoid method maintains an ellipsoid that initially contains the entire feasible domain formula_24. At each iteration "t", it takes the center formula_25 of the current ellipsoid, and sends it to the separation oracle:
After making a cut, we construct a new, smaller ellipsoid, that contains the remaining region. It can be shown that this process converges to an approximate solution, in time polynomial in the required accuracy.
Converting a weak oracle to a strong oracle.
Given a weak separation oracle for a "polyhedron", it is possible to construct a strong separation oracle by a careful method of rounding, or by diophantine approximations.
References.
 ;templatestyles src="Reflist/styles.css" / ;