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?

  • 1
    $\begingroup$ 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$. $\endgroup$ Mar 4, 2021 at 17:03
  • 2
    $\begingroup$ Yes sorry $X$ is convex $\endgroup$ Mar 4, 2021 at 17:08

1 Answer 1


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.

  • $\begingroup$ thanks, that looks pretty cool! $\endgroup$ Mar 5, 2021 at 9:09
  • $\begingroup$ If $X$ is a polytope, can i converge such that the separation hyerplane becomes a facet at some point? $\endgroup$ Mar 5, 2021 at 9:21
  • $\begingroup$ And didnt you mean the ball is centered around the current iterate? Or maybe can you expand the last point? $\endgroup$ Mar 5, 2021 at 14:08
  • $\begingroup$ 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. $\endgroup$
    – mtanneau
    Mar 5, 2021 at 14:36
  • $\begingroup$ 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. $\endgroup$
    – mtanneau
    Mar 5, 2021 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.