Separation oracle

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

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

Suppose the set of vertices of K is given as an input, so that ${\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 z₁,...,z_k such that: [1]^: 49

• ${\displaystyle z_{1}\cdot v_{1}+\cdots +z_{k}\cdot v_{k}=y}$;
• ${\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

• ${\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).

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:

• 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.[3]
• 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, which can be done in polynomial time.[3]
• The dual of the configuration linear program for the bin packing problem. It can be approximated by an LP with a constraint for each feasible configuration. While there are exponentially-many such cycles, a separation oracle that works in pseudopolynomial time can be implemented by solving a knapsack problem. This is used by the Karmarkar-Karp bin packing algorithms.

Let f be a convex function on Rⁿ. The set ${\displaystyle K=\{(x,t)|f(x)\leq t\}}$ is a convex set in Rⁿ⁺¹. 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.[1]^: 49 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ⁿ). Denote ${\displaystyle c:=(g,-1)}$.Then, ${\displaystyle c\cdot (y,s)=g\cdot y-s>g\cdot y-f(y)}$, and for all (x, t) in K: ${\displaystyle c\cdot (x,t)=g\cdot x-t\leq g\cdot x-f(x)}$. By definition of a subgradient: ${\displaystyle f(x)\geq f(y)+g\cdot (x-y)}$ for all x in Rⁿ. Therefore, ${\displaystyle g\cdot y-f(y)\geq g\cdot x-f(x)}$, so ${\displaystyle c\cdot (y,s)>c\cdot (x,t)}$ , and c represents a separating hyperplane.

A membership oracle is a weaker variant of the separation oracle, which does not require the separating hyperplane.

Formally, a strong membership oracle for K is an oracle that, given a vector y in Rⁿ, returns one of the following:

• Assert that y is in K.
• Assert that y is in not in K.

Obviously, a strong separation oracle implies a strong membership oracle.

A weak membership oracle for K is an oracle that, given a vector y in Qⁿ and a rational number d>0, returns one of the following:

• Assert that y is d-near K;
• Assert that y is not d-deep in K.

Using a weak separation oracle (WSO), one can construct a weak membership oracle as follows.

• Run WSO(K,y,d). If it returns "yes", then return "yes".
• Otherwise, run WSO(K,y,d/3). If it returns "yes", then return "yes".
• Otherwise, return "no"; see [1]^: 52 for proof of correctness.

An optimization oracle is an oracle which finds an optimal point in a given convex set.

Formally, a strong optimization oracle for K is an oracle that, given a vector c in Rⁿ, returns one of the following:

• Assert that K is empty.
• Find a vector y in K that maximizes ${\displaystyle c\cdot y}$ (that is, ${\displaystyle c\cdot y\geq c\cdot x}$. for all x in K).

A weak optimization oracle for K is an oracle that, given a vector c in Qⁿ and a rational number d>0, returns one of the following:

• Assert that no point is d-deep in K;
• Find a vector y that is d-near K, such that ${\displaystyle c\cdot y+d\geq c\cdot x}$ for all x that are d-deep in K.

A strong violation oracle for K is an oracle that, given a vector c in Rⁿ and a real number r, returns one of the following:

• Assert that ${\displaystyle c\cdot x\leq r}$ for all x in K;
• Find a vector y in K with ${\displaystyle c\cdot y>r}$.

A weak violation oracle for K is an oracle that, given a vector c in Qⁿ, a rational number r, and a rational number d>0, returns one of the following:

• Assert that ${\displaystyle c\cdot x\leq r+d}$ for all x that are d-deep in K;
• Find a vector y that is d-near K, such that ${\displaystyle c\cdot y+d\geq r}$.

A major result in convex optimization is that, for any "well-described" polyhedron, the strong-separation problem, the strong-optimization problem and the strong-violation problem are equivalent

A major result in convex optimization is that, for any "well-described" polyhedron, the strong-separation problem, the strong-optimization problem and the strong-violation problem are polynomial-time-equivalent. That is, given an oracle for any one of these three problems, the other two problems can be solved in polynomial time.[1]^: 158 A polyhedron is called "well-described" if the input contains n (the number of dimensions of the space it lies in), and contains a number p such K can be defined by linear inequalities with encoding-length at most p.[1]^: 163 The result is proved using the ellipsoid method.