Исключение Фурье-Моцкина

Математический алгоритм исключения переменных из системы линейных неравенств

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

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

Устранение

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

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

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

• те неравенства, которые имеют вид ; обозначим их через , для значений от 1 до , где - число таких неравенств; ${\displaystyle x_{r}\geq b_{i}-\sum _{k=1}^{r-1}a_{ik}x_{k}}$ ${\displaystyle x_{r}\geq A_{i}(x_{1},\dots ,x_{r-1})}$ ${\displaystyle i}$ ${\displaystyle n_{A}}$ ${\displaystyle n_{A}}$
• те неравенства, которые имеют вид ; обозначим их через , для значений от 1 до , где - число таких неравенств; ${\displaystyle x_{r}\leq b_{i}-\sum _{k=1}^{r-1}a_{ik}x_{k}}$ ${\displaystyle x_{r}\leq B_{i}(x_{1},\dots ,x_{r-1})}$ ${\displaystyle i}$ ${\displaystyle n_{B}}$ ${\displaystyle n_{B}}$
• те неравенства, в которых не играет никакой роли, группируются в одну конъюнкцию . ${\displaystyle x_{r}}$ ${\displaystyle \phi }$

Исходная система, таким образом, эквивалентна

${\displaystyle \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 }$.

Устранение состоит в создании системы, эквивалентной . Очевидно, что эта формула эквивалентна ${\displaystyle \exists x_{r}~S}$

${\displaystyle \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 }$.

Неравенство

${\displaystyle \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}))}$

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

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

Пример

Рассмотрим следующую систему неравенств: ^{[2] : 100–102}

${\displaystyle {\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 неравенства, поэтому мы используем это вместо этого.

${\displaystyle {\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 неравенства:

${\displaystyle {\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}}}$

Упрощение:

${\displaystyle {\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 удовлетворяет как исходной системе, так и редуцированным.

Сложность

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

Ссылки

1. Фурье, Жозеф (1827). «История Академии, математическая партия (1824 г.)». Мемуары Академии наук Института Франции . Том. 7. Готье-Виллар.
2. Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования . Берлин: Шпрингер. ISBN 3-540-30697-8.Страницы 81–104.
3. Дэвид Моннио, Устранение квантификаторов с помощью ленивого перечисления моделей, Компьютерная верификация (CAV) 2010.
4. RJ. Jing, M. Moreno-Maza и D. Talaashrafi [1] Оценки сложности для исключения Фурье-Моцкина . В: Boulier, F., England, M., Sadykov, TM, Vorozhtsov, EV (ред.) Computer Algebra in Scientific Computing. CASC 2020. Lecture Notes in Computer Science, т. 12291. Springer,]
5. Жан-Луи Имбер, Об избыточных неравенствах, генерируемых алгоритмом Фурье , Искусственный интеллект IV: Методология, системы, приложения, 1990.
6. Жан-Луи Имбер, Исключение Фурье: что выбрать?.
7. Gattegno, Ido B.; Goldfeld, Ziv; Permuter, Haim H. (2015-09-25). "Программное обеспечение для исключения Фурье-Моцкина для неравенств теории информации". arXiv : 1610.03990 [cs.IT].

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

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

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

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