Caratheodory定理

設S是$\mathbb{R}^n$中的任意集合。如果$x \in Co\left ( S \right )$，則$x \in Co\left ( x_1,x_2,....,x_n,x_{n+1} \right )$。

證明

由於$x \in Co\left ( S\right )$，則x可以表示為S中有限個點的凸組合，即：

$x=\displaystyle\sum\limits_{j=1}^k \lambda_jx_j,\displaystyle\sum\limits_{j=1}^k \lambda_j=1, \lambda_j \geq 0$ 且 $x_j \in S, \forall j \in \left ( 1,k \right )$

如果$k \leq n+1$，則結果顯然成立。

如果$k \geq n+1$，則$\left ( x_2-x_1 \right )\left ( x_3-x_1 \right ),....., \left ( x_k-x_1 \right )$線性相關。

$\Rightarrow \exists \mu _j \in \mathbb{R}, 2\leq j\leq k$（不全為零）使得 $\displaystyle\sum\limits_{j=2}^k \mu _j\left ( x_j-x_1 \right )=0$

定義$\mu_1=-\displaystyle\sum\limits_{j=2}^k \mu _j$，則$\displaystyle\sum\limits_{j=1}^k \mu_j x_j=0, \displaystyle\sum\limits_{j=1}^k \mu_j=0$

其中不所有的$\mu_j$都等於零。由於$\displaystyle\sum\limits_{j=1}^k \mu_j=0$，至少有一個$\mu_j > 0,1 \leq j \leq k$

則，$x=\displaystyle\sum\limits_{1}^k \lambda_j x_j+0$

$x=\displaystyle\sum\limits_{1}^k \lambda_j x_j- \alpha \displaystyle\sum\limits_{1}^k \mu_j x_j$

$x=\displaystyle\sum\limits_{1}^k\left ( \lambda_j- \alpha\mu_j \right )x_j $

選擇$\alpha$使得$\alpha=min\left \{ \frac{\lambda_j}{\mu_j}, \mu_j\geq 0 \right \}=\frac{\lambda_j}{\mu _j},$ 對於某個$i=1,2,...,k$

如果$\mu_j\leq 0$，則$\lambda_j-\alpha \mu_j\geq 0$

如果$\mu_j> 0$，則 $\:\frac{\lambda _j}{\mu_j}\geq \frac{\lambda_i}{\mu _i}=\alpha \Rightarrow \lambda_j-\alpha \mu_j\geq 0, j=1,2,...k$

特別地，$\lambda_i-\alpha \mu_i=0$，根據$\alpha$的定義

$x=\displaystyle\sum\limits_{j=1}^k \left ( \lambda_j- \alpha\mu_j\right )x_j$，其中

$\lambda_j- \alpha\mu_j\geq0$ 且 $\displaystyle\sum\limits_{j=1}^k\left ( \lambda_j- \alpha\mu_j\right )=1$ 且 $\lambda_i- \alpha\mu_i=0$

因此，x可以表示為最多(k-1)個點的凸組合。

這個簡化過程可以重複進行，直到x可以表示為(n+1)個元素的凸組合。