Лема Фаркаша

Лема Фаркаша — твердження опуклої геометрії, що широко використовується в теорії оптимізації, зокрема при розгляді двоїстих задач лінійного програмування і доведення теореми Каруша — Куна — Такера в нелінійному програмуванні. Лема Фаркаша є однією з так званих теорем альтернативності, що стверджують про існування розв'язку однієї і тільки однієї з деяких двох систем лінійних рівнянь і нерівностей

Твердження [ред.]

Нехай A – матриця розмірності m × n, $b \in \R^m$ . Тоді розв’язок має тільки одна з таких систем:

$A x = b,\quad x \geq 0, \quad x \in \R^n$
$y^\top A \leq 0,\quad \langle y,b \rangle > 0 \quad x \in \R^n$

Доведення [ред.]

Нехай система 1 має розв’язок, тобто існує вектор $x \geq 0$ такий, що $A x = b.$ Припустимо $y^\top A \leq 0,$ тоді:

$0 < \langle y, b \rangle = \langle y, A x \rangle = \langle y^\top A, x \rangle \leq 0$ .

Одержана суперечність доводить, що система 2 не має розв’язку.

Припустимо, що система 1 не має розв’язку. Розглянемо замкнуту опуклу множину $Z = \left \{ c:c = A x,\;x \ge 0 \right \}$ . За припущенням $b \notin Z,$ тоді з огляду на теорему про віддільність опуклої множини і точки, що їй не належить, існують вектор $p \in \R^n, p \neq 0$ , і число α такі, що $\left \langle p , b \right \rangle > \alpha ,\quad \;\left \langle p,c \right \rangle \le \alpha \quad \forall c \in Z.$ Оскільки, $0 \in Z$ , то $\alpha \geq 0, \, \left \langle p , b \right \rangle > \alpha \geq 0.$ З іншого боку $\alpha \geq \left \langle p , A x \right \rangle = \left \langle p^\top A, x \right \rangle.$ Компоненти вектора x можуть бути як завгодно великими, тому з останньої нерівності отримуємо $p^\top A \leq 0.$ Отже, p — розв’язок системи 2.