Equivalence of two definitions of polar of polytope

223 Views Asked by At

Let $a_i \in \mathbb{R}^n$. $P = \{ x_i \vert \ a_i \cdot x_i \leq 1 \ \forall x_i \in \mathbb{R}^n, i \in [1\dots n] \}$, P is bounded. Since P is a bounded polyhedra, it is a polytope (by Weyl-Minkowski).

Now, consider:

$$ \begin{align} Q_1 &= \text{Conv}(a_1, a_2, \dots, a_n) \\ Q_2 &= \{ y \mid y \cdot p \leq 1, \forall y \in \mathbb{R}^n, \forall p \in P \} \end{align} $$

Prove that $Q_1 = Q_2$. We know that $Q_2$ is the standard definiton of polar. We wish to show equivalence to the first form. Roughly, we wish to show that the polar of a polytope is a polytope, with the new vertices being the hyperplane normals. Note that we are using a normalized polytope, with the constraints $\leq 1$.

Forward direction of proof ($Q_1 \subseteq Q_2$)

The rough sketch is as follows. Let $q \in Q_1$. Since $Q_1$ is the convex hull of $a_1, \dots, a_n$:

$$ q = \sum_i a_i \lambda_i \\ $$

Where $\lambda_i$ are of the form: $$ \begin{align} \lambda_i &\in \mathbb{R} \\ \lambda_i &\geq 0 \\ \sum_i \lambda_i &= 1 \end{align} $$

$\forall p \in P$, consider $q \cdot p$.

$ q \cdot p = (\sum_i a_i \lambda_i) \cdot p = \sum (a_i \cdot p) \lambda_i $

Each $a_i \cdot p \leq 1$, because $p \in P$, hence by definition of $P$ the inequality holds.

Therefore, $\sum (a_i \cdot p) \lambda_i \leq \sum 1 \lambda_i \leq \sum \lambda_i$.

We know that $\sum \lambda_i = 1$ by definition. Hence, $\forall p \in P, q \cdot p \leq \sum \lambda_i \leq 1$.

Hence, $q \in Q_2$, and $Q_1 \subseteq Q_2$.

Backward Direction of Proof ($Q_2 \subseteq Q_1$)

I have gotten stuck when trying to prove this. The obstacle I face is this: given some point $q \in Q_2$, we need to actually describe such a point as a convex combination of $a_i$. I have no idea how to come up with the $\lambda_i$ coefficients.

Any proof strategy hints would be very welcome :)

1

There are 1 best solutions below

2
On BEST ANSWER

The following incomplete proof uses LP duality. $$\begin{align} Q_2 &= \{ y \in \mathbb{R}^n \mid y \cdot p \leq 1 \; \forall p : a_i \cdot p \leq 1 \} \\ &= \{ y \in \mathbb{R}^n \mid \max_p \{ y \cdot p \mid a_i \cdot p \leq 1 \} \leq 1 \} \\ &= \{ y \in \mathbb{R}^n \mid \min_{\lambda \in \mathbb{R}^n_+} \{ \sum \lambda_i \mid \sum_i \lambda_i a_i = y \} \leq 1 \} \\ &= \{ y \in \mathbb{R}^n \mid \exists \lambda \in \mathbb{R}^n_+ : \sum_i \lambda_i \leq 1, \sum_i \lambda_i a_i = y \} \end{align}$$ This is almost correct, the only problem being the sum of $\lambda$ is not necessarily $1$. We have not used that $P$ is bounded.