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

Шаблон:Другие значения термина Лемма Фаркаша — утверждение о свойствах линейных неравенств. Была сформулирована и доказана Шаблон:Iw в 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).$

Замечания

Доказательство приводится в книге Шаблон:Sfn.

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

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

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

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

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

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

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

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

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

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

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

Литература

• Шаблон:Книга