Carathéodory's Theorem (Convex Analysis)

From ProofWiki
Jump to navigation Jump to search

This proof is about Carathéodory's Theorem in 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