Farkasovo lemma - Farkas lemma - Wikipedia
Farkasovo lemma je teorém řešitelnosti pro konečný systém lineární nerovnosti v matematice. Původně to prokázal maďarský matematik Gyula Farkas.[1]Farkaš lemma je klíčovým výsledkem, o který se opírá lineární programování dualita a hrála ústřední roli ve vývoji matematická optimalizace (alternativně, matematické programování ). Používá se mimo jiné v dokladu o Karush – Kuhn – Tuckerova věta v nelineární programování.[2]Je pozoruhodné, že v oblasti základů kvantové teorie je lemma také základem celé sady Nerovnosti zvonu v podobě nezbytných a dostatečných podmínek pro existenci a lokální teorie skrytých proměnných, dané údaje z jakékoli konkrétní sady měření.[3]
Zevšeobecnění Farkasova lematu je o teorému řešitelnosti pro konvexní nerovnosti,[4] tj. nekonečný systém lineárních nerovností. Farkasovo lema patří do třídy příkazů zvaných „věty alternativy“: věta o tom, že právě jeden ze dvou systémů má řešení.
Prohlášení o lemmatu
V literatuře existuje řada mírně odlišných (ale ekvivalentních) formulací lemmatu. Ten, který je zde uveden, je způsoben Galeem, Kuhnem a Tuckerem (1951).[5]
Farkasovo lemma — Nechat a . Pak platí přesně jedno z následujících dvou tvrzení:
- Existuje takhle a .
- Existuje a takhle a .
Tady notace znamená, že všechny složky vektoru jsou negativní.
Příklad
Nechat m, n = 2, , a . Lemma říká, že přesně jeden z následujících dvou příkazů musí být pravdivý (v závislosti na b1 a b2):
- Existují X1 ≥ 0, X2 ≥ 0 takové, že 6 X1 + 4 X2 = b1 a 3 X1 = b2nebo
- Existují y1, y2 tak, že 6 y1 + 3 y2 ≥ 0, 4 y1 ≥ 0 a b1 y1 + b2 y2 < 0.
Zde je důkaz lemmatu v tomto zvláštním případě:
- Li b2 ≥ 0 a b1 − 2b2 ≥ 0, pak je možnost 1 pravdivá, protože řešení lineárních rovnic je X1 = b2/ 3 a X2 = b1-2b2. Možnost 2 je nepravdivá b1 y1 + b2 y2 ≥ b2 (2 y1 + y2) = b2 (6 y1 + 3 y2) / 3, takže pokud je pravá strana kladná, musí být kladná i levá strana.
- V opačném případě je možnost 1 nepravdivá, protože jedinečné řešení lineárních rovnic není slabě pozitivní. V tomto případě však platí možnost 2:
- Li b2 <0, pak můžeme vzít např. y1 = 0 a y2 = 1.
- Li b1 − 2b2 <0, tedy pro nějaké číslo B > 0, b1 = 2b2 - B, takže: b1 y1 + b2 y2 = 2 b2 y1 + b2 y2 − B y1 = b2 (6 y1 + 3 y2) / 3 − B y1. Můžeme tedy vzít například y1 = 1, y2 = −2.
Geometrická interpretace
Zvažte Zavřeno konvexní kužel rozložený sloupy ; to je
Dodržujte to je sada vektorů pro které platí první tvrzení ve výroku Farkasova lematu. Na druhou stranu vektor ve druhém tvrzení je kolmý na a nadrovina který odděluje a . Lemma vyplývá z pozorování patří právě tehdy, pokud neexistuje žádná nadrovina, která ji odděluje .
Přesněji řečeno označit sloupce . Pokud jde o tyto vektory, Farkasovo lemma uvádí, že právě jeden z následujících dvou příkazů je pravdivý:
- Existují nezáporné koeficienty takhle .
- Existuje vektor takhle pro , a .
Součty s nezápornými koeficienty tvoří kužel rozložený sloupy . Proto to říká první výrok patří .
Druhé tvrzení říká, že existuje vektor takový, že úhel s vektory je maximálně 90 °, zatímco úhel s vektorem je více než 90 °. Nadrovina kolmá k tomuto vektoru má vektory na jedné straně a vektor na druhé straně. Tato nadrovina proto odděluje kužel překlenutý z vektoru .
Například nechte n, m = 2, A1 = (1, 0)T, a A2 = (1, 1)T. Konvexní kužel překlenul A1 a A2 lze vidět jako klínovitý plátek prvního kvadrantu v xy letadlo. Nyní předpokládejme b = (0, 1). Rozhodně, b není v konvexním kuželu A1X1 + A2X2. Proto musí existovat oddělující nadrovina. Nechat y = (1, −1)T. To vidíme A1 · y = 1, A2 · y = 0 a b · y = -1. Proto je nadrovina s normálem y skutečně odděluje konvexní kužel A1X1 + A2X2 z b.
Logická interpretace
Obzvláště sugestivní a snadno zapamatovatelná verze je následující: pokud soubor nerovností nemá řešení, lze z toho vytvořit rozpor lineární kombinací s nezápornými koeficienty. Ve vzorcích: pokud ≤ je tedy neřešitelný , , ≥ má řešení.[6] Všimněte si, že je kombinací levé strany, kombinace pravé strany nerovností. Vzhledem k tomu, že pozitivní kombinace vytváří nulový vektor vlevo a -1 vpravo, je rozpor patrný.
Farkasovo lema lze tedy chápat jako větu o logická úplnost: ≤ je množina „axiomů“, lineární kombinace jsou „odvozovacími pravidly“ a lemma říká, že pokud je množina axiomů nekonzistentní, lze ji vyvrátit pomocí odvozovacích pravidel.[7]:92–94
Varianty
Farkasova lemma má několik variant s různými omezeními znaménka (první je původní verze):[7]:92
- Buď systém má řešení s nebo systém má řešení s .
- Buď systém má řešení s nebo systém má řešení s a .
- Buď systém má řešení s nebo systém má řešení s a .
- Buď systém má řešení s nebo systém má řešení s .
Druhá varianta je uvedena pro úplnost; ve skutečnosti to není „Farkasovo lemma“, protože obsahuje pouze rovnosti. Jeho důkaz je a jednoduché cvičení v lineární algebře.
Zobecnění
Zobecněné Farkasovo lemma — Nechat , , je uzavřený konvexní kužel v a dvojitý kužel z je . Pokud je konvexní kužel je zavřeno, pak platí přesně jeden z následujících dvou příkazů:
- Existuje takhle a .
- Existuje a takhle a .
Zobecněné Farkasovo lema lze interpretovat geometricky následovně: buď je vektor v daném uzavřeném konvexní kužel, nebo existuje a nadrovina oddělení vektoru od kužele; neexistují žádné další možnosti. Podmínka uzavření je nutná, viz Věta o oddělení I v Věta o oddělení hyperplánů. Pro původní Farkasovo lema je nezáporný orthant , proto se podmínka uzavření udržuje automaticky. Ve skutečnosti existuje mnohostěnný konvexní kužel, tj takhle , podmínka uzavření se udržuje automaticky. v konvexní optimalizace, různé druhy omezení omezení, např. Slaterův stav, jsou odpovědné za uzavřenost podkladového konvexního kužele .
Nastavením a v zobecněném Farkasově lematu získáme následující důsledek týkající se řešitelnosti pro konečný systém lineárních rovností:
Důsledek — Nechat a . Pak platí přesně jedno z následujících dvou tvrzení:
- Existuje takhle .
- Existuje a takhle a .
Další důsledky
Farkasovo lema lze obměňovat na mnoho dalších alternativních vět jednoduchými modifikacemi, jako např Gordanova věta: Buď má řešení Xnebo má nenulové řešení y s y ≥ 0.
Mezi běžné aplikace Farkasova lematu patří prokazování věta o silné dualitě spojená s lineárním programováním, teorie her na základní úrovni,[je zapotřebí objasnění ] a Kuhn – Tucker omezení. Rozšíření Farkasova lematu lze použít k analýze silných dualitních podmínek pro a sestrojení dvojího typu semidefinitního programu. Postačuje prokázat existenci Kuhn – Tuckerových omezení pomocí Fredholmova alternativa ale aby byla podmínka nezbytná, je třeba použít Von Neumannovu věta o minimaxu ukázat rovnice odvozené Cauchy nejsou porušeny.
Viz také
- Věta o oddělení hyperplánů
- Duální lineární program
- Vyřazení Fourier-Motzkin - lze použít k prokázání Farkasova lematu.
Poznámky
- ^ Farkas, Julius (Gyula) (1902), „Theorie der Einfachen Ungleichungen“, Journal für die Reine und Angewandte Mathematik, 1902 (124): 1–27, doi:10.1515 / crll.1902.124.1, S2CID 115770124
- ^ Takayama, Akira (1985). Matematická ekonomie (2. vyd.). New York: Cambridge University Press. str.48. ISBN 0-521-31498-4.
- ^ Garg, Anupam; Mermin, N. D. (1984), „Farkasovo lemma a podstata reality: statistické důsledky kvantových korelací“, Základy fyziky, 14: 1–39, doi:10.1007 / BF00741645
- ^ Dinh, N.; Jeyakumar, V. (2014), „Farkasovo lema tři desetiletí generalizace pro matematickou optimalizaci“, HORNÍ, 22 (1): 1–22, doi:10.1007 / s11750-014-0319-r, S2CID 119858980
- ^ Gale, David; Kuhn, Harold; Tucker, Albert W. (1951), „Lineární programování a teorie her - kapitola XII“ (PDF), v Koopmans (ed.), Analýza činnosti výroby a přiděleníWiley. Viz lemma 1 na straně 318.
- ^ Boyd, Stephen P .; Vandenberghe, Lieven (2004), „Oddíl 5.8.3“ (pdf), Konvexní optimalizace, Cambridge University Press, ISBN 978-0-521-83378-3, vyvoláno 15. října 2011.
- ^ A b Gärtner, Bernd; Matoušek, Jiří (2006). Porozumění a používání lineárního programování. Berlín: Springer. ISBN 3-540-30697-8. Stránky 81–104.
Další čtení
- Goldman, A. J .; Tucker, A. W. (1956). "Polyhedral Convex Cones". In Kuhn, H. W .; Tucker, A. W. (eds.). Lineární nerovnosti a související systémy. Princeton: Princeton University Press. 19–40. ISBN 0691079994.
- Rockafellar, R. T. (1979). Konvexní analýza. Princeton University Press. str. 200.