凸多胞体

凸多胞体（convex polytope）是有限点集的凸包。对点 $v_1,\dots ,v_k\in {ℝ}^n$，它包含全部组合 $$P=\{\sum _{i=1}^k{\lambda }_i{v}_i:{\lambda }_i\ge 0,\sum _i{\lambda }_i=1\}.$$ 二维的凸多边形、三维的有界凸多面体都是例子；线段和单点也是允许的低维多胞体。它与凸多面体的关系是：有限维中，非空凸多胞体恰好是有界凸多面体。

取正方形四顶点 $A=(0,0),B=(2,0),C=(2,2),D=(0,2)$。它们的凸包就是 $[0,2{]}^2$。点 $P=(1,1/2)$ 可写为 $\frac{1}{2}A+\frac{1}{4}B+\frac{1}{4}C$，也可写为 $\frac{3}{8}A+\frac{3}{8}B+\frac{1}{8}C+\frac{1}{8}D$。同一点在多胞体中的凸组合一般不唯一。

多胞体由有限顶点生成；线性目标的接触集合可以是一条边，也可以是一个顶点。

顶点与生成点的区别

若点不能写成集合内两个不同点的严格凸组合，它就是极点，即多胞体的顶点。有限点凸包的每个极点必来自生成点：若 $x$ 有一个使用至少两个不同点且权重严格为正的表示，把其中一个点与其余点的加权平均分开，就得到严格两点凸组合；若 $x$ 为极点，这些正权重点必须都等于 $x$。

但生成点未必都是顶点。给正方形的生成列表添加中心 $(1,1)$，凸包不变，中心也不是新顶点，因为它是 $A,C$ 的中点。有限列表可以冗余；“由这些点生成”与“这些点恰好是顶点”是两个命题。

仿射独立的 $k+1$ 个点生成 $k$ 维单纯形，其重心坐标唯一。正方形四点在二维中仿射相关，所以上面的两组权重并不矛盾。Carathéodory 定理保证二维中总能找到至多三点的表示，却不保证这个三点表示唯一。

有限凸包一定有界

设所有生成点范数不超过 $R$。任意凸组合满足 $\Vert \sum _i{\lambda }_i{v}_i\Vert \le \sum _i{\lambda }_i\Vert v_i\Vert \le R$，所以有界。权重集合是闭有界的标准单纯形，凸组合映射连续，因此像集紧，故也闭。这排除了开多边形、射线和无界楔形。

有限凸包可以用有限个线性不等式描述，这是多胞体的两种表示之间的定理的一侧；在有限维中它与有界多面体表示等价。下面完整证明较直接的另一侧：有界多面体由它的有限个顶点生成。

有界多面体由顶点生成的证明

设非空 $P=\{x:Ax\le b\}$ 有界。先有顶点数有限：每个顶点的活跃法向量张成 ${ℝ}^n$，可从中选择 $n$ 个独立约束；相应等式至多决定一个点，而有限约束只有有限种选择。

任取 $x\in P$。若活跃法向量已张满，它就是顶点。否则选非零 $d$ 与全部活跃法向量正交。有限个不活跃约束的正余量保证沿 $x+td$ 可向正负两侧移动一小段；有界性保证可行参数的最大闭区间为有限的 $[t_{-},t_{+}]$，其中 $t_{-}<0<t_{+}$。

两个端点 $x_{-}=x+t_{-}d$、$x_{+}=x+t_{+}d$ 均在 $P$，并且 $$x=\frac{t_{+}}{t_{+}-t_{-}}{x}_{-}+\frac{-t_{-}}{t_{+}-t_{-}}{x}_{+}.$$ 两权重正且和为一。到达任一端点必新激活一条与 $d$ 不正交的约束，否则还能继续移动；它不在原活跃法向量的张成中，所以活跃秩至少增加一。对端点重复同样分解，每条分支至多增加 $n$ 次就达到顶点。将有限分解树的权重相乘并汇总，得到 $x$ 是顶点的凸组合。

全部顶点本来就在凸集 $P$ 中，故其凸包包含于 $P$；刚证明的反向包含给出等号。有界性在保证两个有限端点处起作用。对射线 $[0,\mathrm{\infty })$，唯一顶点零的凸包只有零，证明不能照搬。

面与线性优化

固定向量 $a$，线性函数在凸组合上的值是顶点值的加权平均。因此在多胞体上最大化时，总能由某个顶点达到最大值；全部最大化点正是达到该最大值的顶点的凸包，构成一个暴露面。

主例方向 $a=(0,1)$ 的最大值为二，接触面为上边 $CD$；方向 $(1,1)$ 的最大值为四，只有顶点 $C$ 达到。变式删去顶点 $D$，得到三角形 $ABC$，原来的点 $(0,1)$ 不再可行，因为三角形要求 $y\le x$。删除一个真正顶点会改变集合，而删除内部的冗余生成点不会。