Everything2
Near Matches
Ignore Exact
Full Text
Everything2

proof of Caratheodory's theorem on convexity

created by ariels

(idea) by ariels (1.5 d) (print)   ?   (I like it!) 1 C! Fri Sep 28 2001 at 9:42:18

It's best to read about Caratheodory's theorem, to know we're trying to prove.

Caratheodory's theorem on convex sets is essentially equivalent to Radon's theorem; we'll use that theorem in our proof.

Suppose x = ∑k=1mxkxk is a convex combination of m>d+1 points. We need to show that x is a convex combination of m-1 of these points (this is the equivalent formulation given).

By Radon's theorem (and since m>d+1 is large enough!), we can divide our m points into 2 nonempty sets of points (WLOG x1,...,xl and xl+1,...,xm) whose convex hulls share a point:

i=1laixi = ∑i=l+1mbixi
ai >= 0, bj >= 0, ∑ai = ∑bj = 1
Furthermore, one of the b's, WLOG bm, satisfies ∀k:ck/bk >= cm/bm (every finite set has a minimum!).

Isolating xm, we have:

xm = (∑i=1laixi - ∑i=l+1m-1bixi) / bm
Substituting for x, we may write x as a linear combination of the points x1,...,xm-1 (this in itself is no surprise; it's true for any linear combination of >d points in Rd! The point is we'll show it's a convex combination...):
x = ∑i=1l(ci+aicm/bm)xi + ∑i=l+1m-1(ci-bicm/bm)xi
Checking, we find the sum of the coefficients is 1 (this is not surprising), so it's an affine combination.

It remains to prove that all coefficients are nonnegative. Those involving ai are just sums of positive numbers, so there's no problem. And for each l+1<=i<m, we have ci>=bicm/bm) due to how we arranged the coefficients.

So x is a convex combination of m-1 points. We may continued to eliminate points from the convex combination until only d+1 are left; at that point, Radon's theorem could fail, so no further reduction is possible.


printable version
chaos

Caratheodory's theorem Radon's theorem Galaxy Quest compactness theorem
ultraproduct theorem WLOG convex combination
Convex
Y'know, if you log in, you can write something here, or contact authors directly on the site. Create a New User if you don't already have an account.
  Epicenter
Login
Password

password reminder
register

Everything2 Help

Cool Staff Picks
What you are reading:
William Shakespeare
logicism
The Infamous Bell Tower Prank of 1996
Alcohol vs. ecstasy
True neutral
Nobel Prize in Literature
On finding a wife
I, Robot
OLA Scary Story Contest 2000
Essay on Silence
Rhubarb
Early, before our hands knew what to do
Everything as a second language
New Writeups
XWiz
Trism(review)
artman2003
Briefcase Full of Souls - Part I(fiction)
Dreamvirus
Alan Ladd(person)
waverider37
Harold Holt(person)
The Debutante
Until death do us part(fiction)
Ysardo
a brother to a sister(personal)
antigravpussy
your warm whispers(personal)
Clarke
Multiculturalism(idea)
aneurin
Earl of Landaff(person)
Heitah
Pseudocide(idea)
XWiz
Google Knol(lede)
Mythi
July 24, 2008(personal)
locke baron
The fall of Earth(fiction)
BookReader
Fear the Cold(dream)
Pavlovna
Kathleen MacInnes(person)
This page courtesy of The Everything Development Company