Русская Википедия:Лемма Фаркаша
Шаблон:Другие значения термина Лемма Фаркаша — утверждение о свойствах линейных неравенств. Была сформулирована и доказана Шаблон:Iw в 1902 году[1]. Применяется в геометрическом программировании.
Формулировка
Пусть <math>f_{1}(x), f_{2}(x), ..., f_{r}(x)</math> и <math>g(x)</math> — однородные линейные функции <math>m</math> вещественных переменных <math>x_{1}, x_{2}, ..., x_{m}</math>. Предположим, что соотношения <math>f_{1}(x) \geqslant 0, f_{2}(x) \geqslant 0, ..., f_{r}(x) \geqslant 0</math> влекут за собой неравенство <math>g(x) \geqslant 0</math>. Тогда существуют неотрицательные постоянные <math>y_{1}, y_{2}, ..., y_{r}</math>, для которых выполняется тождество
- <math>y_{1}f_{1}(x)+y_{2} f_{2}(x)+ ... +y_{r}f_{r}(x) \equiv g(x).</math>
Доказательство
Доказательство есть в книге Шаблон:Sfn.
Эквивалентные формулировки
Далее под <math>\mathbf{x}>0</math> будем подразумевать, что каждая компонента вектора положительна; аналогично определяются другие неравенства.
Формулировка Гейла, Куна и Таккера
Пусть <math>\mathbf{A} \in \mathbb{R}^{m\times n}, \mathbf{x} \in \mathbb{R}^m</math>. Тогда либо существует вектор <math>\mathbf{x} \in \mathbb{R}^n</math> такой, что <math>\mathbf{A}\mathbf{x} = \mathbf{b}</math> и <math>x \geqslant 0</math>, либо существует вектор <math>\mathbf{y} \in \mathbb{R}^m</math> такой, что <math>\mathbf{A}^\mathrm{T} \mathbf{y} \geqslant 0</math> и <math>\mathbf{b}^\mathrm{T} \mathbf{y} < 0 </math>[2].
В этой формулировке столбцы матрицы <math>\mathbf{A}</math> играют роль линейных функций <math>f_i (x)</math>, столбец <math>\mathbf{b}</math> играет роль функции <math>g(x)</math>, вектор <math>\mathbf{x}</math> содержит коэффициенты, аналогичные <math>y_{1}, y_{2}, ..., y_{r}</math>. Существование вектора <math>\mathbf{y}</math> означает, что из исходных неравенств не следует <math>g(x) \geqslant 0</math>.
Геометрический смысл
Пусть <math>C(\mathbf{A})</math> — выпуклый конус, порождённый столбцами матрицы <math>\mathbf{A}</math>. Его можно описать как множество <math>\{\mathbf{A}\mathbf{x} \mid \mathbf{x} \geqslant 0 \}</math>. Тогда формулировку Гейла-Куна-Таккера можно переформулировать так: либо вектор <math>\mathbf{b}</math> лежит в конусе <math>C(\mathbf{A})</math>, либо есть гиперплоскость (ортогональная вектору <math>\mathbf{y}</math>), разделяющая конус <math>C(\mathbf{A})</math> и вектор <math>\mathbf{b}</math>.
Теорема Гордана
Шаблон:Не путать В 1873 году П. Гордан опубликовал теорему, эквивалентную открытой позднее, но более известной лемме Фаркаша[3].
В современных терминах она звучит так: либо существует решение <math>\mathbf{x}</math> неравенства <math>\mathbf{A}\mathbf{x} < 0 </math>, либо существует ненулевое решение <math>\mathbf{y}</math> уравнения <math>\mathbf{A}^\mathrm{T} \mathbf{y} = 0</math> такое, что <math>\mathbf{y} \geqslant 0 </math>.
Иными словами, либо конус, задаваемый столбцами <math>\mathbf{A}</math>, острый и существует опорная гиперплоскость, либо он не острый и существует нетривиальная выпуклая комбинация определяющих его векторов, равная нулю.
Примечания
Литература
