Лемма Фаркаша - Farkas lemma

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

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

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

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

Лемма Фаркаша —  Позволять ${\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} ^{\mathsf {T}}\mathbf {y} \geq 0}$ и ${\displaystyle \mathbf {b} ^{\mathsf {T}}\mathbf {y} <0}$.

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

Пример

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

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

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

• Если б₂ ≥ 0 и б₁ − 2б₂ ≥ 0, то верен вариант 1, так как решение линейных уравнений есть Икс₁ = б₂/ 3 и Икс₂ = б₁-2б₂. Вариант 2 неверен, поскольку б₁ у₁ + б₂ у₂ ≥ б₂ (2 у₁ + у₂) = б₂ (6 у₁ + 3 у₂) / 3, поэтому, если правая часть положительна, левая часть тоже должна быть положительной.
• В противном случае вариант 1 неверен, поскольку единственное решение линейных уравнений не является слабо положительным. Но в этом случае верен вариант 2:
  • Если б₂ <0, то мы можем взять, например, у₁ = 0 и у₂ = 1.
  • Если б₁ − 2б₂ <0, то для некоторого числа B > 0, б₁ = 2б₂ - Б, так что: б₁ у₁ + б₂ у₂ = 2 б₂ у₁ + б₂ у₂ − B у₁ = б₂ (6 у₁ + 3 у₂) / 3 − B у₁. Таким образом, мы можем взять, например, у₁ = 1, у₂ = −2.

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

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

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

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

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

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}^{\mathsf {T}}\mathbf {y} \geq 0}$ за ${\displaystyle i=1,\dots ,n}$, и ${\displaystyle \mathbf {b} ^{\mathsf {T}}\mathbf {y} <0}$.

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

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

Например, пусть п, м = 2, а₁ = (1, 0)^Т, и а₂ = (1, 1)^Т. Выпуклый конус, натянутый на а₁ и а₂ можно рассматривать как клиновидный срез первого квадранта в ху самолет. Теперь предположим б = (0, 1). Безусловно, б не находится в выпуклом конусе а₁Икс₁ + а₂Икс₂. Следовательно, должна быть разделяющая гиперплоскость. Позволять у = (1, −1)^Т. Мы видим, что а₁ · у = 1, а₂ · у = 0 и б · у = -1. Следовательно, гиперплоскость с нормалью у действительно разделяет выпуклый конус а₁Икс₁ + а₂Икс₂ из б.

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

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

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

Варианты

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

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

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

Обобщения

Обобщенная лемма Фаркаша —  Позволять ${\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} ^{\mathsf {T}}\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} ^{\mathsf {T}}\mathbf {y} \in \mathbf {S} ^{*}}$ и ${\displaystyle \mathbf {b} ^{\mathsf {T}}\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} ^{\mathsf {T}}\mathbf {y} =0}$ и ${\displaystyle \mathbf {b} ^{\mathsf {T}}\mathbf {y} \neq 0}$.

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

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

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

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

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

Примечания

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

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

• Goldman, A. J .; Такер, А. В. (1956). «Многогранные выпуклые конусы». В Kuhn, H.W .; Такер, А. В. (ред.). Линейные неравенства и родственные системы. Принстон: Издательство Принстонского университета. С. 19–40. ISBN  0691079994.
• Рокафеллар, Р. Т. (1979). Выпуклый анализ. Издательство Принстонского университета. п. 200.