# Equivalence of two definitions of polar of polytope

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 :)

• Your definition of $P$ does not make sense due to the $\forall x_i$. Do you mean $P = \{ x \in \mathbb{R}^n : a_i \cdot x \leq 1 \forall i \in \{1,..,n\} \}$? – LinAlg Mar 19 '18 at 13:20

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.
• Thanks for the pointer. I'm actually unsure how you would control $\lambda_i$ using the fact that $P$ is bounded. May I have a hint or a full proof? I've never seen duality used within algebraic manipulation before :) – Siddharth Bhat Mar 19 '18 at 17:42
• It has to do with $0 \in Q_i$, and giving it weight $1-\sum_i \lambda_i$. – LinAlg Mar 20 '18 at 1:04