Carathéodory theorem
===
###### tags: `Mathematics` `Convex Analysis`
:::info
**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\leq m+1$ such that $x\in \text{conv}(X)$.
:::
:::warning
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_ix_i=0 \text{ and } \sum_{i=1}
^n\alpha_i=0.$$
Let
$$
\mu=\min\left\{ \frac{\lambda_i}{\alpha_i}:\alpha_i>0\right\}
$$
and let $\displaystyle \mu=\frac{\lambda_k}{\alpha_k}$ for some $k$. Then
$$
\lambda_i-\mu \alpha_i\geq 0 \text{ for all } i
$$
and
$$
\lambda_k-\mu \alpha_k= 0.
$$
This implies
\begin{align}
x&=\sum_{i=1}^n\lambda_ix_i=\sum_{i=1}^n\lambda_ix_i-\mu \sum_{i=1}^n\alpha_ix_i\\
&=\sum_{i=1}^n(\lambda_i-\mu\alpha_i)x_i.
\end{align}
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\backslash \{x_k\}).
$$
By induction on $n$, we obtain the desired result.
:::