多面体

这篇文章介绍一些与多面体有关的知识. 阅读本文前, 你需要懂得线性代数的基础内容, 并最好已经读过本站的单纯形法教程.

你可以不必从头到尾读完这篇文章. 本站的其他多面体优化教程中会有大量链接, 将你引向本文对应的部分.

多面体的定义

定义 1. 一个多面体是形如 \(\{ x\in\mathbb{R}^n \mid Ax\leq b \}\) 的集合, 其中 \(A\) 是一个 \(m\) 行 \(n\) 列的矩阵. 这称为多面体的 H-表示.

例如, 一个三角形是一个 2 维的多面体. 拿顶点在 \((0, 0)\), \((0, 1)\), \((1, 0)\) 的直角三角形为例, 我们可以将它写作:

\[ \begin{align*} -x &\leq 0 \\ -y &\leq 0 \\ x+y &\leq 1 \end{align*} \]

换成矩阵的写法, 则是

\[ \begin{pmatrix} -1 & 0 \\ 0 & -1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} \leq \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \]

所以, 我们可以将 \(Ax\leq b\) 看成是 \(m\) 个不等式构成的不等式组.

我们再看看前面的三个不等式. \(-x \leq 0\) 说明整个三角形在 x 轴之上; \(-y \leq 0\) 说明整个三角形在 y 轴右边; \(x+y\leq 1\) 说明三角形在 \(y=1-x\) 这条线的下面. 换言之, 每个不等式都把整个二维空间切割成了两半, 而整个三角形都在其中的半边. 因此, 每个不等式都指明了一个半空间 (halfspace); 这就是 H-表示中字母 H 的来源.

值得注意的是, 矩阵 \(A\) 的行向量是每个半空间的分界面的法向量. 证明是显然的.

定义 2. 多面体的顶点是无法由多面体内的其他两点凸组合而成的点.

等价地, 对于一个 \(d\) 维多面体, 顶点是使得 \(Ax\leq b\) 中的 \(d\) 个线性无关的不等式取得等号的点. 这些不等式被称为在顶点处活跃 (active) 的不等式. 在单纯形法中, 我们证明了基解和顶点一一对应, 那里的证明方法和这里是类似的.

证明. 假设 \(V\) 使得 \(d\) 个线性无关的不等式取得等号. 假如存在 \(V_1\), \(V_2\) 与 \(\lambda\in [0,1]\) 使得 \(V=\lambda V_1 + (1-\lambda)V_2\), 那么 \(V_1\), \(V_2\) 在那些不等式处一定也会取得等号. 由于这些等式线性无关, 所以只有唯一解, 进而 \(V = V_1 = V_2\).

假设 \(V\) 使得 \(m < d\) 个线性无关的不等式取得等号, 那么满足这 \(m\) 个等式的向量至少构成了 \(d-m\) 维空间. 我们只需要在其中取合适的 \(v\), 使得 \(V+\varepsilon v\) 和 \(V - \varepsilon v\) 都在多面体内部, 就能说明 \(V\) 不是顶点.

定义 3. 一个点集的凸包 (convex hull) 是最小的包含它们的凸集. 一个向量集合 \(\{ v_i \}\) 的锥包 (conical hull) 是

\[ \left\{ \sum \lambda_i v_i \mid \lambda_i\geq 0 \right\} \]

我们只考虑有限个向量构成的的锥包, 这时, 它就是我们几何直观上的锥. 这里的 \(v_i\) 被称作 rays, 我并没有看到令我满意的翻译, 不过有时叫做生成射线或极向量. 可以直接将它理解为锥的"棱".

定义 1'. 一个多面体是它顶点的凸包和极向量的锥的并.

这被称为多面体的 V-表示, 其中 V 来自顶点 (vertex).

这个定义和定义 1 是等价的, 这被称为 Minkowski-Weyl 定理. 我们在这里只说明比较简单的情况: 多面体 \(\{x \mid Ax \geq 0\}\) 和 \(\{x \mid x = R\lambda , \lambda \geq 0\}\) 是等价的 (后者就是换了个写法的锥包, 其中 \(R\) 是 \(v_i\) 构成的矩阵).

想从 V-表示转换到 H-表示, 就意味着我们需要在给定 \(R\) 的情况下, 消去那些参数 \(\lambda\), 从而得到 \(A\). 这可以直接使用 Fourier-Motzkin 消元法完成. 它不会引入新的常数, 所以最终的结果确实可以写作 \(Ax\leq 0\) 的形式. 这就完成了一个方向的证明.

我们称上面所描述的 \((A, R)\) 是一个双重描述对 (double description pair), 或者直接称为 DD 对. 严格来说, \((A, R)\) 是一个 DD 对, 当且仅当 \(\{x\mid Ax \geq 0\} = \{x \mid x = R\lambda, \lambda\geq 0\}\).

对于另一个方向, 我们声明: 如果 \((A, R)\) 是一个 DD 对, 那么 \((R^T, A^T)\) 也是. 证明如下:

设原本的锥体是 \(C\), 我们定义它的极锥 \(C^\circ\):

\[ C^\circ = \{ y\mid \forall x\in C, \langle y, x\rangle \leq 0\} \]

既然我们知道 \(C\) 中的每个元素都是 \(R\) 列向量的线性组合, 那么要让 \(\langle y, x \rangle \leq 0\), 只需要让它和每个列向量的内积都不大于零即可. 也就是说, \(C^\circ = \{ y\mid \forall R_i, \langle y, R_i\rangle \leq 0\}\), 或者换种写法, \(C^\circ = \{ y\mid R^Ty \leq 0 \}\).

此外, 根据 \(C^\circ\) 的定义, 它的极向量就是 \(A\) 的行向量, 所以根据定义 1', 它可以写作 \(\{y\mid y = -A^T\lambda, \lambda\geq 0\}\). 这就说明了 \((R^T, A^T)\) 是一个 DD 对.

所以在给定 \(A\) 的情况下, 我们可以直接利用刚刚的方法来求出 \(R\).

这种转换可以在只知道多面体 \(P = \{x\mid Ax\leq b\}\) 的情况下, 给出多面体的顶点, 所以十分有用. 然而, 我们刚刚的转换方式主要依靠 F-M 消元法, 而它最坏是指数级的. 我们需要更高效的算法.

双重描述法

双重描述法 (double description method) 是在给定 \(A\) 的情况下尝试求出 \(R\) 的算法.

假设 \(K\subseteq [1,m]\cap \mathbb{Z}\) 是 \(A\) 行向量下标构成的集合, 而 \(A_K\) 是由 \(A\) 的行向量构成的子矩阵. 如果我们已经找出了与 \(A_K\) 对应的 \(R\), 我们可以向 \(K\) 中加入一个元素 \(i\), 并求出 \(A_{K\cup \{i\}}\) 所对应的 \(R'\). 换言之, 我们一个一个地加入不等式, 每次加入时, 都计算出多面体新的棱 (极向量). 最开始的情况可以是加入 0 个不等式的情况, 此时这个多面体就是 \(\mathbb{R}^n\) (\(n\) 是维数).

对于已有的 \(R\), 我们可以将它分成三部分:

\[ \begin{align*} J^+ &= \{j\mid A_ir_j > 0\} \\ J^0 &= \{j\mid A_ir_j = 0\} \\ J^- &= \{j\mid A_ir_j < 0\} \\ \end{align*} \]

这里的 \(i\) 就是我们向 \(A\) 中加入的行向量的下标, 而 \(r_j\) 则是 \(R\) 的第 \(j\) 列 (也就是第 \(j\) 条极向量). 从几何意义上来说, \(J^-\) 中的向量都不满足新加入的不等式, 而 \(J^+\) 中的向量则都满足. 在新的 \(R\) 中, 我们需要保留 \(J^+\) 和 \(J^0\), 而对于 \(J^-\), 我们需要计算出一些新的极向量.

考虑 \(j\in J^+\) 和 \(j'\in J^-\), 那么 \(r_j\) 和 \(r_{j'}\) 所张成的平面, 应当和新加入的不等式 \(A_ix\geq 0\) 的分界面 \(A_ix = 0\) 有一条交线. 这说明存在 \(\alpha, \beta\) 使得 \(\alpha r_j + \beta r_{j'} = r_k\), 且 \(A_ir_k = 0\). 将后者带入前者, 就有 \(\alpha A_ir_j = -\beta A_ir_{j'}\), 所以令 \(\alpha = -A_ir_{j'}, \beta = A_ir_j\) 即可. 总而言之, 这条交线可以被这个方程给出:

\[ r_k = (A_ir_j)r_{j'} - (A_ir_{j'})r_j \]

对 \(J^+\times J^-\) 中所有的向量对都计算出这样的 \(r_k\), 我们就得到了新的 \(R\). 这就是双重描述法的工作流程.

不过, 上面的内容只考虑了多面体是 \(P = \{x\mid Ax\geq 0\}\) 的情况. 对于更一般的 \(P = \{x\mid Ax\geq b\}\), 我们可以将它写作 \(P' = \{(x, 1)\mid A'x\geq 0\}\) (类似图形学中的齐次坐标), 然后再进行上述变换.

切锥

定义 4. \(n\) 维多面体 \(P = \{x\mid Ax\leq b\}\) 顶点 \(u\) 处的切锥 (tangent cone) \(K_u\) 是 \(\{ d\in \mathbb{R}^n \mid \exists \varepsilon > 0, u+\varepsilon\in P \}\).

直观上说, 在顶点 \(u\) 处, 沿着某些方向走一小段会留在多面体内, 而沿着其他方向走则会离开多面体. 所有能"留在多面体内"的方向构成的锥, 就是 \(u\) 处的切锥.

定义 4'. 设多面体 \(P = \{x\mid Ax\leq b\}\) 的顶点 \(u\) 处, 活跃的不等式的下标是 \(I = \{i\mid A_iu = b\}\). 那么, 在顶点 \(u\) 处的切锥是 \(\{x\mid \forall i\in I, A_ix\leq 0\}\).

这两个定义是等价的, 这也很好理解: 既然 \(A_iu = b\), 沿着某个方向从 \(u\) 走到 \(u'\) 时, 如果还要留在多面体内, 必然不能增加 \(A_iu'\) 的值. 所以, 对每一个 \(A_i\) 都满足这个条件的方向就是我们所需要的.

有的时候, 我们想要这个切锥的顶点在 \(u\) 处, 而不是在原点. 这时, 直接给其中的所有元素加上 \(u\) 就可以了.

单纯锥

定义 5. 如果一个 \(n\) 维的锥有恰好 \(n\) 个线性无关的极向量, 那么它是一个单纯锥 (simplicial cone).

锥都可以切分为单纯锥, 就跟多边形都可以切分成三角形一样. 即使是对于一般的锥而言, 这种切分依然叫做三角切分 (triangulation).

一种切分的方法是先用一个平面去截这个锥, 得到一个平面上的多边形, 我们可以求出它的顶点. 接下来, 我们对这个多边形进行三角切分, 然后再把它重新映射回原来的锥中. 多边形的三角切分有十分成熟的算法, 例如 Delaunay 切分, 在这里就不做介绍.

我是 AdUhTkJm. 文中如有错漏, 请在 Issues 中指出.