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 Rn. A strong separation oracle for K is an oracle (black box) that, given a vector y in Rn, returns one of the following:
Assert that y is in K. Find a hyperplane that separates y from K: a vector a in Rn, such that a ⋅ y > a ⋅ x {\displaystyle a\cdot y>a\cdot x} for all x in K. 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:
A vector y is d-near K if its Euclidean distance from K is at most d; A vector y is d-deep in K if it is in K, and its Euclidean distance from any point in outside K is at least d. 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 Qn and a rational number d>0, returns one of the following:
Assert that y is d-near K; Find a vector a in Qn, normalized such that its maximum element is 1, such that a ⋅ y + d ≥ a ⋅ x {\displaystyle a\cdot y+d\geq a\cdot x} for all x that are d-deep in K.
Implementation A special case of a convex set is a set represented by linear inequalities: K = { x | A x ≤ b } {\displaystyle K=\{x|Ax\leq b\}} . 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 K = { x | A x ≤ b } {\displaystyle K=\{x|Ax\leq b\}} , then a strong separation oracle can be implemented as follows. Given a point y, compute A y {\displaystyle Ay} :
If the outcome is at most b {\displaystyle b} , then y is in K by definition; Otherwise, there is at least one row c {\displaystyle c} of A, such that c ⋅ y {\displaystyle c\cdot y} is larger than the corresponding value in b {\displaystyle b} ; this row c {\displaystyle c} gives us the separating hyperplane, as c ⋅ y > b ≥ c ⋅ x {\displaystyle c\cdot y>b\geq c\cdot x} for all x in K. 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 K = conv ( v 1 , … , v k ) = {\displaystyle K={\text{conv}}(v_{1},\ldots ,v_{k})=} 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 z1,...,zk such that:
z 1 ⋅ v 1 + ⋯ + z k ⋅ v k = y {\displaystyle z_{1}\cdot v_{1}+\cdots +z_{k}\cdot v_{k}=y} ;
0 ≤ z i ≤ 1 {\displaystyle 0\leq z_{i}\leq 1} for all i in 1,...,k. 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
c ⋅ y > c ⋅ v i {\displaystyle c\cdot y>c\cdot v_{i}} for all i in 1,...,k. 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 2n 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:
… excerpt ends here. Continue reading the full article.
