Лемма Фаркаша - утверждение выпуклой геометрии, широко используется в теории оптимизации, в частности при рассмотрении двойственных задач линейного программирования и доведение теоремы Каруша - Куна - Такера в нелинейном программировании . Лемма Фаркаша является одной из так называемых теорем альтернативности, что утверждают о существовании решения одной и только одной из немногих двух систем линейных уравнений и неравенств.
Теорема
Пусть A - матрица размерности m ? n , . Тогда решение имеет только одна из таких систем:
-
Доказательство
Пусть система 1 имеет решение, то есть существует вектор такой, что A X = b . Предположим тогда:
- .
Полученная противоречие доказывает, что система 2 не имеет решения.
Предположим, что система 1 не имеет решения. Рассмотрим замкнутую выпуклую множество . По предположению тогда учитывая теорему о отделимость выпуклой множества и точки, что ей не принадлежит, существуют вектор , и число ? такие, что Так, , то С другой стороны Компоненты вектора x могут быть сколь угодно большими, поэтому из последней неравенства получаем Таким , p - решение системы 2.