# Can I solve the separation problem efficiently, when I have access to an optimization oracle?

Assume I have given a convex feasible set $$X$$ and I have an oracle that can optimize some linear objective function $$c$$ over $$X$$. Assume that I have given a point $$r$$.

I want to solve the separation problem to decide if either $$r \in X$$ or I want a hyperplane that separates $$r$$ from $$X$$. Is there some practical algorithm for this given the optimization oracle?

• You haven't stated that $X$ is convex. If $X$ is not convex and $r \notin X$,, there may not be a hyperplane separating $r$ from $X$. – Mark L. Stone Mar 4 at 17:03
• Yes sorry $X$ is convex – user3680510 Mar 4 at 17:08

You can minimize any convex function $$f$$ over $$X$$ using the Frank-Wolfe algorithm. In particular, this will give you valid dual bounds at every iteration.

[Note: the FW algorithm assumes that you can minimize any linear function over $$X$$]

Consider the problem \begin{align} Z^{*} = &\min_{x}\quad\|x - r\|^{2}\\ &\text{s.t.} \quad x \in X \end{align}

Assume that $$r \notin X$$, i.e., $$Z^{*} > 0$$, and apply Frank-Wolfe to the above problem. After some iteration, you will get a positive dual bound, i.e., you know that $$Z^{*} \geq Z_{\text{dual}} > 0$$, which will prove that $$r \notin X$$.

You can then deduce a separation hyperplane from the ball centered at $$r$$ of radius $$Z^{*}$$ by taking a tangent at $$x^{*}$$, where $$x^{*}$$ is an optimal solution of the above problem.

• thanks, that looks pretty cool! – user3680510 Mar 5 at 9:09
• If $X$ is a polytope, can i converge such that the separation hyerplane becomes a facet at some point? – user3680510 Mar 5 at 9:21
• And didnt you mean the ball is centered around the current iterate? Or maybe can you expand the last point? – user3680510 Mar 5 at 14:08
• Sorry, I made a slight typo. Once you have $Z_{dual} > 0$, you know that $r \notin X$. To get a separating hyperplane you can use an optimal solution provided by FW. I've edited the answer. – mtanneau Mar 5 at 14:36
• My gut tells me there should be a way to deduce a separating hyperplane as soon as you have $Z_{dual} > 0$, but I did not manage to prove that in the 10min I spent thinking about it. – mtanneau Mar 5 at 14:43