Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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: users.eecs.northwestern.edu/~thanh/paper/alg.pdf –  alancalvitti Jan 19 '13 at 16:04

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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