Separation oracle

A separation 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 in linear programming

In the context of linear programming, the constraints are all linear, and K is a convex polytope. It can be represented by $K=\{x|Ax\leq b\}$, where A is an m by n matrix and b is an m-length vector (m is the number of constraints and n is the number of variables). Given this representation, the separation oracle can be easily implemented as follows. Given a point y, just computes $Ay$:

• If the outcome is at most $b$, then y is in K;
• 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. 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.