1. 多面体(Polyhedron)

多面体是一系列线性等式和不等式的解集。

$\mathcal{P}=\{x \mid a_{j}^{T} x \leq b_{j}, j=1, \ldots, m, c_{j}^{T} x=d_{j}, j=1, \ldots, p\}$

向量形式为

$\mathcal{P}= \{x \mid A x \preceq b, C x=d \}$

从定义可以看出，多面体就是超平面和半空间的交集。

有界的多面体称为Polytope。

2. 单纯形(Simplex)

2.1 定义

假设 $k+1$ 个点 $v_0, \ldots, v_k \in R^n$ 仿射独立，即 $v_1-v_0, \ldots, v_k-v_0$ 线性不相关，则与这 $k+1$ 个点相关的单纯形即为这些点的凸包：

$\begin{align} C & = \operatorname{conv}\{v_{0}, \ldots, v_{k}\} \\ & = \{\theta_{0} v_{0}+\cdots+\theta_{k} v_{k} \mid \theta \succeq 0, \mathbf{1}^{T} \theta = 1\} \end{align}$

2.2 例子

以二维空间为例

若给两个不同的点，则构成的单纯形为一条线段
若给三个不同的点，则构成的单纯形为一个三角形
若给四个以上不同的点，则不可能仿射独立，不能构成单纯形

2.3 证明单纯形是多面体

思路：

把单纯形中的点表示成多面体的形式
线性不相关->满秩

设单纯形为 $C$ ，则 $C$ 中的点可表示为

$x=\theta_{0} v_{0}+\theta_{1} v_{1}+\cdots+\theta_{k} v_{k}$

其中 $\theta \succeq 0, \mathbf{1}^{T} \theta = 1$ ，要注意的是 $\theta$ 是可变的，决定了 $x$ 的取值。
对上式进行变换，得

$\begin{align} x &= v_{0}+\theta_{1} (v_{1}-v_{0})+\cdots+\theta_{k} (v_{k}-v_{0})\\ &=v_0 +By \end{align}$

其中

$\begin{align} B & = \left[\begin{array}{lll} v_{1}-v_{0} & \cdots & v_{k}-v_{0} \end{array}\right] \in \mathbf{R}^{n \times k}\\ y & = \left(\theta_{1}, \ldots, \theta_{k}\right) \end{align}$

注意这里的 $y$ 不是 $\theta$ ，少了一个元素。 $y \succeq 0,\mathbf{1}^{T} y \le 1$ 。显然可以用 $y$ 的约束条件来得到对 $x$ 的约束，那么下一步要做的就是把 $y$ 独立出来。

由于 $B$ 中各向量线性无关，则 $rank(B)=k$ ，因此，存在非奇异矩阵 $A=(A_1, A_2) \in R^{n \times n}$ 使得，

$A B=\left[\begin{array}{l} A_{1} \\ A_{2} \end{array}\right] B=\left[\begin{array}{l} I \\ 0 \end{array}\right]$

在 $x$ 的表达式左边乘上矩阵 $A$ ，可得

$A_{1} x=A_{1} v_{0}+y, \quad A_{2} x=A_{2} v_{0}$

代入 $y$ 的约束，可得

$A_{2} x=A_{2} v_{0}, \quad A_{1} x \succeq A_{1} v_{0}, \quad \mathbf{1}^{T} A_{1} x \leq 1+\mathbf{1}^{T} A_{1} v_{0}$

符合多面体的定义，证毕。