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:^[1]^: 48

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.

References

^ M. Grötschel, L. Lovász, A. Schrijver: Geometric Algorithms and Combinatorial Optimization, Springer, 1988.

[1] M. Grötschel, L. Lovász, A. Schrijver: Geometric Algorithms and Combinatorial Optimization, Springer, 1988.

[1]