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.


Theorem

Let $E \subset \R^\ell$.

Let $\mathbb x \in \map {\operatorname{co} } 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 $\ell + 1$ points of $E$.


Proof

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

From the definition of convex combination:

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

with:

$\gamma_i \ge 0$
$\displaystyle \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$:

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

and:

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


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

Then:

$\displaystyle \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:

$\displaystyle \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:

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

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

$\blacksquare$


Source of Name

This entry was named for Constantin Carathéodory.


Sources