1
$\begingroup$

Let $P$ be a polyhedron and let $S=\{ v_1, \ldots, v_r\}$ its extreme points. Suppose further that $\text{rec}(P)={0}$ so $P=\text {conv}(S)$. How do I see that I cannot remove any points from $S$ and still get a proper subset $S'$ such that $P=\text{conv}(S')$ ?

I've considered linear equations and matrix form, but cannot prove rigorously that I cannot remove any points. Can someone help ?

$\endgroup$
1
$\begingroup$

By definition, an extreme point is one that can't be represented as a (nontrivial) convex combination of two other points in the set.

By definition, the convex hull of a set of points is the set of all their convex combinations.

What we'd like to say now is that, if $S'\subsetneq S$, then there is $x\in S\setminus S'$; since $x$ is extreme, it cannot be represented as a convex combination of points in $S'$, and so $x$ isn't in the convex hull of $S'$; in particular, $\operatorname{\text{conv}}\ S'\ne P$. This doesn't quite work, though, because of the gap between "convex combination of two points" and "convex combination of [some number of] points".

What's needed to cross that gap is something like this: If $x$ is a nontrivial convex combination of points $v_1,\dotsc,v_r$, then there exist points $u_1$ and $u_2$ which are convex combinations of $v_1,\dotsc,v_r$ and such that $x$ is a nontrivial convex combination of $u_1$ and $u_2$. Can you prove that? (If it's not clear how to get started, draw a picture for the case $r=3$.)


As a hint, consider this different, kind of converse, statement: if $u_1$ and $u_2$ are convex combinations of $v_1,\dotsc,v_r$, and $x$ is a convex combination of $u_1$ and $u_2$, then $x$ is a convex combination of $v_1,\dotsc,v_r$. Proof: By assumption, there exist $\alpha_i$ and $\beta_i$, all nonnegative, such that $\sum_i \alpha_i = 1$ and $\sum_i \beta_i = 1$ and $$ u_1 = \sum_i \alpha_i v_i \qquad\text{and}\qquad u_2 = \sum_i \beta_i v_i $$ Also by assumption, there exists $\lambda$, nonnegative, such that $x = (1-\lambda)u_1 + \lambda u_2$. Thus \begin{align*} x &= (1-\lambda)u_1 + \lambda u_2 \\ &= (1-\lambda)\sum_i\alpha_i v_i + \lambda\sum_i \beta_i v_i \\ &= \sum_i ((1-\lambda)\alpha_i + \lambda\beta_i) v_i \end{align*} I claim that this is a representation of $x$ as a convex combination of the $v_i$. Indeed, it is a linear combination of the $v_i$; the coefficients $(1-\lambda)\alpha_i+\lambda\beta_i$ are nonnegative (since they are weighted averages of nonnegative quantities); and they sum to 1: $$ \sum_i ((1-\lambda)\alpha_i + \lambda\beta_i) = (1-\lambda)\sum_i\alpha_i + \lambda\sum_i\beta_i = (1-\lambda)\cdot 1 + \lambda\cdot 1 = 1 $$

This is most of a proof that $\operatorname{conv}\operatorname{conv} S = \operatorname{conv} S$. As stated above, though, you can see that the parts are the same as in the statement you need to prove, just rearranged. The goal for the above problem is to reverse this process somehow — to find possible $u_1$ and $u_2$, given only the final convex combination.

$\endgroup$
  • $\begingroup$ I've tried proving it. I don't get started. Is the proof hard ? $\endgroup$ – Shuzheng Jun 22 '15 at 12:16
  • $\begingroup$ I don't know whether it's hard. It uses ideas like those in the proof that $\operatorname{\text{conv}}\operatorname{\text{conv}}\ S = \operatorname{\text{conv}}\ S$, but backwards. Do you know that proof? $\endgroup$ – user21467 Jun 22 '15 at 12:19
  • $\begingroup$ Sorry no, can you like it ? $\endgroup$ – Shuzheng Jun 22 '15 at 12:20
  • $\begingroup$ I'll see if I can find it online later today, but I have to go to work now. $\endgroup$ – user21467 Jun 22 '15 at 12:23
  • $\begingroup$ Thank you ... see you later. $\endgroup$ – Shuzheng Jun 22 '15 at 12:33
1
$\begingroup$

You can separate the $\mathrm{conv}(S')$ and $S\setminus S'$ due to the separation theorems which follow from Hahn--Banach Theorem. So if we would have $\mathrm{conv}(S')=P$, then $S\setminus S'\not\subset P$, a contradiction.

$\endgroup$

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.