Элиминация Фурье – Моцкина

Исключение Фурье-Моцкина , также известное как метод FME , представляет собой математический алгоритм исключения переменных из системы линейных неравенств . Он может выводить реальные решения.

Алгоритм назван в честь Жозефа Фурье. предложивший этот метод в 1826 году, и Теодор Моцкин, заново открывший его в 1936 году.

Устранение

Исключение набора переменных, скажем V , из системы отношений (в данном случае линейных неравенств) означает создание другой системы того же типа, но без переменных из V , такой, что обе системы имеют одинаковые решения в остальные переменные.

Если из системы линейных неравенств исключить все переменные, то получится система постоянных неравенств. Тогда тривиально решить, является ли полученная система истинной или ложной. Это верно тогда и только тогда, когда исходная система имеет решения. Как следствие, исключение всех переменных можно использовать для определения того, имеет ли система неравенств решения или нет.

Рассмотрим систему $S$ из $n$ неравенства с $r$ переменные $x_{1}$ к $x_{r}$, с $x_{r}$ переменная, которую необходимо исключить. Линейные неравенства в системе можно сгруппировать в три класса в зависимости от знака (положительного, отрицательного или нулевого) коэффициента при $x_{r}$.

• те неравенства, которые имеют вид $x_{r}\geq b_{i}-\sum _{k=1}^{r-1}a_{ik}x_{k}$; обозначим их через $x_{r}\geq A_{i}(x_{1},\dots ,x_{r-1})$, для $i$ от 1 до $n_{A}$ где $n_{A}$ – число таких неравенств;
• те неравенства, которые имеют вид $x_{r}\leq b_{i}-\sum _{k=1}^{r-1}a_{ik}x_{k}$; обозначим их через $x_{r}\leq B_{i}(x_{1},\dots ,x_{r-1})$, для $i$ от 1 до $n_{B}$ где $n_{B}$ – число таких неравенств;
• те неравенства, в которых $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}))$

эквивалентно $n_{A}n_{B}$ неравенства $A_{i}(x_{1},\dots ,x_{r-1})\leq B_{j}(x_{1},\dots ,x_{r-1})$, для $1\leq i\leq n_{A}$ и $1\leq j\leq n_{B}$.

Поэтому мы преобразовали исходную систему в другую систему, в которой $x_{r}$ устраняется. Обратите внимание, что система вывода имеет $(n-n_{A}-n_{B})+n_{A}n_{B}$ неравенства. В частности, если $n_{A}=n_{B}=n/2$, то количество выходных неравенств равно $n^{2}/4$.

Пример

Рассмотрим следующую систему неравенств:

${\begin{cases}2x-5y+4z\leqslant 10\\3x-6y+3z\leqslant 9\\-x+5y-2z\leqslant -7\\-3x+2y+6z\leqslant 12\\\end{cases}}$

Поскольку все неравенства имеют одинаковую форму (все меньше или все больше), мы можем проверить знаки коэффициентов для каждой переменной. Устранение x приведет к получению 2*2 = 4 неравенств для оставшихся переменных, как и исключение y. Устранение z даст только 3*1 = 3 неравенства, поэтому вместо этого мы используем его.

${\begin{cases}z\leqslant {\frac {10-2x+5y}{4}}\\z\leqslant {\frac {9-3x+6y}{3}}\\{\frac {7-x+5y}{2}}\leqslant z\\z\leqslant {\frac {12+3x-2y}{6}}\\\end{cases}}$

что дает 3 неравенства:

${\begin{cases}{\frac {7-x+5y}{2}}\leqslant {\frac {10-2x+5y}{4}}\\{\frac {7-x+5y}{2}}\leqslant {\frac {9-3x+6y}{3}}\\{\frac {7-x+5y}{2}}\leqslant {\frac {12+3x-2y}{6}}\\\end{cases}}$

Упрощение:

${\begin{cases}5y\leqslant -4\\x+y\leqslant -1\\-6x+17y\leqslant -9\\\end{cases}}$

В этой системе используются только 2 переменные вместо 3. Проверка знаков коэффициентов для каждой переменной дает все положительные результаты для y, поэтому мы можем сразу сказать, что система неограничена по y: поскольку все коэффициенты y положительны, а все неравенства меньше -или равно, установка y равным отрицательной бесконечности (или любому достаточно большому отрицательному числу) удовлетворит приведенную систему, поэтому существуют соответствующие x и z и для более крупных систем, и таких решений бесконечно много. Например, установка y = -1000000, x = 0, z = -2222222 удовлетворяет как исходной системе, так и сокращенным.

Сложность

Выполнение этапа исключения $n$ неравенства могут привести не более чем к $n^{2}/4$ неравенства в выпуске, таким образом, наивно работая $d$ последующие шаги могут привести не более чем к $4(n/4)^{2^{d}}$, двойная экспоненциальная сложность. Это связано с тем, что алгоритм создает множество избыточных ограничений, подразумеваемых другими ограничениями.

Макмаллена Теорема о верхней границе , согласно которой количество неизбыточных ограничений растет по одной экспоненте. Единая экспоненциальная реализация исключения Фурье-Моцкина и оценки сложности приведены в.

линейное программирование Хорошо известно, что дает решения для систем неравенств за полиномиальное время, предпочитая его методу исключения Фурье-Моцкина.

Теоремы Имберта об ускорении

Две теоремы об «ускорении» Имберта позволяют исключить избыточные неравенства, основанные исключительно на синтаксических свойствах дерева вывода формул, тем самым сокращая необходимость решения линейных программ или вычисления рангов матриц.

Определите историю $H_{i}$ неравенства $i$ как набор индексов неравенств исходной системы $S$ используется для производства $i$. Таким образом, $H_{i}=\{i\}$ для неравенств $i\in S$ исходной системы. При добавлении нового неравенства $k:A_{i}(x_{1},\dots ,x_{r-1})\leq B_{j}(x_{1},\dots ,x_{r-1})$ (путем устранения $x_{r}$), новая история $H_{k}$ построен как $H_{k}=H_{i}\cup H_{j}$.

Предположим, что переменные $O_{k}=\{x_{r},\ldots ,x_{r-k+1}\}$ были официально ликвидированы. Каждое неравенство $i$ разделяет набор $O_{k}$ в $E_{i}\cup I_{i}\cup R_{i}$:

• $E_{i}$, набор эффективно исключенных переменных, т.е. намеренно. Переменная $x_{j}$ находится в наборе, как только хотя бы одно неравенство в истории $H_{i}$ из $i$ результате устранения $x_{j}$.
• $I_{i}$, набор неявно исключенных переменных, т.е. случайно. Переменная неявно исключается, если она появляется хотя бы в одном неравенстве $H_{i}$, но не появляется ни в неравенстве $i$ ни в $E_{i}$
• $R_{i}$, все остальные переменные.

Неизбыточное неравенство обладает тем свойством, что его история минимальна .

Теорема (первая теорема Имберта об ускорении). Если история $H_{i}$ неравенства $i$ минимально, то $1+|E_{i}|\ \leq \ |H_{i}|\ \leq 1+\left|E_{i}\cup (I_{i}\cap O_{k})\right|$.

Неравенство, не удовлетворяющее этим границам, обязательно является избыточным и может быть удалено из системы без изменения множества ее решений.

Вторая теорема об ускорении определяет минимальные наборы истории:

Теорема (вторая теорема Имберта об ускорении). Если неравенство $i$ таков, что $1+|E_{i}|=|H_{i}|$, затем $H_{i}$ является минимальным.

Эта теорема обеспечивает критерий быстрого обнаружения и используется на практике, чтобы избежать более дорогостоящих проверок, например, основанных на рангах матриц. Подробности реализации см. в ссылке.

Приложения в теории информации

Теоретико-информационные доказательства достижимости приводят к созданию условий, при которых гарантируется существование хорошо работающей схемы кодирования. Эти условия часто описываются линейной системой неравенств. Переменные системы включают как скорости передачи (которые являются частью постановки задачи), так и дополнительные вспомогательные скорости, используемые при разработке схемы. Обычно стремятся описать фундаментальные ограничения коммуникации только с точки зрения параметров задачи. Это приводит к необходимости исключения упомянутых выше вспомогательных скоростей, что осуществляется методом исключения Фурье–Моцкина. Однако в результате процесса исключения получается новая система, которая, возможно, содержит больше неравенств, чем исходная. Однако зачастую некоторые неравенства в сокращенной системе являются избыточными. Избыточность может подразумеваться другими неравенствами или неравенствами в теории информации (также известными как неравенства типа Шеннона). Недавно разработанное программное обеспечение с открытым исходным кодом для MATLAB. выполняет исключение, одновременно выявляя и удаляя лишние неравенства. Следовательно, программное обеспечение выдает упрощенную систему (без избыточности), в которой учитываются только скорости связи.

Избыточное ограничение можно выявить путем решения линейной программы следующим образом. Для системы линейных ограничений, если $i$-е неравенство выполняется для любого решения всех остальных неравенств, то оно избыточно. Точно так же ИППП относятся к неравенствам, которые подразумеваются неотрицательностью теоретико-информационных мер и базовых идентичностей, которым они удовлетворяют. Например, СТИ $I(X_{1};X_{2})\leq H(X_{1})$ является следствием тождества $I(X_{1};X_{2})=H(X_{1})-H(X_{1}|X_{2})$ и неотрицательность условной энтропии, т. е. $H(X_{1}|X_{2})\geq 0$. Неравенства типа Шеннона определяют конус в $\mathbb {R} ^{2^{n}-1}$, где $n$ – это количество случайных величин, входящих в задействованные информационные меры. Следовательно, любое STI можно доказать с помощью линейного программирования, проверив, подразумевается ли оно из основных тождеств и ограничений неотрицательности. Описанный алгоритм сначала выполняет метод исключения Фурье – Моцкина, чтобы удалить вспомогательные скорости. Затем он накладывает теоретико-информационные ограничения неотрицательности на сокращенную систему вывода и удаляет избыточные неравенства.

См. также

• Лемма Фаркаша - может быть доказана методом исключения FM.
• Реальное замкнутое поле - алгоритм цилиндрической алгебраической декомпозиции выполняет устранение кванторов над полиномиальными неравенствами, а не только над линейными.

Дальнейшее чтение

• Шрийвер, Александр (1998). Теория линейного и целочисленного программирования . Джон Уайли и сыновья. стр. 155–156. ISBN  978-0-471-98232-6 .
• Кесслер, Кристоф В. (1996). «Параллельное устранение Фурье – Моцкина». Трирский университет : 66–71. CiteSeerX   10.1.1.54.657 .
• Уильямс, HP (1986). «Метод линейного программирования Фурье и его двойник» (PDF) . Американский математический ежемесячник . 93 (9): 681–695. дои : 10.2307/2322281 . JSTOR   2322281 .

Внешние ссылки

• Глава 1 книги «Выпуклость для студентов» , учебник Нильса Лауритцена из Орхусского университета .
• Программное обеспечение FME для теории информации , открытый исходный код в MATLAB, авторы Идо Б. Гаттеньо, Зив Голдфельд и Хаим Х. Пермутер.
• Символическое исключение Фурье-Моцкина , открытый исходный код на Python, реализующий две теоремы Имберта об ускорении.