# Convex function for checking if the point is outside of a polytope

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.

• Your test is correct. Why bother about the non convexity of this function ? It does the work, that's all... – Jean Marie Aug 14 at 5:46
• I will put this as my constraint in an optimization problem, so in order to have a convex program, I need a convex constraint. – Seda Aug 14 at 5:48
• 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 ? – Jean Marie Aug 14 at 5:54
• 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$. – Seda Aug 14 at 6:51
• 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. – Michal Adamaszek Aug 14 at 7:41