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.

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 $Q$ is a convex polytope. Then, the separation oracle can be easily implemented as follows. Given the constraints $Q=\{x|Ax\leq b\}$ and a point $x\in \mathbb {R} ^{n}$, the oracle just computes $Ax$:

• If the outcome is at most $b$, then $x$ is in $Q$;
• Otherwise, there is at least one row $c$ of A, such that $c\cdot x$ is larger than the corresponding value in $b$; this row $c$ gives us the separating hyperplane.

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.

The output of the ellipsoid method is either:

• Any point in the polytope $Q$ (i.e., any feasible point), or -
• A proof that $Q$ is empty.

Inequality-constrained minimization of a function that is zero everywhere corresponds to the problem of simply identifying any feasible point. It turns out that any linear programming problem can be reduced to a linear feasibility problem (e.g. minimize the zero function subject to some linear inequality and equality constraints). One way to do this is by combining the primal and dual linear programs together into one program, and adding the additional (linear) constraint that the value of the primal solution is no worse than the value of the dual solution. Another way is to treat the objective of the linear program as an additional constraint, and use binary search to find the optimum value.