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^{T}y>c^{T}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^{T}y+d\geq c^{T}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).