Лема Фаркаша

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

Твердження

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

Доведення

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

.

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

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

Наслідок

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

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

Доведення

Нехай це матриця , де це одинична матриця. Розмірність цієї матриці є рівною 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.