Лемма Фаркаса

Теорема разрешимости конечных систем линейных неравенств

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

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

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

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

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

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

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

Пример

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

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

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

• Если b ₂ ≥ 0 и b ₁ − 2 b ₂ ≥ 0 , то вариант 1 верен, так как решение линейных уравнений равно , а вариант 2 ложен, так как если правая часть положительна, то левая часть тоже должна быть положительной. ${\displaystyle x_{1}={\tfrac {b_{2}}{3}}}$ ${\displaystyle x_{2}={\tfrac {b_{1}-2b_{2}}{4}}.}$ $${\displaystyle 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 ₂ < 0 , то можно взять, например, y ₁ = 0 и y ₂ = 1 .
  • Если b ₁ − 2 b ₂ < 0 , то для некоторого числа B > 0 _b 1 ₌ 2 b ₂ − B , так что: Таким образом, мы можем взять, например, y ₁ = 1 , y 2 = −2 . $${\displaystyle 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}.}$$

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

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

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

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

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

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

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

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

Например, пусть n , m = 2 , a ₁ = (1, 0) ^T , и a ₂ = (1, 1) ^T . Выпуклый конус, натянутый на a ₁ и a _{2 ,} можно рассматривать как клиновидный срез первого квадранта в плоскости xy . Теперь предположим, что b = (0, 1) . Конечно, b не находится в выпуклом конусе a ₁ x ₁ + a ₂ x ₂ . Следовательно, должна быть разделяющая гиперплоскость. Пусть y = (1, −1) ^T . Мы можем видеть, что a ₁ · y = 1 , a ₂ · y = 0 , и b · y = −1 . Следовательно, гиперплоскость с нормалью y действительно отделяет выпуклый конус a ₁ x ₁ + a ₂ x ₂ от b .

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

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

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

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

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

Варианты

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

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

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

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

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

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

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

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

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

Варианты обобщены в таблице ниже.

Обобщения

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

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

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

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

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

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

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

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

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

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

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

Примечания

1. Фаркас, Юлиус (Дьюла) (1902), "Theorie der Einfachen Ungleichungen", Journal für die reine und angewandte Mathematik , 1902 (124): 1–27, doi : 10.1515/crll.1902.124.1, S2CID  115770124
2. Такаяма, Акира (1985). Математическая экономика (2-е изд.). Нью-Йорк: Cambridge University Press. стр. 48. ISBN 0-521-31498-4.
3. Гарг, Анупам ; Мермин, НД (1984), «Лемма Фаркаса и природа реальности: статистические следствия квантовых корреляций», Основы физики , 14 : 1–39, doi :10.1007/BF00741645, S2CID  123622613
4. Динь, Н.; Джеякумар, В. (2014), «Лемма Фаркаса о трех десятилетиях обобщений для математической оптимизации», TOP , 22 (1): 1–22, doi :10.1007/s11750-014-0319-y, S2CID  119858980
5. Border, KC (2013). "Альтернативные линейные неравенства" (PDF) . Получено 29.11.2021 .
6. Гейл, Дэвид ; Кун, Гарольд ; Такер, Альберт В. (1951), «Линейное программирование и теория игр — Глава XII» (PDF) , в Koopmans (ред.), Анализ деятельности по производству и распределению , Wiley. См. Лемму 1 на стр. 318.
7. Бойд, Стивен П.; Ванденберг, Ливен (2004), "Раздел 5.8.3" (pdf) , Выпуклая оптимизация , Cambridge University Press, ISBN 978-0-521-83378-3, получено 15 октября 2011 г..
8. Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования . Берлин: Шпрингер. ISBN 3-540-30697-8.Страницы 81–104.
9. Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация, Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер документа : 10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, г-н  1261419

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

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