1

Caratheodory's Theorem states that any member $x$ of a convex set $C \subseteq \mathbb{R}^{d}$ can be written as a convex combination of at most $d+1$ points from $C$. The wikipedia article for Caratheodory's Theorem (and other resources) mention that in fact you can go one step further and assert that any $x \in C$ can be written as a convex combination of at most $d+1$ extremal points from $C$.

Intuitively, I can see why this is the case, but I am struggling to justify this corollary rigorously. Why do we only need extremal points? This seems to amount to proving that every member of a convex set can be written as a convex combination of the set's extremal points. How would I go about proving this?

Nick Bishop
  • 797
  • The Wikipedia page sketches the proof of the corollary in that sentence: if $P$ denotes the set whose convex hull is $C$, then "non-extremal points can be removed from $P$ without changing the membership of $x$ in the convex hull." – angryavian May 16 '22 at 19:22
  • Thanks, I think I have a proof based on this now! Its actually really obvious...oh well haha. – Nick Bishop May 16 '22 at 20:34

1 Answers1

0

So I think the answer to this is in fact really obvious. If we can prove that the convex hull of any set of points $ S = \{x_{1}, \dots, x_{n}\} \subseteq C$ produces the same convex hull when a non-extremal point is removed then we are done.

So without loss of generality, assume that $x_{1}$ is non-extremal. Then $x_{1}$ can be written as a convex combination not including itself. This means it can be expressed as a convex combination of the form $x_{1} = \sum^{k}_{i=2}\mu_{i}x_{i}$. Now consider any $x \in \text{conv}(S)$. By definition, $x$ can be written as

$$ x = \sum^{k}_{i=1}\lambda_{i}x_{i} = \sum^{k}_{i=2}\lambda_{i}x_{i} + \lambda_{1}x_{1} = \sum^{k}_{i=2}\lambda_{i}x_{i} + \lambda_{1}\sum_{i=2}^{k}\mu_{i}x_{i} $$

We have expressed $x$ as a convex combination of elements of $S - \{x_{1}\}$. Since $x$ was arbitrary we conclude that $\text{conv}(S) = \text{conv}(S - \{x_{1}\})$ and we are done!

EDIT: My only concern is in how this argument is exactly applied:

For example, by Caratheodory's Theorem there exists an expression for any $x \in C$ such that

$$ x = \sum^{d+1}_{i=1}\lambda_{i}x_{i} $$

Say $x_{1}$ is non-extremal. It may still be extreme in $\text{conv}(\{x_{1}, \dots, x_{n}\})$! Therefore, the previous argument does not allow us to remove it!

Nick Bishop
  • 797
  • Aren't we only concerned with a set of points whose convex hull is $C$? Why are you considering some other convex sets besides $C$? – angryavian May 16 '22 at 22:02
  • My first thought was to apply this argument to the convex hull of the set of $d+1$ points whose existence is guaranteed by Caratheodory. But then you run into the issue in my edit I think. If I applied this argument directly to $C$ I'd need to have a way of going from removing one non-extremal point to all of them at once. I think this requires some sort of intersection argument I am now working on. – Nick Bishop May 16 '22 at 22:13
  • What exactly is the statement of the theorem you are using? In the Wikipedia statement, the set of points generating the convex hull is given as a condition in the theorem, and the guaranteed $d+1$ points are a subset of this set of points. – angryavian May 16 '22 at 22:15
  • I am assuming I am given a convex set $C$. That is, the set of points I am given is the set $C$ and the convex hull I am looking at is $C = \text{conv}(C)$. – Nick Bishop May 16 '22 at 23:15
  • I guess I do not understand how $x_1$ is non-extremal in $C$ but can be extreme in $\text{conv}{x_1, \ldots, x_n}$ when this latter set is the same as $C$. – angryavian May 17 '22 at 04:14
  • So I guess I am trying to argue that you can take the $d+1$ points returned by Caratheodory, and discard the non-extremal points of this set of $d+1$ points. However note that in general the convex hull of these $d+1$ may not be equal to $C$. As a result, a point in the set of $d+1$ points may be extremal in the $d+1$ convex hull whilst not being extremal in $C$. Therefore you cannot use the argument I outlined to remove it if that makes sense. – Nick Bishop May 17 '22 at 15:00
  • The $d+1$ points returned by the theorem are such that any point of $C$ is a convex combination of these $d+1$ points. This is equivalent to saying that the convex hull of these $d+1$ points is $C$. Read the first two sentences of the Wikipedia article. – angryavian May 17 '22 at 16:44
  • Yes but these $d+1$ points don't need to be the same for every $x$ right? There could be a different set of $d+1$ points for each $x$. My understanding is that you provide a point $x$ and are given a convex combination of $d+1$ points. These $d+1$ points may depend on your choice of $x$. This is evident in the proof of the theorem too? – Nick Bishop May 17 '22 at 17:03
  • Ah I see, that was my misunderstanding, thanks for pointing that out. Regarding how to make the non-extremal argument work: you should remove the non-extremal points from set of points whose convex hull is $C$ and then apply the theorem (rather than removing non-extremal points from the set of $d+1$ points returned by the theorem). – angryavian May 17 '22 at 17:09
  • I was thinking that something like this may work but my concern is that we are only removing one point at a time. First of all, there is no guarantee that after a certain number of points are removed that a remaining point won't become extremal. It is also unclear how to ensure that this process terminates as $C$ is uncountable. – Nick Bishop May 17 '22 at 17:20
  • Good point, you might want to ask a separate question on this. I think Krein-Milman may be relevant, but I'm not too knowledgeable about this. – angryavian May 17 '22 at 17:52
  • Yeah I think this result is what I need. There is a finite dimensional analogue called the Caratheodory-Minkowsky Theorem. I will update my answer with a proof of this result. Thanks for the help! – Nick Bishop May 17 '22 at 18:59