多面体与多胞形

形式陈述 ​

在有限维实仿射空间中，多面体（polyhedron）是有限个闭半空间的交。选定仿射坐标后可写成

$$P=\{x\in {\mathbb{R}}^d:Ax\le b\}.$$

多胞形（polytope）是有限点集的凸包公理库凸包Convex hull包含给定点集的最小凸集，是凸几何中的基本包络对象，并可进一步研究其算法构造。：

$$Q=\mathrm{conv}\{v_1,\dots ,v_m\}.$$

本页固定这组英文对应。Minkowski–Weyl 定理说明两种有限描述之间的关系：每个非空多面体都可表示为

$$P=\mathrm{conv}(V)+\mathrm{cone}(R)$$

其中 $V,R$ 为有限集；反之，这样的集合也是多面体。特别地，多面体有界当且仅当它是多胞形。这个结论依赖有限维实线性结构，不能直接当作任意拓扑向量空间中的定义等价。

若线性泛函 $c$ 在 $P$ 上取得最小值 $\alpha$，集合

$$F=\{x\in P:c(x)=\alpha \}$$

称 $P$ 的一个面。零维面是顶点，余维一的真面称 facet。面必须由支撑超平面公理库仿射超平面与半空间Affine hyperplane · Half-space由非零线性泛函的等值集及其两侧不等式区域定义的仿射几何对象。截出，不是任意低维凸子集。

直觉 ​

多面体的 H-表示从“约束”观察对象：每条线性不等式削去空间的一侧，剩余交集就是可行域。多胞形的 V-表示从“生成元”观察对象：有限个顶点通过所有凸组合填出整个形状。Minkowski–Weyl 定理说，在有界情形中，这两种看法描述同一类对象；无界时还必须记录逃向无穷的射线方向。

顶点、边和 facets 不是额外装饰，而是约束与生成描述相遇的位置。某个线性目标在多胞形上若有最优解，至少有一个顶点最优；但最优解也可能铺满一条边或更高维面，因此“最优点必唯一”并不成立。

例子与边界 ​

三角形既是三个顶点的凸包，也是三个适当闭半平面的交。立方体 $[0,1{]}^d$ 由 $2d$ 个坐标不等式给出，也等于其 $2^d$ 个顶点的凸包。条带

$$\{(x,y)\in {\mathbb{R}}^2:0\le y\le 1\}$$

是无界多面体，却不可能是有限点的凸包，因为有限点凸包总有界。第一象限是由 $x\ge 0,y\ge 0$ 给出的多面锥，其射线方向不可从有限顶点列表中恢复。

空集也可由矛盾不等式定义为多面体；若定理使用顶点或 Minkowski–Weyl 的非空表示，必须单独排除它。低维对象同样允许存在于高维环境，例如 ${\mathbb{R}}^3$ 中的平面三角形。维数应取其仿射包的维数，而不是环境维数。

不同文献偶尔交换 polyhedron 与 polytope 的中文译法，或把 polyhedron 限定为有界对象。页面和后续算法必须沿用开头约定。也不能把任意凸集公理库凸集Convex set任意两点间线段全部包含在集合中的向量空间子集。都称为多面体：圆盘需要无限多个支撑方向，不能由有限线性不等式精确描述。

推论与应用 ​

线性规划公理库线性规划Linear programming · LP在线性等式和不等式约束下优化线性目标函数的问题。以多面体为可行域；单纯形法公理库单纯形法Simplex method沿可行多面体顶点与边枢轴移动求解线性规划的方法。沿顶点和边移动寻找更优基可行解。退化、无界和不可行分别对应不同的面结构，不能用“总会走到唯一顶点”概括。组合优化常把离散可行解取凸包，再研究其 facets 是否给出紧的线性描述。

在计算几何公理库计算几何问题Computational geometry problem以点、线段、多边形等几何对象为输入并要求组合或数值几何输出的问题族。中，H/V 转换、面枚举、半空间交与凸包算法互为对偶视角。Carathéodory 定理公理库Carathéodory 定理Caratheodory theorem in convex geometry有限维凸包中的每个点都可由至多维数加一个原集合点的凸组合表示。限制单个凸组合所需的点数，Helly 定理公理库Helly 定理Helly theorem欧氏 d 维空间中有限凸集族的全局非空交可由至多 d 加一个集合的局部交保证。控制有限凸约束的交；这些是建立在多面体语言之上的后续定理，不属于本页的对象定义。

参考资料

• Günter M. Ziegler, Lectures on Polytopes, Springer, 1995, Ch. 1, H- and V-representations, faces, and polytopes.
• Alexander Schrijver, Theory of Linear and Integer Programming, Wiley, 1986, Chs. 7–8, polyhedra and the Weyl–Minkowski theorem.