Carathéodory's Theorem (Convex Analysis)

From ProofWiki
Jump to navigation Jump to search

This proof is about Carathéodory's Theorem in the context of Convex Analysis. For other uses, see Carathéodory's Theorem.


This article needs to be linked to other articles.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{MissingLinks}} from the code.


Theorem

Let $E \subset \R^l$.

Let $\mathbb x \in \map {\operatorname {conv} } E$, where $\map {\operatorname {conv} } E$ denotes the convex hull of $E$.


Then $\mathbf x$ is a convex combination of affinely independent points of $E$.

In particular, $\mathbf x$ is a convex combination of at most $l + 1$ points of $E$.


Proof

Since $\mathbb x \in \map {\operatorname {conv} } E$, $\mathbf x$ is a convex combination of points in $E$.

From the definition of convex combination:

$\ds \mathbf x = \sum_{i \mathop = 1}^k \gamma_i \mathbf y_i$

with:

$\gamma_i \ge 0$
$\ds \sum_{i \mathop = 1}^k \gamma_i = 1$

and:

$\mathbf y_i \in E$


Let $K \subset \N$ be the set of all possible $k$ such that $\mathbf x$ is a convex combination of $k$ elements of $E$.

By the Well-Ordering Principle, $K$ is well-ordered.

$K$ has a smallest element $k_s$ by the definition of well-ordered sets.


Suppose that the set $\set {\mathbf y_i: i \le k_s}$ is affinely dependent.

From the condition for affinely dependent set, there exists a set $\set {\alpha_i: i \le k_s}$ such that for some $\alpha_i > 0$:

$\ds \sum_{i \mathop = 1}^{k_s} \alpha_i \mathbf y_i = 0$

and:

$\ds \sum_{i \mathop = 1}^{k_s} \alpha_i = 0$


Pick the smallest $\dfrac {\gamma_j} {\alpha_j} > 0$.

Then:

$\ds \mathbf x = \paren {\sum_{i \mathop = 1}^{k_s} \gamma_i \mathbf y_i} + 0 = \paren {\sum_{i \mathop = 1}^{k_s} \gamma_i \mathbf y_i} - \paren {\frac {\gamma_j} {\alpha_j} \sum_{i \mathop = 1}^{k_s} \alpha_i \mathbf y_i}$

Rearrange to get:

$\ds \mathbf x = \paren {\sum_{i \mathop = 1}^{k_s} \paren {\gamma_i - \frac {\gamma_j} {\alpha_j} \alpha_i} \mathbf y_i}$

Since $\gamma_j > 0$ is made the smallest and $\alpha_j > 0$ is made the greatest:

$\dfrac {\alpha_i} {\alpha_j} \gamma_j \le \gamma_j \le \gamma_i$

for all $i \le k_s$.

Thus:

$\paren {\gamma_i - \dfrac {\gamma_j} {\alpha_j} \alpha_i} \ge 0$

For $i = j$:

$\paren {\gamma_i - \dfrac {\gamma_j} {\alpha_j} \alpha_i} = 0$

For $i \ne j$, let:

$\gamma'_{i'} \equiv \gamma_i - \dfrac {\gamma_j} {\alpha_j} \alpha_i$

We can express:

$\ds x = \sum_{i' \mathop = 1}^{k_s-1} \gamma'_{i'} \mathbf y_i$

which contradicts the assumption that $k_s = \min K$.


This needs considerable tedious hard slog to complete it.
In particular: It seems to intend to prove $k_s \le l + 1$ with affine independence of $\set {\mathbf y_i: i \le k_s}$.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Finish}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.


$\blacksquare$


Source of Name

This entry was named for Constantin Carathéodory.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Carathéodory%27s_Theorem_(Convex_Analysis)&oldid=652723"