Лемма Фаркаша
Лемма Фаркаша — утверждение о свойствах линейных неравенств. Была сформулирована и доказана Дьюлой Фаркашем[англ.] в 1902 году[1]. Применяется в геометрическом программировании.
Формулировка
Пусть [math]\displaystyle{ f_{1}(x), f_{2}(x), ..., f_{r}(x) }[/math] и [math]\displaystyle{ g(x) }[/math] — однородные линейные функции [math]\displaystyle{ m }[/math] вещественных переменных [math]\displaystyle{ x_{1}, x_{2}, ..., x_{m} }[/math]. Предположим, что соотношения [math]\displaystyle{ f_{1}(x) \geqslant 0, f_{2}(x) \geqslant 0, ..., f_{r}(x) \geqslant 0 }[/math] влекут за собой неравенство [math]\displaystyle{ g(x) \geqslant 0 }[/math]. Тогда существуют неотрицательные постоянные [math]\displaystyle{ y_{1}, y_{2}, ..., y_{r} }[/math], для которых выполняется тождество
- [math]\displaystyle{ y_{1}f_{1}(x)+y_{2} f_{2}(x)+ ... +y_{r}f_{r}(x) \equiv g(x). }[/math]
Доказательство
Доказательство есть в книге [2].
Эквивалентные формулировки
Далее под [math]\displaystyle{ \mathbf{x}\gt 0 }[/math] будем подразумевать, что каждая компонента вектора положительна; аналогично определяются другие неравенства.
Формулировка Гейла, Куна и Таккера
Пусть [math]\displaystyle{ \mathbf{A} \in \mathbb{R}^{m\times n}, \mathbf{x} \in \mathbb{R}^m }[/math]. Тогда либо существует вектор [math]\displaystyle{ \mathbf{x} \in \mathbb{R}^n }[/math] такой, что [math]\displaystyle{ \mathbf{A}\mathbf{x} = \mathbf{b} }[/math] и [math]\displaystyle{ x \geqslant 0 }[/math], либо существует вектор [math]\displaystyle{ \mathbf{y} \in \mathbb{R}^m }[/math] такой, что [math]\displaystyle{ \mathbf{A}^\mathrm{T} \mathbf{y} \geqslant 0 }[/math] и [math]\displaystyle{ \mathbf{b}^\mathrm{T} \mathbf{y} \lt 0 }[/math][3].
В этой формулировке столбцы матрицы [math]\displaystyle{ \mathbf{A} }[/math] играют роль линейных функций [math]\displaystyle{ f_i (x) }[/math], столбец [math]\displaystyle{ \mathbf{b} }[/math] играет роль функции [math]\displaystyle{ g(x) }[/math], вектор [math]\displaystyle{ \mathbf{x} }[/math] содержит коэффициенты, аналогичные [math]\displaystyle{ y_{1}, y_{2}, ..., y_{r} }[/math]. Существование вектора [math]\displaystyle{ \mathbf{y} }[/math] означает, что из исходных неравенств не следует [math]\displaystyle{ g(x) \geqslant 0 }[/math].
Геометрический смысл
Пусть [math]\displaystyle{ C(\mathbf{A}) }[/math] — выпуклый конус, порождённый столбцами матрицы [math]\displaystyle{ \mathbf{A} }[/math]. Его можно описать как множество [math]\displaystyle{ \{\mathbf{A}\mathbf{x} \mid \mathbf{x} \geqslant 0 \} }[/math]. Тогда формулировку Гейла-Куна-Таккера можно переформулировать так: либо вектор [math]\displaystyle{ \mathbf{b} }[/math] лежит в конусе [math]\displaystyle{ C(\mathbf{A}) }[/math], либо есть гиперплоскость (ортогональная вектору [math]\displaystyle{ \mathbf{y} }[/math]), разделяющая конус [math]\displaystyle{ C(\mathbf{A}) }[/math] и вектор [math]\displaystyle{ \mathbf{b} }[/math].
Теорема Гордана
В 1873 году П. Гордан опубликовал теорему, эквивалентную открытой позднее, но более известной лемме Фаркаша[4].
В современных терминах она звучит так: либо существует решение [math]\displaystyle{ \mathbf{x} }[/math] неравенства [math]\displaystyle{ \mathbf{A}\mathbf{x} \lt 0 }[/math], либо существует ненулевое решение [math]\displaystyle{ \mathbf{y} }[/math] уравнения [math]\displaystyle{ \mathbf{A}^\mathrm{T} \mathbf{y} = 0 }[/math] такое, что [math]\displaystyle{ \mathbf{y} \geqslant 0 }[/math].
Иными словами, либо конус, задаваемый столбцами [math]\displaystyle{ \mathbf{A} }[/math], острый и существует опорная гиперплоскость, либо он не острый и существует нетривиальная выпуклая комбинация определяющих его векторов, равная нулю.
Примечания
- ↑ Farkas, J. Theorie der Einfachen Ungleichungen (нем.) // Journal für die reine und angewandte Mathematik. — 1902. — Bd. 124. — S. 1—27. — doi:10.1515/crll.1902.124.1.
- ↑ Геометрическое программирование, 1972, с. 263.
- ↑ Gale, D., Kuhn, H., Tucker, A. W. Linear Programming and the Theory of Games - Chapter XII // Activity Analysis of Production and Allocation (англ.) / Koopmans (ed.). — Wiley, 1951. — P. 318.
- ↑ Cherng-Tiao Perng. A Note on Gordan's Theorem (англ.) // British Journal of Mathematics & Computer Science. — 2015-01-10. — Vol. 10, iss. 5. — P. 1–6. — doi:10.9734/BJMCS/2015/19134. Архивировано 14 сентября 2021 года.
Литература
- Р. Даффин, Э. Питерсон, К. Зенер. Геометрическое программирование. — М.: Мир, 1972. — 311 с.