Farkasovo lemma

Farkasovo lemma je tvrzení o vlastnostech lineárních nerovnic. Zformuloval a dokázal jej Gyula Farkas v roce 1902 [1] . Používá se v geometrickém programování .

Formulace

Nechť a být homogenní lineární funkce reálných proměnných . Předpokládejme, že vztahy obsahují nerovnost . Pak existují nezáporné konstanty , pro které je identita $f_{1}(x), f_{2}(x), ..., f_{r}(x)$ $g(x)$ $m$ $x_{1}, x_{2}, ..., x_{m}$ $f_{1}(x)\geqslant 0,f_{2}(x)\geqslant 0,...,f_{r}(x)\geqslant 0$ $g(x) \geqslant 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).

Důkaz

Důkaz je v knize [2] .

Ekvivalentní formulace

V následujícím máme na mysli, že každá složka vektoru je kladná; ostatní nerovnosti jsou definovány podobně. $\mathbf {x} >0$

Formulace Galea, Kuhna a Tuckera

Nechte _ Pak buď existuje vektor jako a , nebo existuje vektor jako a [3] . ${\displaystyle \mathbf {A} \in \mathbb {R} ^{m\times n},\mathbf {x} \in \mathbb {R} ^{m))$ ${\mathbf {x}}\in {\mathbb {R}}^{n}$ $\mathbf {A} \mathbf {x} =\mathbf {b}$ $x \geqslant 0$ ${\displaystyle \mathbf {y} \in \mathbb {R} ^{m))$ $\mathbf {A} ^{\mathrm {T} }\mathbf {y} \geqslant 0$ $\mathbf {b} ^{\mathrm {T} }\mathbf {y} <0$

V této formulaci hrají sloupce matice roli lineárních funkcí , sloupec hraje roli funkce , vektor obsahuje koeficienty podobné . Existence vektoru znamená, že počáteční nerovnosti neimplikují . $\mathbf {A}$ $f_{i}(x)$ ${\mathbf {b}}$ $g(x)$ $\mathbf {x}$ $y_{1}, y_{2}, ..., y_{r}$ $\mathbf {y}$ $g(x) \geqslant 0$

Geometrický smysl

Dovolit být konvexní kužel vytvořený sloupci matice . Dá se to popsat jako komplet . Potom lze Gale-Kuhn-Tuckerovu formulaci přeformulovat následovně: buď vektor leží v kuželu , nebo existuje nadrovina (ortogonální k vektoru ), která odděluje kužel a vektor . $C(\mathbf {A} )$ $\mathbf {A}$ ${\displaystyle \{\mathbf {A} \mathbf {x} \mid \mathbf {x} \geqslant 0\))$ ${\mathbf {b}}$ $C(\mathbf {A} )$ $\mathbf {y}$ $C(\mathbf {A} )$ ${\mathbf {b}}$

Gordanova věta

V roce 1873 publikoval P. Gordan větu ekvivalentní později objevenému, ale známějšímu Farkasovu lemmatu [4] .

V moderním pojetí to zní takto: buď existuje řešení nerovnosti , nebo existuje nenulové řešení rovnice takové, že . $\mathbf {x}$ $\mathbf {A} \mathbf {x} <0$ $\mathbf {y}$ $\mathbf {A} ^{\mathrm {T} }\mathbf {y} =0$ $\mathbf {y} \geqslant 0$

Jinými slovy, buď je kužel definovaný sloupci ostrý a existuje podpůrná nadrovina , nebo není ostrý a existuje netriviální konvexní kombinace vektorů, která jej definuje, rovna nule. $\mathbf {A}$

Poznámky

↑ Farkas, J. Theorie der Einfachen Ungleichungen (německy) // Journal für die reine und angewandte Mathematik . - 1902. - Bd. 124. - S. 1-27 . - doi : 10.1515/crll.1902.124.1 .
↑ Geometrické programování, 1972 , str. 263.
↑ Gale, D. , Kuhn, H. , Tucker, A. W. Lineární programování a teorie her - kapitola XII // Analýza činností produkce a alokace (anglicky) / Koopmans (ed.). - Wiley , 1951. - S. 318.
↑ Cherng-Tiao Perng. Poznámka ke Gordanově větě // British Journal of Mathematics & Computer Science. — 2015-01-10. — Sv. 10 , iss. 5 . — S. 1–6 . – doi : 10.9734/BJMCS/2015/19134 . Archivováno z originálu 14. září 2021.

Literatura

R. Duffin, E. Peterson, K. Zener. Geometrické programování. - M .: Mir, 1972. - 311 s.