0
$\begingroup$

Is there a way to check if the point is outside of a polytope if polytope is defined as $\mathcal{P}=\{x|a_j^\top x\leq b_j, \;j=1,\dots,m\}$?

I was able to derive the following:

\begin{equation} \min_{j\leq m}\Bigg\{\frac{b_j-a_j^\top x}{\|a_j\|}\Bigg\}. \end{equation}

If the above expression is $\leq 0$, then the point is outside of the polytope. However, the expression above is nonconvex, which is my main concern.

$\endgroup$
  • $\begingroup$ Your test is correct. Why bother about the non convexity of this function ? It does the work, that's all... $\endgroup$ – Jean Marie Aug 14 at 5:46
  • 1
    $\begingroup$ I will put this as my constraint in an optimization problem, so in order to have a convex program, I need a convex constraint. $\endgroup$ – Seda Aug 14 at 5:48
  • $\begingroup$ Your expression in one dimension, it is a concave function (for example $\min((x-3),(-x+5))$. Taking the opposite gives a convex function. Why shouldn't it work in any dimension ? $\endgroup$ – Jean Marie Aug 14 at 5:54
  • 1
    $\begingroup$ if I take the opposite, then instead of $\leq 0$ I get $\geq 0$, which in turn becomes a noncvonex constraint again. In particular, $\min_{j\leq m}\Bigg\{\frac{b_j-a_j^\top x}{\|a_j\|}\Bigg\} \leq 0$ is equivalent to $\max_{j\leq m}\Bigg\{\frac{a_j^\top x-b_j}{\|a_j\|}\Bigg\} \geq 0$. $\endgroup$ – Seda Aug 14 at 6:51
  • $\begingroup$ Of course it must be nonconvex because the complement of the polytope is not convex. You won't avoid that. You will probably need to use binary variables to pick a violated inequality. $\endgroup$ – Michal Adamaszek Aug 14 at 7:41

Your Answer

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

Browse other questions tagged or ask your own question.