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

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

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

ФормулировкаПравить

Пусть $f_1(x),f_2(x),...,f_r(x)$$f_{1}(x), f_{2}(x), ..., f_{r}(x)$  и $g(x)$$g(x)$  — однородные линейные функции $m$$m$  вещественных переменных $x_1,x_2,...,x_m$$x_{1}, x_{2}, ..., x_{m}$ . Предположим, что соотношения $f_1(x)⩾<!--\; ⩾\; -->0,f_2(x)⩾<!--\; ⩾\; -->0,...,f_r(x)⩾<!--\; ⩾\; -->0$$f_{1}(x)\geqslant 0,f_{2}(x)\geqslant 0,...,f_{r}(x)\geqslant 0$  влекут за собой неравенство $g(x)⩾<!--\; ⩾\; -->0$$g(x) \geqslant 0$ . Тогда существуют неотрицательные постоянные $y_1,y_2,...,y_r$$y_{1}, y_{2}, ..., y_{r}$ , для которых выполняется тождество

$y_1{f}_1(x)+y_2{f}_2(x)+...+y_r{f}_r(x)\equiv <!--\; \equiv \; -->g(x).$$y_{1}f_{1}(x)+y_{2}f_{2}(x)+...+y_{r}f_{r}(x)\equiv g(x).$ 

ДоказательствоПравить

Доказательство есть в книге .

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

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

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

Пусть $\mathbf{A}\in <!--\; \in \; -->{\mathbb{R}}^{m\times <!--\; \times \; -->n},\mathbf{x}\in <!--\; \in \; -->{\mathbb{R}}^m$$\mathbf {A} \in \mathbb {R} ^{m\times n},\mathbf {x} \in \mathbb {R} ^{m}$ . Тогда либо существует вектор $\mathbf{x}\in <!--\; \in \; -->{\mathbb{R}}^n$${\mathbf {x}}\in {\mathbb {R}}^{n}$  такой, что $\mathbf{A}\mathbf{x}=\mathbf{b}$$\mathbf {A} \mathbf {x} =\mathbf {b}$  и $x⩾<!--\; ⩾\; -->0$$x \geqslant 0$ , либо существует вектор $\mathbf{y}\in <!--\; \in \; -->{\mathbb{R}}^m$$\mathbf {y} \in \mathbb {R} ^{m}$  такой, что ${\mathbf{A}}^{\mathrm{T}}\mathbf{y}⩾<!--\; ⩾\; -->0$$\mathbf {A} ^{\mathrm {T} }\mathbf {y} \geqslant 0$  и $\mathbf {b} ^{\mathrm {T} }\mathbf {y} <0$ .

В этой формулировке столбцы матрицы $\mathbf{A}$$\mathbf {A}$  играют роль линейных функций $f_i(x)$$f_{i}(x)$ , столбец $\mathbf{b}$${\mathbf {b}}$  играет роль функции $g(x)$$g(x)$ , вектор $\mathbf{x}$$\mathbf {x}$  содержит коэффициенты, аналогичные $y_1,y_2,...,y_r$$y_{1}, y_{2}, ..., y_{r}$ . Существование вектора $\mathbf{y}$$\mathbf {y}$  означает, что из исходных неравенств не следует $g(x)⩾<!--\; ⩾\; -->0$$g(x) \geqslant 0$ .

Геометрический смыслПравить

Пусть $C(\mathbf{A})$$C(\mathbf {A} )$  — выпуклый конус, порождённый столбцами матрицы $\mathbf{A}$$\mathbf {A}$ . Его можно описать как множество $\{\mathbf{A}\mathbf{x}\mid <!--\; \mid \; -->\mathbf{x}⩾<!--\; ⩾\; -->0\}$$\{\mathbf {A} \mathbf {x} \mid \mathbf {x} \geqslant 0\}$ . Тогда формулировку Гейла-Куна-Таккера можно переформулировать так: либо вектор $\mathbf{b}$${\mathbf {b}}$  лежит в конусе $C(\mathbf{A})$$C(\mathbf {A} )$ , либо есть гиперплоскость (ортогональная вектору $\mathbf{y}$$\mathbf {y}$ ), разделяющая конус $C(\mathbf{A})$$C(\mathbf {A} )$  и вектор $\mathbf{b}$${\mathbf {b}}$ .

Теорема ГорданаПравить

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

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

В современных терминах она звучит так: либо существует решение $\mathbf{x}$$\mathbf {x}$  неравенства $\mathbf {A} \mathbf {x} <0$ , либо существует ненулевое решение $\mathbf{y}$$\mathbf {y}$  уравнения ${\mathbf{A}}^{\mathrm{T}}\mathbf{y}=0$$\mathbf {A} ^{\mathrm {T} }\mathbf {y} =0$  такое, что $\mathbf{y}⩾<!--\; ⩾\; -->0$$\mathbf {y} \geqslant 0$ .

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

ЛитератураПравить

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