傅里叶-莫茨金消元法

引入

傅里叶——莫茨金消元法（原名 Fourier–Motzkin Elimination，简称 FME 算法）是一种用于从线性不等式中消除变量的数学方法。

它的命名源自于在 1827 年和 1936 年独立发现该算法的 Joseph Fourier 和 Theodore Motzkin 的姓氏。

过程

从线性不等式中消除一组变量，是指通过将关系式中的若干个元素有限次地变换，消去其中的某些元素，从而解决问题的一种方法。

如果线性不等式中的所有变量都被消除，那么我们会得到一个常不等式。因为当且仅当原不等式有解时，消元后的不等式才为真，消除所有变量可用于检测不等式系统是否有解。

考虑一个含 $n$ 个不等式的系统 $S$ ，有从 $x_{1}$ 到 $x_{r}$ 的 $r$ 个变量，其中 $x_{r}$ 为要消除的变量。根据 $x_{r}$ 系数的符号（正、负或空）， $S$ 中的线性不等式可以分为三类：

形式为 $x_{r} \geq b_{i} - \sum_{k = 1}^{r - 1} a_{i k} x_{k}$ 的不等式，对于范围从 $1$ 到 $n_{A}$ （ $n_{A}$ 为这种不等式的数量）的 $j$ ，用 $x_{r} \geq A_{j} (x_{1}, \dots, x_{r - 1})$ 表示；
形式为 $x_{r} \leq b_{i} - \sum_{k = 1}^{r - 1} a_{i k} x_{k}$ 的不等式，对于范围从 $1$ 到 $n_{B}$ （ $n_{B}$ 为这种不等式的数量）的 $j$ ，用 $x_{r} \leq B_{j} (x_{1}, \dots, x_{r - 1})$ 表示；
不包含 $x_{r}$ 的不等式，设它们构成的不等式组为 $ϕ$ 。

因此原系统等价于

max (A_{1} (x_{1}, \dots, x_{r - 1}), \dots, A_{n_{A}} (x_{1}, \dots, x_{r - 1})) \leq x_{r} \leq min (B_{1} (x_{1}, \dots, x_{r - 1}), \dots, B_{n_{B}} (x_{1}, \dots, x_{r - 1})) \land ϕ

消元包括产生一个等价于 $\exists x_{r} S$ 的系统。显然，这个公式等价于

max (A_{1} (x_{1}, \dots, x_{r - 1}), \dots, A_{n_{A}} (x_{1}, \dots, x_{r - 1})) \leq min (B_{1} (x_{1}, \dots, x_{r - 1}), \dots, B_{n_{B}} (x_{1}, \dots, x_{r - 1})) \land ϕ

不等式

max (A_{1} (x_{1}, \dots, x_{r - 1}), \dots, A_{n_{A}} (x_{1}, \dots, x_{r - 1})) \leq min (B_{1} (x_{1}, \dots, x_{r - 1}), \dots, B_{n_{B}} (x_{1}, \dots, x_{r - 1}))

等价于对于 $1 \leq i \leq n_{A}$ 且 $1 \leq j \leq n_{B}$ ，所有 $n_{A} n_{B}$ 个不等式 $A_{i} (x_{1}, \dots, x_{r - 1}) \leq B_{j} (x_{1}, \dots, x_{r - 1})$ 构成的不等式组。

因此，我们将原系统 $S$ 转换为另一个消掉 $x_{r}$ 的系统，这个系统有 $(n - n_{A} - n_{B}) + n_{A} n_{B}$ 个不等式。特别地，如果 $n_{A} = n_{B} = n / 2$ ，那么新系统不等式的个数为 $n^{2} / 4$ 。

例题

考虑以下不等式系统：

$2 x - 5 y + 4 z \leq 10$

$3 x - 6 y + 3 z \leq 9$

$- x + 5 y - 2 z \leq - 7$

$- 3 x + 2 y + 6 z \leq 12$

为了消除 $x$ ，我们可以根据 $x$ 改写不等式：

$x \leq (10 + 5 y - 4 z) / 2$

$x \leq (9 + 6 y - 3 z) / 3$

$x \geq 7 + 5 y - 2 z$

$x \geq (- 12 + 2 y + 6 z) / 3$

这样我们得到两个 $\leq$ 不等式和两个 $\geq$ 不等式；如果每个 $\leq$ 不等式的右侧至少是每个 $\geq$ 不等式的右侧，则系统有一个解。我们有 $2 \times 2$ 这样的组合：

$7 + 5 y - 2 z \leq (10 + 5 y - 4 z) / 2$

$7 + 5 y - 2 z \leq (9 + 6 y - 3 z) / 3$

$(- 12 + 2 y + 6 z) / 3 \leq (10 + 5 y - 4 z) / 2$

$(- 12 + 2 y + 6 z) / 3 \leq (9 + 6 y - 3 z) / 3$

现在我们有了一个新的少了一个变量不等式系统。

时间复杂度

在 $n$ 个不等式上消元可以最多得到 $n^{2} / 4$ 个不等式，因此连续运行 $d$ 步可以得到最多 $4 (n / 4)^{2^{d}}$ 的双指数复杂度。这是由于算法产生了许多不必要的约束（其他约束隐含的约束）。必要约束的数量以单一指数增长。

可以使用线性规划 (Linear Programming, LP) 检测不必要的约束。

应用

信息论的可实现性证明保证了存在性能良好的编码方案的条件。这些条件通常使用线性不等式系统描述。系统的变量包括传输速率和附加辅助速率。通常，人们旨在仅根据问题的参数（即传输速率）来描述通信的基本限制，因此述辅助率需要消除上。而我们正是通过傅立叶 - 莫茨金消元法来做到这一点的。

实现

在编程语言中，Racket，一种基于 Lisp 的多范式编程语言在 fme - Fourier–Motzkin Elimination for Integer Systems) 中对 FME 算法做了简单函数代数实现。

参考资料与拓展阅读

Rui-Juan Jing, Marc Moreno-Maza, Delaram Talaashrafi, "Complexity Estimates for Fourier-Motzkin Elimination", Journal of Functional Programming 16:2 (2006) pp 197-217.
Fourier–Motzkin elimination - Wikipedia
Fourier-Motzkin elimination and its dual
GE Liepins,Fourier-Motzkin elimination for mixed systems, 1983

本页面最近更新：2023/6/27 13:39:08，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Tiphereth-A, Enter-tainer, hbghlyj, iamtwz, isdanni, sshwy, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用