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

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

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

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

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

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

Замечания

Доказательство приводится в книге ^[2].

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

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

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

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

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

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

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

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

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

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

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

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