Лема Фаркаша

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

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

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

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

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

Нехай система 1 має розв’язок, тобто існує вектор такий, що Припустимо тоді:

.

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

Припустимо, що система 1 не має розв’язку. Розглянемо замкнуту опуклу множину . За припущенням тоді з огляду на теорему про віддільність опуклої множини і точки, що їй не належить, існують вектор , і число α такі, що Оскільки, , то З іншого боку Компоненти вектора x можуть бути як завгодно великими, тому з останньої нерівності отримуємо Отже, p — розв’язок системи 2.

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

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

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