Лема Фаркаша — твердження опуклої геометрії, що широко використовується в теорії оптимізації, зокрема при розгляді двоїстих задач лінійного програмування і доведення теореми Каруша — Куна — Такера в нелінійному програмуванні. Лема Фаркаша є однією з так званих теорем альтернативності, що стверджують про існування розв'язку однієї і тільки однієї з деяких двох систем лінійних рівнянь і нерівностей
Нехай A – матриця розмірності m × n,
. Тоді розв'язок має тільки одна з таких систем:
![{\displaystyle Ax=b,\quad x\geq 0,\quad x\in \mathbb {R} ^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b987c6444db556ba24e8910f70c303b0da3d7e4c)
![{\displaystyle y^{\top }A\leq 0,\quad \langle y,b\rangle >0\quad y\in \mathbb {R} ^{m}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b02f9a8285312b74104d22d87ed7aba9de6d590d)
Нехай система 1 має розв’язок, тобто існує вектор
такий, що
Припустимо
тоді:
.
Одержана суперечність доводить, що система 2 не має розв’язку.
Припустимо, що система 1 не має розв’язку. Розглянемо замкнуту опуклу множину
. За припущенням
тоді з огляду на теорему про віддільність опуклої множини і точки, що їй не належить, існують вектор
, і число α такі, що
Оскільки,
, то
З іншого боку
Компоненти вектора x можуть бути як завгодно великими, тому з останньої нерівності отримуємо
Отже, p — розв’язок системи 2.
Для дійсної матриці A розмірності m × n і
має розв'язок одна і тільки одна з таких систем:
![{\displaystyle Ax\leq b,\quad x\in \mathbb {R} ^{n},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c9f4e57ac8801b220bb943989d442fa5fc91998)
![{\displaystyle A^{T}y=0,\quad b^{T}y<0,\quad y\in \mathbb {R} ^{m},\quad y\geq 0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/24014c3fbf59e3e3843b2a2ed91780d02f4c325c)
Дане твердження іноді називають теоремою Гейла.
Нехай
це матриця
, де
це одинична матриця. Розмірність цієї матриці є рівною m × (2n+m).
Система нерівностей
має розв'язок
тоді і тільки тоді, коли система рівнянь
має невід'ємний розв'язок
. Справді, якщо система рівнянь має такий розв'язок то позначивши
одержуємо
де
позначає вектор елементами якого є
Оскільки усі
то звідси одержуємо
Якщо ж
має розв'язок
то можна знайти розв'язок системи рівнянь
. Для цього для кожного індексу i, якщо
то нехай
Якщо
то нехай
Значеннями
визначимо різницю
і добутку i-го рядка матриці A і вектора x. Тоді так визначений вектор
є розв'язком системи рівнянь
Застосовуючи лему Фаркаша до системи
отримуємо твердження наслідку.
Навпаки із теореми Гейла можна довести лему Фаркаша. Як і вище доводиться, що система
(яку транспонувавши зручніше розглядати у виді
) має розв'язок тоді і тільки тоді коли має розв'язок невід'ємний розв'язок система
де
є матрицею розмірності n × (2m + n). Додаткова умова
при цьому виконується тоді і лише тоді коли для відповідного вектора
(що одержується із
, як
із
вище) виконується умова
де
є вектором перші m координат якого є рівні відповідним координатам вектора
помноженим на -1, наступні m координат є рівні відповідним координатам вектора
, а останні n координат є рівні 0.
Відповідно якщо друга система у твердженні леми Фаркаша не має розв'язків то система
не має невід'ємних розв'язків, що задовольняють нерівність
Тоді із теореми Гейла випливає існування
для якого
Тоді
є розв'язком першої системи в умові леми Фаркаша.
- Borwein, Jonathan, and Lewis, Adrian. (2000). Convex Analysis and Nonlinear Optimization. Springer. ISBN 9780387989402