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)个元素的凸组合。