Лемма Фаркаша — утверждение о свойствах линейных неравенств. Была сформулирована и доказана в 1902 году. Применяется в геометрическом программировании.
Формулировка Пусть и — однородные линейные функции вещественных переменных . Предположим, что соотношения влекут за собой неравенство . Тогда существуют неотрицательные постоянные , для которых выполняется тождество
Замечания Доказательство приводится в книге .
Эквивалентные формулировки
Далее под будем подразумевать, что каждая компонента вектора положительна; аналогично определяются другие неравенства.
Формулировка Гейла, Куна и Таккера Пусть . Тогда либо существует вектор такой, что и , либо существует вектор такой, что и .
В этой формулировке столбцы матрицы играют роль линейных функций , столбец играет роль функции , вектор содержит коэффициенты, аналогичные . Существование вектора означает, что из исходных неравенств не следует .
Геометрический смысл Пусть — выпуклый конус, порождённый столбцами матрицы . Его можно описать как множество . Тогда формулировку Гейла-Куна-Таккера можно переформулировать так: либо вектор лежит в конусе , либо есть гиперплоскость (ортогональная вектору ), разделяющая конус и вектор .
Теорема Гордана
В 1873 году П. Гордан опубликовал теорему, эквивалентную открытой позднее, но более известной лемме Фаркаша.
В современных терминах она звучит так: либо существует решение неравенства , либо существует ненулевое решение уравнения такое, что .
Иными словами, либо конус, задаваемый столбцами , острый и существует опорная гиперплоскость, либо он не острый и существует нетривиальная выпуклая комбинация определяющих его векторов, равная нулю.
Примечания
Литература
Категория:Неравенства Фаркаша Категория:Выпуклый анализ Категория:Линейное программирование