Carathéodory theorem

tags: Mathematics Convex Analysis

Theorem.
Let

$x\in \text{conv}(P)$, where

$P\subseteq {\mathbb{R}}^m$. Then there exists a set of points

$X=\{x_1,\dots ,x_n\}\subseteq P$ with

$n\le m+1$ such that

$x\in \text{conv}(X)$.

Proof.
Assume that

$n>m+1$ and

$$x=\sum _{i=1}^n{\lambda }_i{x}_i,$$
where

$x_i\in P,{\lambda }_i>0$ for each

$i$ and

$\sum _{i=1}^n{\lambda }_i=1$. Since

$n-1>m$, these vecctors

$$x_2-x_1,x_3-x_1,\dots ,x_n-x_1$$
are linearly dependent. Hence, there exists a system of coefficients

$\{{\alpha }_i:i=2,\dots ,n\}$ with

${\alpha }_j>0$ for some

$j$ such that

$$\sum _{i=2}^n{\alpha }_i(x_i-x_1)=0.$$
Let

${\displaystyle {\alpha }_1=-\sum _{i=2}^n{\alpha }_i}$. We have

$$\sum _{i=1}^n{\alpha }_i{x}_i=0\text{ and }\sum _{i=1}^n{\alpha }_i=0.$$
Let

$$\mu =min\{\frac{{\lambda }_i}{{\alpha }_i}:{\alpha }_i>0\}$$
and let

${\displaystyle \mu =\frac{{\lambda }_k}{{\alpha }_k}}$ for some

$k$. Then

$${\lambda }_i-\mu {\alpha }_i\ge 0\text{ for all }i$$
and

$${\lambda }_k-\mu {\alpha }_k=0.$$
This implies

$$\begin{array}{rl}x& =\sum _{i=1}^n{\lambda }_i{x}_i=\sum _{i=1}^n{\lambda }_i{x}_i-\mu \sum _{i=1}^n{\alpha }_i{x}_i\\ & =\sum _{i=1}^n({\lambda }_i-\mu {\alpha }_i)x_i.\end{array}$$
Since

${\displaystyle \sum _{i=1}^n({\lambda }_i-\mu {\alpha }_i)=\sum _{i=1}^n\lambda -\mu \sum _{i=1}^n{\alpha }_i=1}$ and

${\lambda }_k-\mu {\alpha }_k=0$, it follows that

$$x\in \text{conv}(X\mathrm{\setminus }\{x_k\}).$$
By induction on

$n$, we obtain the desired result.