Лемма Фаркаша - Википедия - Farkas lemma

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

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

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

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

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

Существует ${ displaystyle mathbf {x} in mathbb {R} ^ {n}}$ такой, что ${ Displaystyle mathbf {Ax} = mathbf {b}}$ и ${ Displaystyle mathbf {х} geq 0}$ .
Существует ${ 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 {х} 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}}}$ . Лемма утверждает, что должно выполняться ровно одно из следующих двух утверждений (в зависимости от б₁ и б₂):

Существуют Икс₁ ≥ 0, Икс₂ ≥ 0 такое, что 6 Икс₁ + 4 Икс₂ = б₁ и 3 Икс₁ = б₂, или же
Существуют у₁, у₂ так что 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 С ( mathbf {A})}$ покрытый столбцами ${ displaystyle mathbf {A}}$ ; то есть,

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

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

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

Существуют неотрицательные коэффициенты ${ displaystyle x_ {1}, dots, x_ {n} in mathbb {R}}$ такой, что ${ displaystyle mathbf {b} = x_ {1} mathbf {a} _ {1} + dots + x_ {n} mathbf {a} _ {n}}$ .
Существует вектор ${ displaystyle mathbf {y} in mathbb {R} ^ {m}}$ такой, что ${ Displaystyle mathbf {а} _ {я} ^ { mathsf {T}} mathbf {y} geq 0}$ за ${ Displaystyle я = 1, точки, п}$ , и ${ 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 С ( mathbf {A})}$ .

Второе утверждение говорит, что существует вектор ${ displaystyle mathbf {y}}$ такой, что угол ${ displaystyle mathbf {y}}$ с векторами ${ Displaystyle mathbf {а} _ {я}}$ составляет не более 90 °, а угол ${ displaystyle mathbf {y}}$ с вектором ${ displaystyle mathbf {b}}$ больше 90 °. Гиперплоскость, нормальная к этому вектору, имеет векторы ${ Displaystyle mathbf {а} _ {я}}$ с одной стороны и вектор ${ 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 у ^ { mathsf {T}} А = 0}$ , ${ Displaystyle у ^ { mathsf {T}} б = -1}$ , ${ displaystyle y}$ ≥ ${ displaystyle 0}$ есть решение.^[6] Обратите внимание, что ${ displaystyle y ^ { mathsf {T}} A}$ это комбинация левых частей, ${ Displaystyle у ^ { mathsf {T}} б}$ комбинация правой части неравенств. Поскольку положительная комбинация дает нулевой вектор слева и −1 справа, противоречие очевидно.

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

Варианты

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

Либо система ${ Displaystyle mathbf {Ax} = mathbf {b}}$ имеет решение с ${ Displaystyle mathbf {х} 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 {х} 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} ^ {п}}$ , а двойной конус из ${ 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 С ( mathbf {A}) = { mathbf {A} mathbf {x} mid mathbf {x} in mathbf {S} }}$ закрыто, то верно одно из следующих двух утверждений:

Существует ${ displaystyle mathbf {x} in mathbb {R} ^ {n}}$ такой, что ${ Displaystyle mathbf {Ax} = mathbf {b}}$ и ${ displaystyle mathbf {x} in mathbf {S}}$ .
Существует ${ 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} _ {+} ^ {п}}$ , следовательно, условие замкнутости выполняется автоматически. Действительно, для многогранного выпуклого конуса, т.е. существует ${ Displaystyle mathbf {B} in mathbb {R} ^ {п раз k}}$ такой, что ${ Displaystyle mathbf {S} = { mathbf {B} mathbf {x} mid mathbf {x} in mathbb {R} _ {+} ^ {k} }}$ , условие замкнутости выполняется автоматически. В выпуклая оптимизация, различные виды квалификационных ограничений, например Состояние Слейтера, отвечают за замкнутость нижележащего выпуклого конуса ${ Displaystyle С ( 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}}$ . Тогда верно одно из следующих двух утверждений:

Существует ${ displaystyle mathbf {x} in mathbb {R} ^ {n}}$ такой, что ${ displaystyle mathbf {Ax} = mathbf {b}}$ .
Существует ${ 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 А ^ { mathsf {T}} у = 0}$ имеет ненулевое решение у с у ≥ 0.

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

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

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

Примечания

^ Фаркас, Юлиус (Дьюла) (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
^ Такаяма, Акира (1985). Математическая экономика (2-е изд.). Нью-Йорк: Издательство Кембриджского университета. п.48. ISBN 0-521-31498-4.
^ Гарг, Анупам; Мермин, Н. (1984), «Лемма Фаркаша и природа реальности: статистические последствия квантовых корреляций», Основы физики, 14: 1–39, Дои:10.1007 / BF00741645
^ Динь, Н.; Джеякумар, В. (2014), «Лемма Фаркаша три десятилетия обобщений для математической оптимизации», ВЕРХ, 22 (1): 1–22, Дои:10.1007 / s11750-014-0319-у, S2CID 119858980
^ Гейл, Дэвид; Кун, Гарольд; Такер, Альберт В. (1951), «Линейное программирование и теория игр - Глава XII» (PDF), в Купмансе (ред.), Анализ деятельности производства и распределения, Wiley. См. Лемму 1 на стр. 318.
^ Бойд, Стивен П .; Ванденберге, Ливен (2004), «Раздел 5.8.3» (pdf), Выпуклая оптимизация, Издательство Кембриджского университета, ISBN 978-0-521-83378-3, получено 15 октября, 2011.
^ ^а ^б Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования. Берлин: Springer. ISBN 3-540-30697-8. Страницы 81–104.

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

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

[Farkas1902-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.

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

[Jeyakumar2014-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.

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]