Carathéodory 定理 | Codeboy's Blog

形式陈述

设 $S\subseteq\mathbb R^d$ 。若

x\in\operatorname{conv}(S),

则存在 $S$ 中至多 $d+1$ 个点 $s_0,\ldots,s_d$ ，使

x\in\operatorname{conv}\{s_0,\ldots,s_d\}.

更精确地，若 $S$ 的仿射包维数为 $r$ ，则只需至多 $r+1$ 个点。集合 $S$ 可以无限；凸包的定义本来就只使用有限凸组合，所以定理限制的是表示一个给定点所需的证人数量。

证明从任意有限表示

x=\sum_{i=1}^{m}\lambda_i s_i,\qquad \lambda_i\ge0,\qquad \sum_{i=1}^{m}\lambda_i=1

开始。若 $m>r+1$ ，齐次化向量 $(s_i,1)$ 不再线性无关；等价地，这些点仿射相关，故存在不全为零的实数 $\mu_i$ 满足

\sum_i\mu_i s_i=0,\qquad \sum_i\mu_i=0.

把 $\mu$ 整体变号后可假设某个 $\mu_i>0$ ，并令

t=\min_{\mu_i>0}\frac{\lambda_i}{\mu_i}.

新系数 $\lambda_i'=\lambda_i-t\mu_i$ 仍非负、和为一，而且表示同一个 $x$ ；至少一个正系数变成零。删去该项并重复，最终只剩至多 $r+1$ 项。每一步都可核验地保持凸组合，而不是仅用“去掉冗余点”的图形直觉。

直觉

在 $r$ 维仿射空间中，超过 $r+1$ 个点必有仿射冗余。沿一条系数和为零、加权点和也为零的方向移动凸组合系数，不会改变所表示的点；把移动量推到首次碰到系数零的位置，就能删除一个点而不离开概率单纯形。

定理不是说整个凸包只由同一组 $d+1$ 个点生成。不同的 $x$ 可以需要不同证人；它只把每个点的局部表示复杂度限制在环境维数以内。

例子与边界

在平面中，任意凸包点都落在原集合某三个点的三角形内；若该点位于一条弦上，只需两个端点。单位正方形中心可写成一条对角线两端点的平均，因此实际证人数可以小于上界。

上界一般不能改成 $d$ 。取 $\mathbb R^d$ 中一个非退化 $d$ -单纯形的 $d+1$ 个顶点，任一内部点都有全部重心坐标严格为正；若删去一个顶点，只剩一个真面，其凸包不含该内部点。由此 $d+1$ 是锐利界。

有限维假设不能无条件删除。无限维向量空间中，一个点仍由某个有限凸组合表示，但不存在统一的“维数加一”常数控制所有点。系数非负和总和为一也不可省略；允许任意仿射组合得到的是仿射包，允许任意线性组合则得到线性张成。

推论与应用

Carathéodory 定理为凸几何提供小证书：判断点属于高维凸包时，总有一个至多 $d+1$ 点的见证。对有限点生成的多胞形，它限制单个点所需的顶点数，也解释线性规划基本解为何由有限个活跃方向控制。

本定理与Radon 定理都由仿射相关性驱动：前者沿相关方向消去凸组合项，后者按相关系数的正负把点集分成两个凸包相交的部分。二者结论不同，不能把“少量点表示”与“两个凸包相交”合并成一句同义口号。

参考资料

Alexander Barvinok, A Course in Convexity, American Mathematical Society, 2002, Ch. 1, Carathéodory’s theorem.
Jiří Matoušek, Lectures on Discrete Geometry, Springer, 2002, Ch. 1, convexity theorems.