Лема Фаркаша

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

Твердження

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

1. $Ax=b,x\ge 0,x\in {ℝ}^n$
2. $y^{\mathrm{\top }}A\le 0,⟨y,b⟩>0y\in {ℝ}^m.$

Доведення

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

$0<⟨y,b⟩=⟨y,Ax⟩=⟨y^{\mathrm{\top }}A,x⟩\le 0$.

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

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

Наслідок

Для дійсної матриці A розмірності m × n і $b\in {ℝ}^m$ має розв'язок одна і тільки одна з таких систем:

1. $Ax\le b,x\in {ℝ}^n,$
2. $A^{T}y=0,b^{T}y<0,y\in {ℝ}^m,y\ge 0.$

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

Доведення

Нехай $A^{\prime }$ це матриця $A^{\prime }:=[A-AI]$, де $I$ це одинична матриця. Розмірність цієї матриці є рівною m × (2n+m).

Система нерівностей $Ax\le b$ має розв'язок $x$ тоді і тільки тоді, коли система рівнянь $A^{\prime }{x}^{\prime }=b$ має невід'ємний розв'язок $x^{\prime }\in {ℝ}^{2n+m}$. Справді, якщо система рівнянь має такий розв'язок то позначивши $x_i=x{\text{'}}_i-x{\text{'}}_{n+i}$ одержуємо $Ax+x^{″}=b,$ де $x^{″}\in {ℝ}^m$ позначає вектор елементами якого є $x^{\prime }{\text{'}}_i=x{\text{'}}_{2n+i}.$ Оскільки усі $x^{\prime }{\text{'}}_i\ge 0,$ то звідси одержуємо $Ax\le b.$

Якщо ж $Ax\le b$ має розв'язок $x\in {ℝ}^n,$ то можна знайти розв'язок системи рівнянь $A^{\prime }{x}^{\prime }=b$. Для цього для кожного індексу i, якщо $x_i\ge 0,$ то нехай $x{\text{'}}_i:=x_i,x{\text{'}}_{n+i}:=0.$ Якщо $x_i<0,$ то нехай $x{\text{'}}_i:=0,x{\text{'}}_{n+i}:=-x_i.$ Значеннями $x{\text{'}}_{2n+i}$ визначимо різницю $b_i$ і добутку i-го рядка матриці A і вектора x. Тоді так визначений вектор $x^{\prime }\in {ℝ}^{2n+m}$ є розв'язком системи рівнянь $A^{\prime }{x}^{\prime }=b.$

Застосовуючи лему Фаркаша до системи $A^{\prime }{x}^{\prime }=b$ отримуємо твердження наслідку.

Лема Фаркаша випливає із теореми Гейла

Навпаки із теореми Гейла можна довести лему Фаркаша. Як і вище доводиться, що система $y^{\mathrm{\top }}A\le 0,y\in {ℝ}^m$ (яку транспонувавши зручніше розглядати у виді $A^{\mathrm{\top }}y\le 0$) має розв'язок тоді і тільки тоді коли має розв'язок невід'ємний розв'язок система $A^{\prime }{y}^{\prime }=0,$ де

$A^{\prime }:=[A^{\mathrm{\top }}-A^{\mathrm{\top }}I]$ є матрицею розмірності n × (2m + n). Додаткова умова $⟨y,b⟩>0$ при цьому виконується тоді і лише тоді коли для відповідного вектора $y^{\prime }$ (що одержується із $y$, як $x^{\prime }$ із $x$ вище) виконується умова $⟨y^{\prime },b^{\prime }⟩<0,$ де $b^{\prime }$ є вектором перші m координат якого є рівні відповідним координатам вектора $b$ помноженим на -1, наступні m координат є рівні відповідним координатам вектора $b$, а останні n координат є рівні 0.

Відповідно якщо друга система у твердженні леми Фаркаша не має розв'язків то система $A^{\prime }{y}^{\prime }=0$ не має невід'ємних розв'язків, що задовольняють нерівність $⟨y^{\prime },b^{\prime }⟩<0.$ Тоді із теореми Гейла випливає існування $x^{\prime }\in {ℝ}^n$ для якого $A{x}^{\prime }\le -b,-A{x}^{\prime }\le b,x^{\prime }\le 0.$ Тоді $x=x^{\prime }$ є розв'язком першої системи в умові леми Фаркаша.

Див. також

• Метод Фур'є — Моцкіна

Посилання

• Моклячук М.П. Основи опуклого аналізу. Шаблон:Webarchive К.:ТвіМС, 2004. – 240с.

Література

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