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

ТвердженняРедагувати

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

  1.  
  2.  

ДоведенняРедагувати

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

 .

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

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

НаслідокРедагувати

Для дійсної матриці A розмірності m × n і   має розв'язок одна і тільки одна з таких систем:

  1.  
  2.  

Дане твердження іноді називають теоремою Гейла.

ДоведенняРедагувати

Нехай   це матриця  , де   це одинична матриця. Розмірність цієї матриці є рівною 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