More convex hull - Krein-Milman
Published by Angel on Sunday, May 16, 2010 - 04:09:04 - Filed under Convex Sets
I kinda said I was going to post more often and stuff but I’ve been ( again ) very busy with school. The semester is almost over , also I’ve been waiting for more theorems or lemmas related to the convex hull of a set.
I’ve been waiting for this theorem for a while , I didnt knew what it said but it was an intuitive idea I thought it may be inside a theorem and guess what. Here it is :).
————————
[sub]Lemma:[/sub]
Let A be a convex compact set, then each supporting hyperplane on A contains at least one extreme point of A.
[sub]Proof[/sub]
Let H be a supporting hyperplane on A, we know that 
so it is also compact and convex.
Then there is a point x in the intersection of the hyperplane and A such that it is an extreme point of H intersection A, then x is also an extreme point of A.
[sub]Krein-Milman Theorem[/sub]
Let E be a convex and compact set on R^n, then the convex hull of the set of extreme points of E is the set E itself.
[sub]Proof:[/sub]
Its clear that E is a subset of the convex hull of the set of all extreme points of E since the extreme points belong to E.
Now we have to see that 
.
Lets use induction over k the dimension of E
If k =0 then E is a single point
If K = 1 then E is a closed line segment.
Lets use as induction hypothesis that the theorem is true for k-1 with k<n.
Let x be the relative interiorof E. Then by our lemma there is a supporting hyperplane of E that contains x.
Then 
is compact and convex with 
, so by our induction hypothesis we have that x is a convex combination of the extreme points of . Since the extreme points of are extreme in E we have that :
If x is in the relative interior of E then there is a line segment that contains x that also intersects the boundary of E. Then E and the line segment can be expressed as a convex combination of extreme points of E then
Then:
.
—————————–
This is by far my favorite theorem, Ive been tryin to use it along with Radon’s theorem or directly with Caratheodory’s but I havent found anything good enough.
:)
