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?

  • $\begingroup$ Use minimality, i.e. that removing $x_{i_j}$ produces a smaller convex hull. $\endgroup$ Jan 19 '13 at 15:47
  • $\begingroup$ 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: users.eecs.northwestern.edu/~thanh/paper/alg.pdf $\endgroup$ Jan 19 '13 at 16:04

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''$.


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.