凸多面体

凸多面体（convex polyhedron）是有限个闭半空间的交集。在线性代数形式下，它可写为 $$P=\{x\in {ℝ}^n:Ax\le b\},$$ 不等式按分量理解。等式可用一对相反的不等式表示。这个定义允许空集、低维集合和无界集合；在高维凸分析中，它不局限于有体积的三维实体。

例如平面区域 $$x\ge 0,y\ge 0,x+y\le 4,y\le 2$$ 是一个凸多面体，其四个顶点为 $(0,0),(4,0),(2,2),(0,2)$。每个约束是一侧半平面，交集保留同时满足所有约束的点。

顶点处独立的活跃边界限制全部可动方向；边内点仍能沿边双向移动。

凸性、闭性与活跃约束

每个闭半空间凸且闭，有限交仍凸且闭。也可直接验证：若 $Ax,Ay\le b$，对 $0\le t\le 1$ 有 $A(tx+(1-t)y)\le tb+(1-t)b=b$。含严格不等式的开三角形因此通常不属于本文的闭半空间定义；它的闭包才是相应闭凸多面体。

将第 $i$ 行写为 $a_i^{𝖳}x\le b_i$。在某个可行点 $x_0$ 取等号的约束称为活跃约束。主例点 $(2,2)$ 激活 $x+y=4$ 与 $y=2$；点 $(1,2)$ 只激活后一条。活跃约束不是“对所有点都等号”，而是相对于当前点定义。

顶点的秩判别及证明

定理　可行点 $x_0\in P\subseteq {ℝ}^n$ 是极点，当且仅当它的活跃约束法向量张成 ${ℝ}^n$。极点在多面体语境中也称顶点。

若活跃法向量不张满，选非零 $d$ 与它们全都正交。活跃约束在 $x_0\pm td$ 处仍取等号；不活跃约束有严格正余量，因为约束只有有限条，可取足够小的共同 $t>0$，使 $t|a_i^{𝖳}d|$ 不超过各自余量。于是两点都可行、彼此不同，$x_0$ 是它们中点，不是极点。

反向，假设活跃法向量张满，而 $x_0=\theta u+(1-\theta )v$，其中 $u,v\in P$、$0<\theta <1$。每条活跃约束满足 $b_i=\theta a_i^{𝖳}u+(1-\theta )a_i^{𝖳}v$，两项都不超过 $b_i$，所以必须各自等于 $b_i$。于是 $a_i^{𝖳}(u-v)=0$ 对全部活跃约束成立；张满条件迫使 $u=v$，从而 $x_0$ 为极点。

主例 $(2,2)$ 的两个法向量 $(1,1)$ 与 $(0,1)$ 独立，因此是顶点。边内点 $(1,2)$ 可沿 $d=(1,0)$ 向两侧移动，例如它是 $(1/2,2)$ 与 $(3/2,2)$ 的中点，故不是顶点。这些判断由秩与余量给出，不依赖图是否画得像一个角。

无界方向与衰退锥

对非空多面体，向量 $d$ 使每个 $x\in P$ 沿 $x+td$、$t\ge 0$ 都保持可行，当且仅当 $Ad\le 0$。充分性由 $A(x+td)=Ax+tAd\le b$ 得到；必要性若某行 $a_i^{𝖳}d>0$，从任一可行点沿它走得足够远就违反该行约束。所有这样的方向构成衰退锥。

主例的衰退条件为 $d_x\ge 0,d_y\ge 0,d_x+d_y\le 0,d_y\le 0$，只有零向量，区域有界。变式删除 $x+y\le 4$，得到 $x\ge 0,0\le y\le 2$ 的无界条带；其衰退锥为 $\{(t,0):t\ge 0\}$。它仍是凸多面体，却不是有限点集的凸包，不能与凸多胞体混同。

不同表示与整数性

同一多面体可以有多种不等式表示。给主例添加 $x\le 5$ 不改变集合，因为已有约束推出 $x\le 4$；它是冗余约束。低维集合也可表示，例如 $x\ge 0,x\le 0,0\le y\le 1$ 是纵轴上的线段，活跃秩判别仍适用。

系数为整数不保证顶点为整数。区间 $\{x:0\le 2x\le 1\}$ 的顶点之一是 $1/2$。在整数规划中，线性约束描述的连续多面体与要求变量取整数后的可行点集是不同对象；判断其顶点整数性需要额外结构，而非只看系数写成整数。