Лемма Фаркаша

Для термина «Фаркаш» см. также другие значения.

Лемма Фаркаша — утверждение о свойствах линейных неравенств. Была сформулирована и доказана Дьюлой Фаркашем в 1902 году. Применяется в геометрическом программировании.

Формулировка

Пусть $f_{1}(x),f_{2}(x),...,f_{r}(x)$ и $g(x)$ — однородные линейные функции $m$ вещественных переменных $x_{1},x_{2},...,x_{m}$. Предположим, что соотношения $f_{1}(x)\geqslant 0,f_{2}(x)\geqslant 0,...,f_{r}(x)\geqslant 0$ влекут за собой неравенство $g(x)\geqslant 0$. Тогда существуют неотрицательные постоянные $y_{1},y_{2},...,y_{r}$, для которых выполняется тождество

$y_{1}f_{1}(x)+y_{2}f_{2}(x)+...+y_{r}f_{r}(x)\equiv g(x).$

Доказательство

Доказательство есть в книге .

Эквивалентные формулировки

Далее под $\mathbf {x} >0$ будем подразумевать, что каждая компонента вектора положительна; аналогично определяются другие неравенства.

Формулировка Гейла, Куна и Таккера

Пусть $\mathbf {A} \in \mathbb {R} ^{m\times n},\mathbf {x} \in \mathbb {R} ^{m}$. Тогда либо существует вектор $\mathbf {x} \in \mathbb {R} ^{n}$ такой, что $\mathbf {A} \mathbf {x} =\mathbf {b}$ и $x\geqslant 0$, либо существует вектор $\mathbf {y} \in \mathbb {R} ^{m}$ такой, что $\mathbf {A} ^{\mathrm {T} }\mathbf {y} \geqslant 0$ и $\mathbf {b} ^{\mathrm {T} }\mathbf {y} <0$.

В этой формулировке столбцы матрицы $\mathbf {A}$ играют роль линейных функций $f_{i}(x)$, столбец $\mathbf {b}$ играет роль функции $g(x)$, вектор $\mathbf {x}$ содержит коэффициенты, аналогичные $y_{1},y_{2},...,y_{r}$. Существование вектора $\mathbf {y}$ означает, что из исходных неравенств не следует $g(x)\geqslant 0$.

Геометрический смысл

Пусть $C(\mathbf {A} )$ — выпуклый конус, порождённый столбцами матрицы $\mathbf {A}$. Его можно описать как множество $\{\mathbf {A} \mathbf {x} \mid \mathbf {x} \geqslant 0\}$. Тогда формулировку Гейла-Куна-Таккера можно переформулировать так: либо вектор $\mathbf {b}$ лежит в конусе $C(\mathbf {A} )$, либо есть гиперплоскость (ортогональная вектору $\mathbf {y}$), разделяющая конус $C(\mathbf {A} )$ и вектор $\mathbf {b}$.

Теорема Гордана

Не следует путать с леммой Гордана.

В 1873 году П. Гордан опубликовал теорему, эквивалентную открытой позднее, но более известной лемме Фаркаша.

В современных терминах она звучит так: либо существует решение $\mathbf {x}$ неравенства $\mathbf {A} \mathbf {x} <0$, либо существует ненулевое решение $\mathbf {y}$ уравнения $\mathbf {A} ^{\mathrm {T} }\mathbf {y} =0$ такое, что $\mathbf {y} \geqslant 0$.

Иными словами, либо конус, задаваемый столбцами $\mathbf {A}$, острый и существует опорная гиперплоскость, либо он не острый и существует нетривиальная выпуклая комбинация определяющих его векторов, равная нулю.

Литература

• Р. Даффин, Э. Питерсон, К. Зенер. Геометрическое программирование. — М.: Мир, 1972. — 311 с.