Лема Фаркаша

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

Твердження

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

1. ${\displaystyle Ax=b,\quad x\geq 0,\quad x\in \mathbb {R} ^{n}}$
2. ${\displaystyle y^{\top }A\leq 0,\quad \langle y,b\rangle >0\quad y\in \mathbb {R} ^{m}.}$

Доведення

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

${\displaystyle 0<\langle y,b\rangle =\langle y,Ax\rangle =\langle y^{\top }A,x\rangle \leq 0}$.

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

Припустимо, що система 1 не має розв’язку. Розглянемо замкнуту опуклу множину ${\displaystyle Z=\left\{c:c=Ax,\;x\geq 0\right\}}$. За припущенням ${\displaystyle b\notin Z,}$ тоді з огляду на теорему про віддільність опуклої множини і точки, що їй не належить, існують вектор ${\displaystyle p\in \mathbb {R} ^{n},p\neq 0}$ , і число α такі, що ${\displaystyle \left\langle p,b\right\rangle >\alpha ,\quad \;\left\langle p,c\right\rangle \leq \alpha \quad \forall c\in Z.}$ Оскільки, ${\displaystyle 0\in Z}$ , то ${\displaystyle \alpha \geq 0,\,\left\langle p,b\right\rangle >\alpha \geq 0.}$ З іншого боку ${\displaystyle \alpha \geq \left\langle p,Ax\right\rangle =\left\langle p^{\top }A,x\right\rangle .}$ Компоненти вектора x можуть бути як завгодно великими, тому з останньої нерівності отримуємо ${\displaystyle p^{\top }A\leq 0.}$ Отже, p — розв’язок системи 2.

Наслідок

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

1. ${\displaystyle Ax\leq b,\quad x\in \mathbb {R} ^{n},}$
2. ${\displaystyle A^{T}y=0,\quad b^{T}y<0,\quad y\in \mathbb {R} ^{m},\quad y\geq 0.}$

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

Доведення

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

Система нерівностей ${\displaystyle Ax\leq b}$ має розв'язок ${\displaystyle x}$ тоді і тільки тоді, коли система рівнянь ${\displaystyle A'x'=b}$ має невід'ємний розв'язок ${\displaystyle x'\in \mathbb {R} ^{2n+m}}$. Справді, якщо система рівнянь має такий розв'язок то позначивши ${\displaystyle x_{i}=x'_{i}-x'_{n+i}}$ одержуємо ${\displaystyle Ax+x''=b,}$ де ${\displaystyle x''\in \mathbb {R} ^{m}}$ позначає вектор елементами якого є ${\displaystyle x''_{i}=x'_{2n+i}.}$ Оскільки усі ${\displaystyle x''_{i}\geq 0,}$ то звідси одержуємо ${\displaystyle Ax\leq b.}$

Якщо ж ${\displaystyle Ax\leq b}$ має розв'язок ${\displaystyle x\in \mathbb {R} ^{n},}$ то можна знайти розв'язок системи рівнянь ${\displaystyle A'x'=b}$. Для цього для кожного індексу i, якщо ${\displaystyle x_{i}\geq 0,}$ то нехай ${\displaystyle x'_{i}:=x_{i},\ x'_{n+i}:=0.}$ Якщо ${\displaystyle x_{i}<0,}$ то нехай ${\displaystyle x'_{i}:=0,\ x'_{n+i}:=-x_{i}.}$ Значеннями ${\displaystyle x'_{2n+i}}$ визначимо різницю ${\displaystyle b_{i}}$ і добутку i-го рядка матриці A і вектора x. Тоді так визначений вектор ${\displaystyle x'\in \mathbb {R} ^{2n+m}}$ є розв'язком системи рівнянь ${\displaystyle A'x'=b.}$

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

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

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

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

Відповідно якщо друга система у твердженні леми Фаркаша не має розв'язків то система ${\displaystyle A'y'=0}$ не має невід'ємних розв'язків, що задовольняють нерівність ${\displaystyle \langle y',b'\rangle <0.}$ Тоді із теореми Гейла випливає існування ${\displaystyle x'\in \mathbb {R} ^{n}}$ для якого ${\displaystyle Ax'\leq -b,\quad -Ax'\leq b,\quad x'\leq 0.}$ Тоді ${\displaystyle x=x'}$ є розв'язком першої системи в умові леми Фаркаша.

Див. також

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

Посилання

• Моклячук М.П. Основи опуклого аналізу. [ 5 липня 2016 у Wayback Machine.] К.:ТвіМС, 2004. – 240с.

Література

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