Suppose I want to minimize a linear function $f$ over a convex set $K$ and I have only access to a separation oracle, that is, given a point, the oracle returns 'yes' if the point is in $K$ and otherwise returns a hyperplane separating the point from the set. How can I use this to minimize $f$ in polynomial time?
I have read about cutting plane methods that return a point in the set unless the volume if the set is very small. But I don't see how it will help to get the minimizer of $f$.
You may be looking for the Ellipsoid method. This method allows one to optimize a linear function over a convex set via a separation oracle. The method can solve these problems with running time polynomial in the size of the input. Khachiyan applied this notably to linear programming. It has also been used in combinatorial optimization.