Лема Фаркаша

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

  1. A x = b,\quad x \geq 0, \quad x \in \R^n
  2. 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.

Посилання[ред.ред. код]

Література[ред.ред. код]

  • Borwein, Jonathan, and Lewis, Adrian. (2000). Convex Analysis and Nonlinear Optimization. Springer. ISBN 9780387989402