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

редактировать

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

Алгоритм назван в честь Джозефа Фурье и Теодора Моцкина, которые независимо открыли этот метод в 1827 и 1936 годах соответственно.

Содержание

1 Исключение
2 Пример
3 Сложность
4 Теоремы Имберта об ускорении
5 Приложения в теории информации
6 См. Также
7 Ссылки
8 Дополнительные чтение
9 Внешние ссылки

Исключение

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

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

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

тех неравенств, которые имеют вид $xr ≥ bi - ∑ k = 1 r - 1 aikxk {\ displaystyle x_ {r} \ geq b_ {i} - \ sum _ {k = 1} ^ {r-1} a_ {ik} x_ {k} }$ $x_r \ geq b_i- \ sum_ {k = 1} ^ {r-1} a_ {ik} x_k$ ; обозначим их $xr ≥ A j (x 1,…, xr - 1) {\ displaystyle x_ {r} \ geq A_ {j} (x_ {1}, \ dots, x_ {r-1})}$ $x_r \ geq A_j (x_1, \ dots, x_ {r-1})$ для $j {\ displaystyle j}$ $j$ от 1 до $n A {\ displaystyle n_ {A}}$ $n_ {A}$ где $n A {\ displaystyle n_ {A}}$ $n_ {A}$ - количество таких неравенств;
те неравенства, которые имеют вид $xr ≤ bi - ∑ k = 1 r - 1 aikxk {\ displaystyle x_ {r} \ leq b_ {i} - \ sum _ {k = 1} ^ {r-1} a_ {ik} x_ {k}}$ $x_r \ leq b_i- \ sum_ {k = 1} ^ {r-1} a_ {ik} x_k$ ; обозначим их $xr ≤ B j (x 1,…, xr - 1) {\ displaystyle x_ {r} \ leq B_ {j} (x_ {1}, \ dots, x_ {r-1})}$ $x_r \ leq B_j (x_1, \ dots, x_ {r-1})$ , для $j {\ displaystyle j}$ $j$ от 1 до $n B {\ displaystyle n_ {B}}$ $n_ {B}$ где $n B {\ displaystyle n_ {B}}$ $n_ {B}$ - количество таких неравенств;
те неравенства, в которых $xr {\ displaystyle x_ {r}}$ $x_r$ не играет роли, сгруппированы в одно соединение $ϕ {\ displaystyle \ phi}$ $\ phi$ .

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

max (A 1 (x 1,…, xr - 1),…, A n A (x 1,…, xr - 1)) ≤ xr ≤ min (B 1 (x 1,…, xr - 1),…, B n B (x 1,…, xr - 1)) ∧ ϕ {\ 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}

\ 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, \ точки, x_ {r-1})) \ wedge \ phi

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

max (A 1 (x 1,…, xr - 1),…, A n A (x 1,…, xr - 1)) ≤ min (B 1 (x 1, …, Xr - 1),…, B n B (x 1,…, xr - 1)) ∧ ϕ {\ 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}

\ 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,…, xr - 1),…, A n A (x 1,…, xr - 1)) ≤ min (B 1 (x 1,…, xr - 1),…, B n B (x 1,…, Xr - 1)) {\ 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}))}

\ 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 {\ displaystyle n_ {A} n_ {B}}$ $n_A n_B$ неравенства $A я (x 1,…, xr - 1) ≤ B j (x 1,…, xr - 1) {\ displaystyle A_ {i} (x_ {1}, \ dots, x_ {r-1}) \ leq B_ {j} (x_ {1}, \ dots, x_ {r-1})}$ $A_i (x_1, \ dots, x_ {r-1}) \ leq B_j (x_1, \ dots, x_ {r-1})$ , для $1 ≤ i ≤ n A {\ displaystyle 1 \ leq i \ leq n_ { A}}$ $1 \ leq i \ leq n_A$ и $1 ≤ j ≤ N B {\ displaystyle 1 \ leq j \ leq n_ {B}}$ $1 \ leq j \ leq n_B$ .

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

Пример

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

2x - 5y + 4z ≤ 10

3x - 6y + 3z ≤ 9

−x + 5y - 2z ≤ −7

−3x + 2y + 6z ≤ 12

Чтобы исключить x, мы можем написать неравенства в терминах x:

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

x ≤ (9 + 6y - 3z) / 3

x ≥ 7 + 5y - 2z

x ≥ (−12 + 2y + 6z) / 3

У нас есть два неравенства с «≤» и два с «≥»; система имеет решение тогда и только тогда, когда правая часть каждого неравенства «≤» является по крайней мере правой частью каждого неравенства «≥». У нас есть 2 * 2 таких сочетания:

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

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

(−12 + 2y + 6z) / 3 ≤ (10 + 5y - 4z) / 2

(−12 + 2y + 6z) / 3 ≤ (9 + 6y - 3z) / 3

Теперь у нас есть новая система неравенств с на одну переменную меньше.

Сложность

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. Также

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

Ссылки

^Фурье, Жозеф (1827). «История академии, математическая партия (1824 г.)». Mémoires de l'Académie des Sciences de l'Institut de France. 7 . Готье-Виллар.
^Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования. Берлин: Springer. ISBN 3-540-30697-8.Страницы 81–104.
^Дэвид Моннио, Исключение квантора с помощью ленивого перечисления моделей, Компьютерная проверка (CAV) 2010.
^Жан-Луи Имбер, О избыточных неравенствах, порождаемых алгоритмом Фурье, Искусственный интеллект IV: Методология, системы, Applications, 1990.
^ Жан-Луи Имбер, Исключение Фурье: что выбрать?.
^Gattegno, Ido B.; Гольдфельд, Зив; Пермутер, Хаим Х. (25 сентября 2015 г.). "Программа исключения Фурье-Моцкина для теоретических информационных неравенств". arXiv : 1610.03990 [cs.IT ].

Дополнительная литература

Шрайвер, Александр (1998). Теория линейного и целочисленного программирования. Джон Уайли и сыновья. С. 155–156. ISBN 978-0-471-98232-6.
Кесслер, Кристоф В. «Параллельное исключение Фурье – Моцкина». Universität Trier. CiteSeerX 10.1.1.54.657. Отсутствует или пусто | url =()
Williams, HP (1986). «Метод Фурье линейного программирования и двойственное ему». American Mathematical Monthly. 93 (9): 681–695. doi : 10.2307 / 2322281. JSTOR 2322281.

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

Глава 1 программы Undergraduate Convexity, учебник Нильса Лауритцена из Орхусского университета.
Программное обеспечение FME для теории информации, открытый исходный код в MATLAB от Идо Б. Гаттегно, Зива Голдфельда и Хаима Х. Пермутера.