Лемма Вольфа

В математике — лемма Фаркаша теорема разрешимости конечной системы линейных неравенств . Первоначально это было доказано венгерским математиком Дьюлой Фаркашем . ^[1] Фаркаша Лемма является ключевым результатом, лежащим в основе двойственности линейного программирования , и сыграла центральную роль в развитии математической оптимизации (альтернативно, математического программирования ). Он используется, среди прочего, при доказательстве теоремы Каруша-Куна-Такера в нелинейном программировании . ^[2]Примечательно, что в области основ квантовой теории лемма также лежит в основе полного набора неравенств Белла в виде необходимых и достаточных условий существования локальной теории скрытых переменных при данных любого конкретного набора измерений. ^[3]

Обобщения леммы Фаркаша касаются теоремы о разрешимости выпуклых неравенств: ^[4] т. е. бесконечная система линейных неравенств. Лемма Фаркаша принадлежит к классу утверждений, называемых «теоремы альтернативы»: теорема, утверждающая, что ровно одна из двух систем имеет решение. ^[5]

Утверждение леммы

В литературе встречается ряд несколько отличающихся (но эквивалентных) формулировок леммы. Приведенный здесь результат принадлежит Гейлу, Куну и Такеру (1951). ^[6]

Лемма Фаркаша — Пусть $\mathbf {A} \in \mathbb {R} ^{m\times n}$ и $\mathbf {b} \in \mathbb {R} ^{m}.$ Тогда верно ровно одно из следующих двух утверждений:

Существует $\mathbf {x} \in \mathbb {R} ^{n}$ такой, что $\mathbf {Ax} =\mathbf {b}$ и $\mathbf {x} \geq 0.$
Существует $\mathbf {y} \in \mathbb {R} ^{m}$ такой, что $\mathbf {A} ^{\top }\mathbf {y} \geq 0$ и $\mathbf {b} ^{\top }\mathbf {y} <0.$

Здесь обозначение $\mathbf {x} \geq 0$ означает, что все компоненты вектора $\mathbf {x}$ неотрицательны.

Пример

Пусть $m, n = 2$ , $\mathbf {A} ={\begin{bmatrix}6&4\\3&0\end{bmatrix}},$ и $\mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\end{bmatrix}}.$ Лемма гласит, что ровно одно из следующих двух утверждений должно быть истинным (в зависимости от $b 1$ и $b 2$ ):

Существуют $x 1 \geq 0$ , $x 2 \geq 0$ такие, что $6 x 1 + 4 x 2 = b 1$ и $3 x 1 = b 2$ , или
Существуют $y 1, y 2$ такие, что $6 y 1 + 3 y 2 \geq 0$ , $4 y 1 \geq 0$ и $b 1 y 1 + b 2 y 2 < 0$ .

Вот доказательство леммы в этом частном случае:

Если $b 2 \geq 0$ и $b 1 - 2 b 2 \geq 0$ , то верен вариант 1, поскольку решение линейных уравнений есть $x_{1}={\tfrac {b_{2}}{3}}$ и $x_{2}={\tfrac {b_{1}-2b_{2}}{4}}.$ Вариант 2 неверен, так как $b_{1}y_{1}+b_{2}y_{2}\geq b_{2}(2y_{1}+y_{2})=b_{2}{\frac {6y_{1}+3y_{2}}{3}},$ поэтому, если правая часть положительна, левая часть тоже должна быть положительной.
В противном случае вариант 1 неверен, поскольку единственное решение линейных уравнений не является слабо положительным. Но в данном случае верен вариант 2:
- Если $b 2 < 0$ , то мы можем взять, например, $y 1 = 0$ и $y 2 = 1$ .
- Если $b 1 - 2 b 2 < 0$ , то для некоторого числа $B > 0$ b $1 = 2 b 2 - B$ , поэтому: $b_{1}y_{1}+b_{2}y_{2}=2b_{2}y_{1}+b_{2}y_{2}-By_{1}=b_{2}{\frac {6y_{1}+3y_{2}}{3}}-By_{1}.$ образом, мы можем взять, например, $y1, = 1$ y2 $= Таким -2$ .

Геометрическая интерпретация

Рассмотрим замкнутый выпуклый конус $C(\mathbf {A} )$ натянутый столбцами $A$ ; то есть,

C(\mathbf {A} )=\{\mathbf {A} \mathbf {x} \mid \mathbf {x} \geq 0\}.

Обратите внимание, что $C(\mathbf {A} )$ — множество векторов $b$ , для которых выполнено первое утверждение леммы Фаркаша. С другой стороны, вектор $y$ во втором утверждении ортогонален гиперплоскости , разделяющей $b$ и $C(\mathbf {A} ).$ Лемма следует из наблюдения, что $b$ принадлежит $C(\mathbf {A} )$ тогда и только тогда, когда не существует гиперплоскости, отделяющей его от $C(\mathbf {A} ).$

Точнее, пусть $\mathbf {a} _{1},\dots ,\mathbf {a} _{n}\in \mathbb {R} ^{m}$ обозначаем столбцы $A$ . Что касается этих векторов, лемма Фаркаша утверждает, что верно ровно одно из следующих двух утверждений:

Существуют неотрицательные коэффициенты $x_{1},\dots ,x_{n}\in \mathbb {R}$ такой, что $\mathbf {b} =x_{1}\mathbf {a} _{1}+\dots +x_{n}\mathbf {a} _{n}.$
Существует вектор $\mathbf {y} \in \mathbb {R} ^{m}$ такой, что $\mathbf {a} _{i}^{\top }\mathbf {y} \geq 0$ для $i=1,\dots ,n,$ и $\mathbf {b} ^{\top }\mathbf {y} <0.$

Суммы $x_{1}\mathbf {a} _{1}+\dots +x_{n}\mathbf {a} _{n}$ с неотрицательными коэффициентами $x_{1},\dots ,x_{n}$ образуют конус, охватываемый столбцами $A$ . Следовательно, первое утверждение говорит, что $b$ принадлежит $C(\mathbf {A} ).$

Второе утверждение говорит, что существует вектор $y$ такой, что угол $y$ с векторами $a i$ не превышает 90°, а угол $y$ с вектором $b$ больше 90°. Гиперплоскость, нормальная к этому вектору, имеет векторы $a i$ с одной стороны и вектор $b$ с другой стороны. Следовательно, эта гиперплоскость разделяет конус, натянутый на $\mathbf {a} _{1},\dots ,\mathbf {a} _{n}$ из вектора $b$ .

Например, пусть $n, m = 2$ , $a 1 = (1, 0) Т$ , и $а 2 = (1, 1) Т$ . Выпуклый конус, охватываемый $цифрами 1$ и $2,$ можно рассматривать как клиновидный срез первого квадранта в $плоскости xy$ . Теперь предположим, что $b = (0, 1)$ . Разумеется, $b$ не находится в выпуклом конусе $a 1 x 1 + a 2 x 2$ . Следовательно, должна существовать разделяющая гиперплоскость. Пусть $y = (1, -1) Т$ . Мы видим, что $a 1 \cdot y = 1$ , $a 2 \cdot y = 0$ и $b \cdot y = -1$ . Следовательно, гиперплоскость с нормалью $y$ действительно отделяет выпуклый конус $a 1 x 1 + a 2 x 2$ от $b$ .

Логическая интерпретация

Особенно наглядный и легко запоминающийся вариант: если набор линейных неравенств не имеет решения, то из него можно получить противоречие путем линейной комбинации с неотрицательными коэффициентами. В формулах: если $\mathbf {Ax} \leq \mathbf {b}$ тогда неразрешимо $\mathbf {y} ^{\top }\mathbf {A} =0,$ $\mathbf {y} ^{\top }\mathbf {b} =-1,$ $\mathbf {y} \geq 0$ имеет решение. ^[7] Обратите внимание, что $\mathbf {y} ^{\top }\mathbf {A}$ представляет собой комбинацию левых частей, $\mathbf {y} ^{\top }\mathbf {b}$ сочетание правых частей неравенств. Поскольку положительная комбинация дает нулевой вектор слева и −1 справа, противоречие очевидно.

Таким образом, лемму Фаркаша можно рассматривать как теорему логической полноты : $\mathbf {Ax} \leq \mathbf {b}$ представляет собой набор «аксиом», линейные комбинации — «правила вывода», а лемма гласит, что если набор аксиом противоречив, то его можно опровергнуть с помощью правил вывода. ^[8]^: 92–94

Последствия для теории сложности

Лемма Фаркаша подразумевает, что проблема решения «Для данной системы линейных уравнений имеет ли она неотрицательное решение?» находится на пересечении NP и co-NP . Это связано с тем, что, согласно лемме, как ответ «да», так и ответ «нет» имеют доказательство, которое можно проверить за полиномиальное время. Проблемы на перекрёстке $NP\cap coNP$ также называются хорошо охарактеризованными проблемами . Вопрос о том, является ли $NP\cap coNP$ равен П. В частности, не было известно, что вопрос о том, имеет ли система линейных уравнений неотрицательное решение, находится в P, пока он не был доказан методом эллипсоидов . ^[9]^: 25

Варианты

Лемма Фаркаша имеет несколько вариантов с разными знаковыми ограничениями (первый — исходный): ^[8]^: 92

Или $\mathbf {Ax} =\mathbf {b}$ есть решение $\mathbf {x} \geq 0,$ или $\mathbf {A} ^{\top }\mathbf {y} \geq 0$ есть решение $\mathbf {y} \in \mathbb {R} ^{m}$ с $\mathbf {b} ^{\top }\mathbf {y} <0.$
Или $\mathbf {Ax} \leq \mathbf {b}$ есть решение $\mathbf {x} \geq 0,$ или $\mathbf {A} ^{\top }\mathbf {y} \geq 0$ есть решение $\mathbf {y} \geq 0$ с $\mathbf {b} ^{\top }\mathbf {y} <0$
Или $\mathbf {Ax} \leq \mathbf {b}$ есть решение $\mathbf {x} \in \mathbb {R} ^{n},$ или $\mathbf {A} ^{\top }\mathbf {y} =0$ есть решение $\mathbf {y} \geq 0$ с $\mathbf {b} ^{\top }\mathbf {y} <0$ .
Или $\mathbf {Ax} =\mathbf {b}$ есть решение $\mathbf {x} \in \mathbb {R} ^{n},$ или $\mathbf {A} ^{\top }\mathbf {y} =0$ есть решение $\mathbf {y} \in \mathbb {R} ^{m}$ с $\mathbf {b} ^{\top }\mathbf {y} \neq 0.$

Последний вариант упоминается для полноты картины; На самом деле это не «лемма Фаркаша», поскольку она содержит только равенства. Его доказательство представляет собой упражнение по линейной алгебре .

Существуют также леммы типа Фаркаша для целочисленных программ. ^[9]^: 12--14 Для систем уравнений лемма проста:

Предположим, что A и b имеют рациональные коэффициенты. Тогда либо $\mathbf {Ax} =\mathbf {b}$ имеет целое решение $\mathbf {x} \in \mathbb {Z} ^{n},$ или существует $\mathbf {y} \in \mathbb {R} ^{n}$ такой, что $\mathbf {A} ^{\top }\mathbf {y}$ является целостным и $\mathbf {b} ^{\top }\mathbf {y}$ не является целостным.

Для системы неравенств лемма значительно сложнее. Он основан на следующих двух правилах вывода :

Учитывая неравенства $a_{1}^{T}x\leq b_{1},\ldots ,a_{m}^{T}x\leq b_{m}$ и коэффициенты $w_{1},\ldots ,w_{m}$ , сделайте вывод о неравенстве $\left(\sum _{i=1}^{m}w_{i}a_{i}^{T}\right)x\leq \sum _{i=1}^{m}w_{i}b_{i}$ .
Учитывая неравенство $a_{1}x_{1}+\cdots +a_{m}x_{m}\leq b$ , сделайте вывод о неравенстве $\lfloor a_{1}\rfloor x_{1}+\cdots +\lfloor a_{m}\rfloor x_{m}\leq \lfloor b\rfloor$ .

Лемма гласит, что:

Предположим, что A и b имеют рациональные коэффициенты. Тогда либо $\mathbf {Ax} \leq \mathbf {b}$ имеет целое решение $\mathbf {x} \in \mathbb {Z} ^{n},x\geq 0$ , или можно сделать вывод из $\mathbf {Ax} \leq \mathbf {b}$ используя конечное число применений правил вывода 1,2, неравенство $0^{T}x\leq -1$ .

Варианты сведены в таблицу ниже.


Система	Ограничения на x	Альтернативная система	Ограничения на y
$\mathbf {Ax} =\mathbf {b}$	$\mathbf {x} \in \mathbb {R} ^{n},x\geq 0$	$\mathbf {A} ^{\top }\mathbf {y} \geq 0$ , $\mathbf {b} ^{\top }\mathbf {y} <0$	$\mathbf {y} \in \mathbb {R} ^{m}$
$\mathbf {Ax} \leq \mathbf {b}$	$\mathbf {x} \in \mathbb {R} ^{n},x\geq 0$	$\mathbf {A} ^{\top }\mathbf {y} \geq 0$ , $\mathbf {b} ^{\top }\mathbf {y} <0$	$\mathbf {y} \in \mathbb {R} ^{m}$ , $\mathbf {y} \geq 0$
$\mathbf {Ax} \leq \mathbf {b}$	$\mathbf {x} \in \mathbb {R} ^{n}$	$\mathbf {A} ^{\top }\mathbf {y} =0$ , $\mathbf {b} ^{\top }\mathbf {y} <0$	$\mathbf {y} \in \mathbb {R} ^{m}$ , $\mathbf {y} \geq 0$
$\mathbf {Ax} =\mathbf {b}$	$\mathbf {x} \in \mathbb {R} ^{n}$	$\mathbf {A} ^{\top }\mathbf {y} =0$ , $\mathbf {b} ^{\top }\mathbf {y} \neq 0$	$\mathbf {y} \in \mathbb {R} ^{m}$
$\mathbf {Ax} =\mathbf {b}$	$\mathbf {x} \in \mathbb {Z} ^{n}$	$\mathbf {A} ^{\top }\mathbf {y}$ интеграл, $\mathbf {b} ^{\top }\mathbf {y}$ не целочисленный	$\mathbf {y} \in \mathbb {R} ^{n}$
$\mathbf {Ax} \leq \mathbf {b}$	$\mathbf {x} \in \mathbb {Z} ^{n},x\geq 0$	$0^{T}x\leq -1$ можно сделать вывод из $\mathbf {Ax} \leq \mathbf {b}$

Обобщения

Обобщенная лемма Фаркаса — Пусть $\mathbf {A} \in \mathbb {R} ^{m\times n},$ $\mathbf {b} \in \mathbb {R} ^{m},$ $\mathbf {S}$ представляет собой замкнутый выпуклый конус $\mathbb {R} ^{n},$ и двойной конус $\mathbf {S}$ является $\mathbf {S} ^{*}=\{\mathbf {z} \in \mathbb {R} ^{n}\mid \mathbf {z} ^{\top }\mathbf {x} \geq 0,\forall \mathbf {x} \in \mathbf {S} \}.$ Если выпуклый конус $C(\mathbf {A} )=\{\mathbf {A} \mathbf {x} \mid \mathbf {x} \in \mathbf {S} \}$ замкнуто, то верно ровно одно из следующих двух утверждений:

Существует $\mathbf {x} \in \mathbb {R} ^{n}$ такой, что $\mathbf {Ax} =\mathbf {b}$ и $\mathbf {x} \in \mathbf {S} .$
Существует $\mathbf {y} \in \mathbb {R} ^{m}$ такой, что $\mathbf {A} ^{\top }\mathbf {y} \in \mathbf {S} ^{*}$ и $\mathbf {b} ^{\top }\mathbf {y} <0.$

Обобщенную лемму Фаркаша можно интерпретировать геометрически следующим образом: либо вектор находится в данном замкнутом выпуклом конусе , либо существует гиперплоскость, отделяющая вектор от конуса; других возможностей нет. Условие замкнутости необходимо, см. Теорему разделения I в Теореме разделения гиперплоскости . Для исходной леммы Фаркаса $\mathbf {S}$ это неотрицательный ортант $\mathbb {R} _{+}^{n},$ следовательно, условие замкнутости выполняется автоматически. Действительно, для многогранного выпуклого конуса, т. е. существует $\mathbf {B} \in \mathbb {R} ^{n\times k}$ такой, что $\mathbf {S} =\{\mathbf {B} \mathbf {x} \mid \mathbf {x} \in \mathbb {R} _{+}^{k}\},$ условие замкнутости выполняется автоматически. В выпуклой оптимизации различные виды уточнений ограничений, например условие Слейтера . за замкнутость лежащего в основе выпуклого конуса отвечают $C(\mathbf {A} ).$

Установив $\mathbf {S} =\mathbb {R} ^{n}$ и $\mathbf {S} ^{*}=\{0\}$ в обобщенной лемме Фаркаша получаем следующее следствие о разрешимости конечной системы линейных равенств:

Следствие — Пусть $\mathbf {A} \in \mathbb {R} ^{m\times n}$ и $\mathbf {b} \in \mathbb {R} ^{m}.$ Тогда верно ровно одно из следующих двух утверждений:

Существует $\mathbf {x} \in \mathbb {R} ^{n}$ такой, что $\mathbf {Ax} =\mathbf {b} .$
Существует $\mathbf {y} \in \mathbb {R} ^{m}$ такой, что $\mathbf {A} ^{\top }\mathbf {y} =0$ и $\mathbf {b} ^{\top }\mathbf {y} \neq 0.$

Дальнейшие последствия

Лемму Фаркаша можно разнообразить многими другими альтернативными теоремами путем простых модификаций: ^[5] например, теорема Гордана : Либо $\mathbf {Ax} <0$ имеет решение $x$ или $\mathbf {A} ^{\top }\mathbf {y} =0$ имеет ненулевое решение $y$ с $y \geq 0$ .

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

См. также

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

Примечания

^ Фаркас, Юлиус (Дьюла) (1902), «Теория простых неравенств» , Журнал чистой и прикладной математики , 1902 (124): 1–27, doi : 10.1515/crll.1902.124.1 , S2CID 115770124
^ Такаяма, Акира (1985). Математическая экономика (2-е изд.). Нью-Йорк: Издательство Кембриджского университета. п. 48 . ISBN 0-521-31498-4 .
^ Гарг, Анупам ; Мермин, Н.Д. (1984), «Лемма Фаркаса и природа реальности: статистические последствия квантовых корреляций» , Foundations of Physics , 14 : 1–39, doi : 10.1007/BF00741645 , S2CID 123622613
^ Динь, Н. ; Джеякумар, В. (2014), «Лемма Фаркаса: три десятилетия обобщений для математической оптимизации», TOP , 22 (1): 1–22, doi : 10.1007/s11750-014-0319-y , S2CID 119858980
^ Jump up to: ^а ^б Граница, КЦ (2013). «Альтернативные линейные неравенства» (PDF) . Проверено 29 ноября 2021 г.
^ Гейл, Дэвид ; Кун, Гарольд ; Такер, Альберт В. (1951), «Линейное программирование и теория игр - Глава XII» (PDF) , в Купмансе (ред.), Анализ деятельности производства и распределения , Wiley . См. лемму 1 на стр. 318.
^ Бойд, Стивен П.; Ванденбергхе, Ливен (2004), «Раздел 5.8.3» (pdf) , Выпуклая оптимизация , Cambridge University Press, ISBN 978-0-521-83378-3 , получено 15 октября 2011 г.
^ Jump up to: ^а ^б Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования . Берлин: Шпрингер. ISBN 3-540-30697-8 . Страницы 81–104.
^ Jump up to: ^а ^б Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер номера : 10.1007/978-3-642-78240-4 , ISBN. 978-3-642-78242-8 , МР 1261419

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

Голдман, AJ; Такер, AW (1956). «Многогранные выпуклые конусы» . В Куне, HW; Такер, AW (ред.). Линейные неравенства и родственные системы . Принстон: Издательство Принстонского университета. стр. 19–40. ISBN 0691079994 .
Рокафеллар, RT (1979). Выпуклый анализ . Издательство Принстонского университета. п. 200.
Кутателадзе С.С. Еще раз о лемме Фаркаша. Сибирский математический журнал , 2010, Том. 51, № 1, 78–87.

[Farkas1902-1] Фаркас, Юлиус (Дьюла) (1902), «Теория простых неравенств» , Журнал чистой и прикладной математики , 1902 (124): 1–27, doi : 10.1515/crll.1902.124.1 , S2CID 115770124

[2] Такаяма, Акира (1985). Математическая экономика (2-е изд.). Нью-Йорк: Издательство Кембриджского университета. п. 48 . ISBN 0-521-31498-4 .

[Garg1984-3] Гарг, Анупам ; Мермин, Н.Д. (1984), «Лемма Фаркаса и природа реальности: статистические последствия квантовых корреляций» , Foundations of Physics , 14 : 1–39, doi : 10.1007/BF00741645 , S2CID 123622613

[Jeyakumar2014-4] Динь, Н. ; Джеякумар, В. (2014), «Лемма Фаркаса: три десятилетия обобщений для математической оптимизации», TOP , 22 (1): 1–22, doi : 10.1007/s11750-014-0319-y , S2CID 119858980

[:0-5] Jump up to: ^а ^б Граница, КЦ (2013). «Альтернативные линейные неравенства» (PDF) . Проверено 29 ноября 2021 г.

[6] Гейл, Дэвид ; Кун, Гарольд ; Такер, Альберт В. (1951), «Линейное программирование и теория игр - Глава XII» (PDF) , в Купмансе (ред.), Анализ деятельности производства и распределения , Wiley . См. лемму 1 на стр. 318.

[7] Бойд, Стивен П.; Ванденбергхе, Ливен (2004), «Раздел 5.8.3» (pdf) , Выпуклая оптимизация , Cambridge University Press, ISBN 978-0-521-83378-3 , получено 15 октября 2011 г.

[gm06-8] Jump up to: ^а ^б Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования . Берлин: Шпрингер. ISBN 3-540-30697-8 . Страницы 81–104.

[:1-9] Jump up to: ^а ^б Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер номера : 10.1007/978-3-642-78240-4 , ISBN. 978-3-642-78242-8 , МР 1261419

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]