Consider the polytope $$K = \{x\in\mathbb{R}^n: \langle x,v_i\rangle \leq 1, 1\le i\leq m\}$$ with $m$ facets, for which $$B^n_2 \subset K \subset dB^n_2$$ where $1<d\in\mathbb{R}^{+}$ and $B^n_2 := \{ x\in\mathbb{R}^n: \| x\| \leq 1\}$, i.e. the Euclidean ball of unit radius. $dB^n_2$ is the scaled version of this.
What I have so far:
- The first inclusion implies that each $\|v_i\| \leq 1$ for all $1\leq i\leq m$ (since $\frac{v_i}{\|v_i\|} \in B^n_2$).
- The second inclusion gives us that if $\|x\| > d$ $(x\notin dB^n_2)$, then there exists $i$ such that $\langle x,v_i\rangle > 1$ (so that $x\notin K$).
What I want to show:
I want to show that the second conclusion above is equivalent to:
For every unit vector $\theta$, there exists an $i$ such that $$\langle \theta,v_i\rangle \geq \frac{1}{d}$$
How should I go about this? I'm unable to relate the statements I have so far to unit vectors in any sense - and hence I haven't had much progress proving the above equivalence. I tried starting off with $\langle d\theta,v_i\rangle \geq 1$ instead, so that $\|d\theta\| = d$ and $d\theta\in dB^n_2$.
I'd appreciate any help, thanks!
Clarification:
- $d\theta$ = $d \times \theta$, i.e. $d$ times the unit vector $\theta$. It is not the infinitesimal $d\theta$ seen often in analysis.
Which part are you struggling with?
The backward direction follows immediately, since for any $x$ with $\|x\|>d$, you know that there exists some $i$ such that $\left\langle \frac{x}{\|x\|},v_i\right\rangle \geq \frac{1}{d}$. Multiplying this by $\|x\|$ on either side gives the required.
For the forward direction, for any $d'>d$, you know that there exists $i$ such that $\langle \theta,v_i\rangle>\frac{1}{d'}$. Are you able to conclude from here that there exists $i$ such that $\langle \theta,v_i\rangle\geq\frac{1}{d}$?