Farkas lemma

Farkas lemma är ett uttalande om egenskaperna hos linjära ojämlikheter. Den formulerades och bevisades av Gyula Farkas 1902 [1] . Används vid geometrisk programmering .

Formulering

Låta och vara homogena linjära funktioner av reella variabler . Låt oss anta att relationerna medför ojämlikheten . Sedan finns det icke-negativa konstanter för vilka identiteten $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).

Bevis

Beviset finns i boken [2] .

Motsvarande formuleringar

I det följande menar vi att varje komponent i vektorn är positiv; andra ojämlikheter definieras på liknande sätt. $\mathbf {x} >0$

Gale, Kuhn och Tuckers formulering

Låt . Sedan antingen finns det en vektor sådan att och , eller så finns det en vektor som och [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$

I denna formulering spelar matriskolumnerna rollen som linjära funktioner , kolumnen spelar rollen som en funktion , vektorn innehåller koefficienter som liknar . Förekomsten av en vektor betyder att de initiala ojämlikheterna inte innebär . $\mathbf {A}$ $f_{i}(x)$ ${\mathbf {b}}$ $g(x)$ $\mathbf {x}$ $y_{1}, y_{2}, ..., y_{r}$ $\mathbf {y}$ $g(x) \geqslant 0$

Geometrisk känsla

Låta vara en konvex kon som genereras av kolumnerna i matrisen . Det kan beskrivas som en uppsättning . Sedan kan Gale-Kuhn-Tucker-formuleringen omformuleras enligt följande: antingen ligger vektorn i konen eller så finns det ett hyperplan (ortogonalt mot vektorn ) som skiljer konen och vektorn åt . $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}}$

Gordans teorem

1873 publicerade P. Gordan ett teorem som motsvarar det senare upptäckta men mer kända Farkas-lemmat [4] .

I moderna termer låter det så här: antingen finns det en lösning på ojämlikheten , eller så finns det en lösning som inte är noll på ekvationen så att . $\mathbf {x}$ $\mathbf {A} \mathbf {x} <0$ $\mathbf {y}$ $\mathbf {A} ^{\mathrm {T} }\mathbf {y} =0$ $\mathbf {y} \geqslant 0$

Med andra ord, antingen är konen som definieras av kolumnerna skarp och det finns ett stödhyperplan , eller så är den inte skarp och det finns en icke-trivial konvex kombination av vektorer som definierar den, lika med noll. $\mathbf {A}$

Anteckningar

↑ Farkas, J. Theorie der Einfachen Ungleichungen (tyska) // Journal für die reine und angewandte Mathematik . - 1902. - Bd. 124. - S. 1-27 . - doi : 10.1515/crll.1902.124.1 .
↑ Geometrisk programmering, 1972 , sid. 263.
↑ Gale, D. , Kuhn, H. , Tucker, A. W. Linjär programmering och teorin om spel - Kapitel XII // Aktivitetsanalys av produktion och allokering (engelska) / Koopmans (red.). - Wiley , 1951. - S. 318.
↑ Cherng-Tiao Perng. A Note on Gordan's Theorem // British Journal of Mathematics & Computer Science. — 2015-01-10. — Vol. 10 , iss. 5 . — S. 1–6 . - doi : 10.9734/BJMCS/2015/19134 . Arkiverad från originalet den 14 september 2021.

Litteratur

R. Duffin, E. Peterson, K. Zener. Geometrisk programmering. - M . : Mir, 1972. - 311 sid.