Numerical check that a polytope is small

61 Views Asked by At

I have a polytope $S$ defined by linear equations. Ideally, I would like to show that my polytope contains only 1 point. To do that, I could maximize and minimize each of the $n$ variables.

However I figured that there could be a faster solution by taking random vectors $v$ according to a distribution that does not bias in a direction.

Suppose that the diameter of $S$ is $d$.

Then the probability of $\left(\max\limits_{x\in S} v \cdot x\right)-\left(\min\limits_{x\in S} v \cdot x\right) < \varepsilon$ is bounded by the probability when taking the max and min over the diameter.

We choose $v$ according to a $n$ dimensional Gaussian distribution. Then WLOG $\Pr\left[\left(\max\limits_{x\in S} v \cdot x\right)-\left(\min\limits_{x\in S} v \cdot x\right) < \varepsilon\right] \le Pr\left[|v_1| < \frac{\varepsilon}{d}\right]$ where $v_1$ is the first component of $v$.

By repeating for multiple $v$, we can exponentiate this probability. Thus, we get some frequentist confidence interval $[d_{min}, d_{max}]$.

Does this work? Is this approach known? Is it documented somewhere? Is there a better way?