3
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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\} \}$? $\endgroup$ – LinAlg Mar 19 '18 at 13:20
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 :) $\endgroup$ – Siddharth Bhat Mar 19 '18 at 17:42
  • 1
    $\begingroup$ It has to do with $0 \in Q_i$, and giving it weight $1-\sum_i \lambda_i$. $\endgroup$ – LinAlg Mar 20 '18 at 1:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.