Separation oracle

A separation oracle (also called a cutting-plane oracle) is a concept in the matematical theory of convex optimization. It is a method to describe a convex set that is given as an input to an optimization algorithm. It is used to solve optimization problems using the ellipsoid method.

Definition

Let K be a convex and compact set in Rⁿ. A strong separation oracle for K is an oracle (black box) that solves the following problem:

Given a vector y in Rⁿ, return one of the following:

• Assert that y is in K.
• Find a hyperplane that separates y from K: a vector c in Rⁿ, such that $c\cdot y>c\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. It 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 solves the following problem:

Given a vector y in Qⁿ, and a rational number d>0, return one of the following:

• Assert that y is in a sphere of radius d around K (= the Euclidean distance between y and K is at most d);
• Find a vector c in Qⁿ, normalized such that its maximum element is 1, such that $c\cdot y+d\geq c\cdot x$ for all x in a sphere of radius d inside K (= all x with Euclidean distance at least d from the boundary of K).

Separation oracles for linear programming

A special case of a convex set is a set represented by linear inequalities: $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 input.

1. If the matrix A and the vector b are given as input, so that $K=\{x|Ax\leq b\}$, then a strong separation oracle can be implemented as follows. Given a point y, compute $Ay$:

• If the outcome is at most $b$, then y is in K by definition;
• Otherwise, there is at least one row $c$ of A, such that $c\cdot y$ is larger than the corresponding value in $b$; this row $c$ gives us the separating hyperplane, as $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.

2. Suppose the set of vertices of K is given as an input, so that $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 z₁,...,z_k such that:

• $z_{1}\cdot v_{1}+\cdots +z_{k}\cdot v_{k}=y$;
• $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\cdot y>c\cdot v_{i}$ for all i in 1,...,k.

3. 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. Two examples are:

• The minimum-cost arborescence problem: given a weighted directed graph and a vertex r in it, find a subgraph of minimum cost that contains a directed path from r to any other vertex. The problem can be presented as an LP with a constraint for each subset of vertices, which is an exponential number of constraints. However, a separation oracle can be implemented using n-1 applications of the minimum cut procedure.
• The maximum independent set problem. It can be approximated by an LP with a constraint for every odd-length cycle. While there are exponentially-many such cycles, a separation oracle that works in polynomial time can be implemented by just finding an odd cycle of minimum length.