Введение
Теорема разрешимости для конечных систем линейных неравенств В математике, лемма Фаркаса - это теорема разрешимости для конечной системы линейных неравенств. Первоначально это было доказано венгерским математиком Гюлой Фаркасом. Лемма Фаркаса является ключевым результатом, лежащим в основе дуальности линейного программирования, и сыграла центральную роль в развитии математической оптимизации (альтернативно, математического программирования). Он используется, среди прочего, в доказательстве теоремы КарушаКунаТаккера в нелинейном программировании. Примечательно, что в области основ квантовой теории лемма также лежит в основе полного набора неравенств Белла в виде необходимых и достаточных условий для существования локальной теории скрытых переменных, учитывая данные из любого конкретного набора измерений. Обобщения леммы Фаркаса касаются теоремы разрешимости для выпуклых неравенств, т. е. бесконечной системы линейных неравенств. Лема Фаркаса относится к классу утверждений, называемых "теоремами альтернативы": теорема, утверждающая, что решение имеет только одна из двух систем.
In mathematics, Farkas' lemma is a solvability theorem for a finite system of linear inequalities. It was originally proven by the Hungarian mathematician Gyula Farkas. Farkas' lemma is the key result underpinning the linear programming duality and has played a central role in the development of mathematical optimization (alternatively, mathematical programming). It is used amongst other things in the proof of the Karush–Kuhn–Tucker theorem in nonlinear programming. Remarkably, in the area of the foundations of quantum theory, the lemma also underlies the complete set of Bell inequalities in the form of necessary and sufficient conditions for the existence of a local hidden variable theory, given data from any specific set of measurements. Generalizations of the Farkas' lemma are about the solvability theorem for convex inequalities, i. e., infinite system of linear inequalities. Farkas' lemma belongs to a class of statements called "theorems of the alternative": a theorem stating that exactly one of two systems has a solution.
Заявление леммы
В литературе существует ряд несколько различных (но эквивалентных) формулировок леммы. Приведенный здесь пример - Гейл, Кун и Такер (1951). Здесь обозначение означает, что все компоненты вектора неотрицательны.
Логическая интерпретация
Особенно внушительной и легко запоминающейся версией является следующая: если набор линейных неравенств не имеет решения, то из него можно произвести противоречие путем линейной комбинации с негативными коэффициентами. В формулах: если неразрешимо, то есть решение. Обратите внимание, что это комбинация левой стороны, комбинация правой стороны неравенств. Поскольку положительная комбинация дает нулевой вектор слева и -1 справа, противоречие очевидно. Таким образом, лемму Фаркаса можно рассматривать как теорему логической полноты: это набор "аксиомов", линейные комбинации - "правила вывода", и лемма говорит, что, если набор аксиомов несовместим, то его можно опровергнуть, используя правила вывода.
Дальнейшие последствия
Лемму Фаркаса можно изменить на многие другие теоремы альтернативы с помощью простых модификаций, таких как теорема Гордана: либо имеет решение 'x', либо имеет ненулевое решение 'y' с 'y' ≥ 0. Общие приложения леммы Фаркаса включают доказательство теоремы сильной дуальности, связанной с линейным программированием и условиями Каруша Куна Таккера. Расширение леммы Фаркаса может быть использовано для анализа сильных условий двойственности и построения двойственности полуопределенной программы. Достаточно доказать существование условий Каруша Куна Таккера с использованием альтернативы Фредхольма, но для того, чтобы условие было необходимым, нужно применить теорему минимакс фон Неймана, чтобы показать, что уравнения, полученные Коши, не нарушены.