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

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

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

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

Пусть $f_1(x),f_2(x),...,f_r(x)$ и $g(x)$ — однородные линейные функции $m$ вещественных переменных $x_1,x_2,...,x_m$. Предположим, что соотношения $f_1(x)⩾0,f_2(x)⩾0,...,f_r(x)⩾0$ влекут за собой неравенство $g(x)⩾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{𝐱}>0$ будем подразумевать, что каждая компонента вектора положительна; аналогично определяются другие неравенства.

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

Пусть $\mathbf{𝐀}\in {\mathbb{ℝ}}^{m\times n},\mathbf{𝐱}\in {\mathbb{ℝ}}^m$. Тогда либо существует вектор $\mathbf{𝐱}\in {\mathbb{ℝ}}^n$ такой, что $\mathbf{𝐀}\mathbf{𝐱}=\mathbf{𝐛}$ и $x⩾0$, либо существует вектор $\mathbf{𝐲}\in {\mathbb{ℝ}}^m$ такой, что ${\mathbf{𝐀}}^{\mathrm{T}}\mathbf{𝐲}⩾0$ и ${\mathbf{𝐛}}^{\mathrm{T}}\mathbf{𝐲}<0$.

В этой формулировке столбцы матрицы $\mathbf{𝐀}$ играют роль линейных функций $f_i(x)$, столбец $\mathbf{𝐛}$ играет роль функции $g(x)$, вектор $\mathbf{𝐱}$ содержит коэффициенты, аналогичные $y_1,y_2,...,y_r$. Существование вектора $\mathbf{𝐲}$ означает, что из исходных неравенств не следует $g(x)⩾0$.

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

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

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

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

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

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

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

Литература

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