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$ – Mark L. Stone Mar 4 at 17:03
  • 2
    $\begingroup$ Yes sorry $X$ is convex $\endgroup$ – 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.

  • $\begingroup$ thanks, that looks pretty cool! $\endgroup$ – user3680510 Mar 5 at 9:09
  • $\begingroup$ If $X$ is a polytope, can i converge such that the separation hyerplane becomes a facet at some point? $\endgroup$ – user3680510 Mar 5 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$ – user3680510 Mar 5 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 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 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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