跳转至

傅里葉-莫茨金消元法

引入

傅里葉——莫茨金消元法（原名 Fourier–Motzkin Elimination，簡稱 FME 算法）是一種用於從線性不等式中消除變量的數學方法。

它的命名源自於在 1827 年和 1936 年獨立發現該算法的 Joseph Fourier 和 Theodore Motzkin 的姓氏。

過程

從線性不等式中消除一組變量，是指通過將關係式中的若干個元素有限次地變換，消去其中的某些元素，從而解決問題的一種方法。

如果線性不等式中的所有變量都被消除，那麼我們會得到一個常不等式。因為當且僅當原不等式有解時，消元后的不等式才為真，消除所有變量可用於檢測不等式系統是否有解。

考慮一個含 \(n\) 個不等式的系統 \(S\)，有從 \(x_{1}\) 到 \(x_{r}\) 的 \(r\) 個變量，其中 \(x_{r}\) 為要消除的變量。根據 \(x_r\) 係數的符號（正、負或空），\(S\) 中的線性不等式可以分為三類：

  1. 形式為 \(x_{r}\geq b_{i}-\sum _{k=1}^{r-1}a_{ik}x_{k}\) 的不等式，對於範圍從 \(1\) 到 \(n_{A}\)（\(n_{A}\) 為這種不等式的數量）的 \(j\)，用 \(x_{r}\geq A_{j}(x_{1},\dots ,x_{r-1})\) 表示；
  2. 形式為 \(x_{r}\leq b_{i}-\sum _{k=1}^{r-1}a_{ik}x_{k}\) 的不等式，對於範圍從 \(1\) 到 \(n_{B}\)（\(n_{B}\) 為這種不等式的數量）的 \(j\)，用 \(x_{r}\leq B_{j}(x_{1},\dots ,x_{r-1})\) 表示；
  3. 不包含 \(x_{r}\) 的不等式，設它們構成的不等式組為 \(\phi\)。

因此原系統等價於

\[ \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}))\wedge \phi \]

消元包括產生一個等價於 \(\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}))\wedge \phi \]

不等式

\[ \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\)。

例題

考慮以下不等式系統：

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

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

\(-x+5y-2z \leq -7\)

\(-3x+2y+6z \leq 12\)

為了消除 \(x\)，我們可以根據 \(x\) 改寫不等式：

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

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

\(x \geq 7 + 5y - 2z\)

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

這樣我們得到兩個 \(\leq\) 不等式和兩個 \(\geq\) 不等式；如果每個 \(\leq\) 不等式的右側至少是每個 \(\geq\) 不等式的右側，則系統有一個解。我們有 \(2\times2\) 這樣的組合：

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

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

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

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

現在我們有了一個新的少了一個變量不等式系統。

時間複雜度

在 \(n\) 個不等式上消元可以最多得到 \(n^{2}/4\) 個不等式，因此連續運行 \(d\) 步可以得到最多 \(4(n/4)^{2^{d}}\) 的雙指數複雜度。這是由於算法產生了許多不必要的約束（其他約束隱含的約束）。必要約束的數量以單一指數增長。

可以使用線性規劃 (Linear Programming, LP) 檢測不必要的約束。

應用

信息論的可實現性證明保證了存在性能良好的編碼方案的條件。這些條件通常使用線性不等式系統描述。系統的變量包括傳輸速率和附加輔助速率。通常，人們旨在僅根據問題的參數（即傳輸速率）來描述通信的基本限制，因此述輔助率需要消除上。而我們正是通過傅立葉 - 莫茨金消元法來做到這一點的。

實現

在編程語言中，Racket，一種基於 Lisp 的多範式編程語言在 fme - Fourier–Motzkin Elimination for Integer Systems) 中對 FME 算法做了簡單函數代數實現。

參考資料與拓展閲讀

  1. Rui-Juan Jing, Marc Moreno-Maza, Delaram Talaashrafi, "Complexity Estimates for Fourier-Motzkin Elimination", Journal of Functional Programming 16:2 (2006) pp 197-217.
  2. Fourier–Motzkin elimination - Wikipedia
  3. Fourier-Motzkin elimination and its dual
  4. GE Liepins,Fourier-Motzkin elimination for mixed systems, 1983
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用