3

Let $P\subseteq \mathbb{R}^{n}$ is convex hull of finite points: $P=conv(x_1,x_2,\ldots,x_m)$. I need to show that $P$ is convex hull of its extreme points.

I am thinking about such proof. Let $x_{i_{1}},x_{i_{2}},\ldots,x_{i_{k}}$ is minimal subset of $x_1,x_2,\ldots,x_m$ for which $P=conv(x_{i_{1}},x_{i_{2}},\ldots,x_{i_{k}})$. How to prove that each $x_{i_{j}}$ is extreme point?

If some $x_{i_{j}}$ is not extreme point, it can be represented $x_{i_{j}}=\frac{1}{2}x'+\frac{1}{2}x''$ where $x'\in P$ and $x''\in P$ and $x' \neq x''$. How to continue?

glS
  • 6,818
Ashot
  • 4,753
  • 3
  • 34
  • 61
  • Use minimality, i.e. that removing $x_{i_j}$ produces a smaller convex hull. – Hagen von Eitzen Jan 19 '13 at 15:47
  • The interior points can be written with positive barycentric coordinates, while the extreme points will have one zero barycentric coordinate. Here is the type of algebra needed to show this precisely: http://users.eecs.northwestern.edu/~thanh/paper/alg.pdf – alancalvitti Jan 19 '13 at 16:04

1 Answers1

3

Let $x_1,x_2,\ldots,x_n$ is minimal set for which $P=conv(x_1,x_2,\ldots,x_n)$ and $x_1$ is not extreme point. $x_1=\frac{1}{2}x'+\frac{1}{2}x''$ and $x'\neq x''$

$x'=\sum_{i=1}^{n}\lambda_i'x_i $ and $\sum_{i=1}^{n}\lambda_i'=1$

$x''=\sum_{i=1}^{n}\lambda_i''x_i $ and $\sum_{i=1}^{n}\lambda_i''=1$

So $x_1=\sum_{i=1}^{n}\frac{\lambda_i'+\lambda_i''}{2}x_i=\sum_{i=1}^{n}\mu_ix_i$

If $\mu_1<1$ then $x_1=\frac{1}{1-\mu_1}\sum_{i=2}^{n}\mu_ix_i$ and we would have contrary to minimality of set $x_1,x_2,\ldots,x_n$

If $\mu_1=1$ then $\mu_i=0$ for $i\neq1$ or $\frac{\lambda_i'+\lambda_i''}{2}=0$ which means $\lambda_i'=\lambda_i''=0$ for $i\neq1$, so that $x'= x_1 = x''$.

Ashot
  • 4,753
  • 3
  • 34
  • 61