Farkas' lemma

Farkas-lemmaet er et udsagn om egenskaberne ved lineære uligheder. Det blev formuleret og bevist af Gyula Farkas i 1902 [1] . Anvendes i geometrisk programmering .

Ordlyd

Lad og være homogene lineære funktioner af reelle variable . Lad os antage, at relationerne medfører uligheden . Så er der ikke-negative konstanter , for hvilke 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 findes i bogen [2] .

Tilsvarende formuleringer

I det følgende mener vi, at hver komponent i vektoren er positiv; andre uligheder defineres på samme måde. $\mathbf {x} >0$

Gale, Kuhn og Tuckers formulering

Lad . Så eksisterer der enten en vektor sådan, at og , eller der findes en vektor som og [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 denne formulering spiller matrixkolonnerne rollen som lineære funktioner , kolonnen spiller rollen som en funktion , vektoren indeholder koefficienter svarende til . Eksistensen af en vektor betyder, at de oprindelige uligheder ikke indebærer . $\mathbf {A}$ $f_{i}(x)$ ${\mathbf {b}}$ $g(x)$ $\mathbf {x}$ $y_{1}, y_{2}, ..., y_{r}$ $\mathbf {y}$ $g(x) \geqslant 0$

Geometrisk sans

Lade være en konveks kegle genereret af søjlerne i matrixen . Det kan beskrives som et sæt . Så kan Gale-Kuhn-Tucker-formuleringen omformuleres som følger: enten ligger vektoren i keglen , eller også er der et hyperplan (ortogonalt på vektoren ), der adskiller keglen og vektoren . $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 sætning

I 1873 udgav P. Gordan en sætning svarende til det senere opdagede, men bedre kendte Farkas-lemma [4] .

I moderne termer lyder det sådan: enten er der en løsning på uligheden , eller også er der en ikke-nul løsning af ligningen sådan at . $\mathbf {x}$ $\mathbf {A} \mathbf {x} <0$ $\mathbf {y}$ $\mathbf {A} ^{\mathrm {T} }\mathbf {y} =0$ $\mathbf {y} \geqslant 0$

Med andre ord, enten er keglen defineret af søjlerne skarp , og der er et støttehyperplan , eller også er den ikke skarp, og der er en ikke-trivial konveks kombination af vektorer, der definerer den, lig med nul. $\mathbf {A}$

Noter

↑ Farkas, J. Theorie der Einfachen Ungleichungen (tysk) // Journal für die reine und angewandte Mathematik . - 1902. - Bd. 124. - S. 1-27 . - doi : 10.1515/crll.1902.124.1 .
↑ Geometric Programming, 1972 , s. 263.
↑ Gale, D. , Kuhn, H. , Tucker, A. W. Lineær programmering og teorien om spil - Kapitel XII // Aktivitetsanalyse af produktion og tildeling (engelsk) / Koopmans (red.). - Wiley , 1951. - S. 318.
↑ Cherng-Tiao Perng. A Note on Gordan's Theorem // British Journal of Mathematics & Computer Science. — 2015-01-10. — Bd. 10 , iss. 5 . — S. 1–6 . - doi : 10.9734/BJMCS/2015/19134 . Arkiveret fra originalen den 14. september 2021.

Litteratur

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