Dualita (optimalizace) - Duality (optimization)

V teorii matematické optimalizace je dualita nebo princip duality principem, že na problémy optimalizace lze nahlížet buď ze dvou perspektiv, prvotního problému nebo dvojího problému . Řešení duálního problému poskytuje dolní mez řešení primárního (minimalizačního) problému. Obecně však nemusí být optimální hodnoty primárních a duálních problémů stejné. Jejich rozdíl se nazývá mezera v dualitě . U konvexních optimalizačních problémů je mezera duality za podmínek kvalifikace omezení nulová .

Duální problém

Termín „duální problém“ obvykle označuje Lagrangeův duální problém, ale používají se i jiné duální problémy - například Wolfeův duální problém a Fenchelův duální problém . Lagrangeův duální problém je získán vytvořením Lagrangeova problému minimalizace použitím nezáporných Lagrangeových multiplikátorů pro přidání omezení do objektivní funkce a poté řešením pro hodnoty primárních proměnných, které minimalizují původní objektivní funkci. Toto řešení dává primární proměnné jako funkce Lagrangeových multiplikátorů, které se nazývají duální proměnné, takže novým problémem je maximalizace objektivní funkce s ohledem na duální proměnné za odvozených omezení duálních proměnných (včetně alespoň nezápornosti omezení).

Obecně uvedeny dva duální páry z oddělených lokálně konvexní prostory a a funkci , můžeme definovat prvotní problém jako zjištění tak, aby Jinými slovy, pokud existuje, je minimální funkce a infima (největší dolní odhad) funkce je dosaženo. ${\ Displaystyle \ left (X, X^{*} \ right)}$ ${\ Displaystyle \ left (Y, Y^{*} \ right)}$ ${\ Displaystyle f: X \ to \ mathbb {R} \ cup \ {+\ infty \}}$ ${\ displaystyle {\ hat {x}}}$ ${\ Displaystyle f ({\ hat {x}}) = \ inf _ {x \ in X} f (x). \,}$ ${\ displaystyle {\ hat {x}}}$ ${\ displaystyle f ({\ hat {x}})}$ ${\ displaystyle f}$

Pokud existují omezující podmínky, lze je integrovat do funkce tak, že necháme kde je vhodná funkce, která má na omezení minimálně 0, a pro které to lze dokázat . Druhá podmínka je triviálně, ale ne vždy vhodně, splněna pro charakteristickou funkci (tj. Pro splnění omezení a jinak). Poté rozšiřte na poruchovou funkci tak, že . ${\ displaystyle f}$ ${\ displaystyle {\ tilde {f}} = f+I _ {\ mathrm {constraints}}}$ ${\ displaystyle I _ {\ mathrm {constraints}}}$ ${\ displaystyle X}$ ${\ Displaystyle \ inf _ {x \ in X} {\ tilde {f}} (x) = \ inf _ {x \ \ mathrm {constrained}} f (x)}$ ${\ displaystyle I _ {\ mathrm {constraints}} (x) = 0}$ ${\ displaystyle x}$ ${\ Displaystyle I _ {\ mathrm {constraints}} (x) = \ infty}$ ${\ displaystyle {\ tilde {f}}}$ ${\ Displaystyle F: X \ times Y \ to \ mathbb {R} \ cup \ {+\ infty \}}$ ${\ Displaystyle F (x, 0) = {\ tilde {f}} (x)}$

Mezera dualita je rozdíl z pravé a levé strany ruka nerovnosti

{\ Displaystyle \ sup _ {y^{*} \ in Y^{*}}-F^{*} (0, y^{*}) \ leq \ inf _ {x \ in X} F (x, 0), \,}

kde je konvexní konjugát v obou proměnných a označuje supremum (nejmenší horní hranice). ${\ displaystyle F^{*}}$ ${\ displaystyle \ sup}$

Mezera v dualitě

Mezera v dualitě je rozdílem mezi hodnotami jakýchkoli primárních řešení a jakýchkoli duálních řešení. Pokud je optimální duální hodnota a je optimální primární hodnota, pak je rozdíl v dualitě roven . Tato hodnota je vždy větší nebo rovna 0. Mezera v dualitě je nulová právě tehdy, pokud silná dualita platí. Jinak je mezera přísně pozitivní a slabá dualita platí. ${\ displaystyle d^{*}}$ ${\ displaystyle p^{*}}$ ${\ Displaystyle p^{*}-d^{*}}$

Ve výpočetní optimalizaci je často hlášena další „mezera v dualitě“, což je rozdíl v hodnotě mezi jakýmkoli duálním řešením a hodnotou proveditelné, ale suboptimální iterace primárního problému. Tato alternativní „mezera v dualitě“ kvantifikuje rozpor mezi hodnotou současného proveditelného, ale suboptimálního iterátu primárního problému a hodnotou duálního problému; hodnota duálního problému je za podmínek pravidelnosti rovna hodnotě konvexní relaxace primárního problému: Konvexní relaxace je problém vznikající nahrazením nekonvexní proveditelné sady uzavřeným konvexním trupem a nahrazením non- konvexní funkce s jejím konvexním uzavřením , to je funkce, která má epigraf, který je uzavřeným konvexním trupem původní primární objektivní funkce.

Lineární případ

Lineární programovací problémy jsou optimalizační problémy, v níž objektivní funkce a omezení jsou všechny lineární . V prvotním problému je objektivní funkce lineární kombinací n proměnných. Existuje m omezení, z nichž každé klade horní hranici na lineární kombinaci n proměnných. Cílem je maximalizovat hodnotu objektivní funkce podléhající omezením. Řešení je vektor (seznam) z n hodnot, které dosahuje maximální hodnotu cílové funkce.

V duálním problému je objektivní funkce lineární kombinací hodnot m, které jsou limity v m omezeních z primárního problému. Existuje n dvojího omezení, z nichž každé klade spodní hranici na lineární kombinaci m duálních proměnných.

Vztah mezi prvotním problémem a dvojitým problémem

V lineárním případě v primárním problému z každého suboptimálního bodu, který splňuje všechna omezení, existuje směr nebo podprostor směrů pohybu, který zvyšuje objektivní funkci. Pohyb v jakémkoli takovém směru údajně odstraní vůli mezi kandidátským řešením a jedním nebo více omezeními. Neproveditelné hodnota kandidátní řešení je ta, která překračuje jednu nebo více omezení.

V duálním problému duální vektor znásobuje omezení, která určují polohy vazeb v primalu. Změna duálního vektoru v duálním problému je ekvivalentní revizi horních hranic v primárním problému. Hledá se nejnižší horní hranice. To znamená, že duální vektor je minimalizován, aby se odstranila vůle mezi kandidátskými polohami omezení a skutečným optimem. Neproveditelná hodnota duálního vektoru je příliš nízká. Nastavuje kandidátské pozice jednoho nebo více omezení v pozici, která vylučuje skutečné optimum.

Tuto intuici formalizují rovnice v lineárním programování: Dualita .

Nelineární případ

V nelineárním programování nejsou omezení nutně lineární. Přesto platí mnoho stejných zásad.

Aby bylo zajištěno, že globální maximum nelineárního problému lze snadno identifikovat, formulace problému často vyžaduje, aby funkce byly konvexní a měly kompaktní sady nižších úrovní.

To je význam podmínek Karush – Kuhn – Tucker . Poskytují nezbytné podmínky pro identifikaci lokálních optima problémů nelineárního programování. Aby bylo možné definovat směr k optimálnímu řešení , jsou nutné další podmínky (omezující kvalifikace) . Optimálním řešením je lokální optimum, ale možná ne globální optimum.

Silný Lagrangeův princip: Lagrangeova dualita

Daný problém nelineárního programování ve standardní formě

{\ displaystyle {\ begin {aligned} {\ text {minimal}} & f_ {0} (x) \\ {\ text {subject to}} & f_ {i} (x) \ leq 0, \ i \ in \ left \ {1, \ ldots, m \ right \} \\ & h_ {i} (x) = 0, \ i \ in \ left \ {1, \ ldots, p \ right \} \ end {aligned}}}

s doménou s neprázdným vnitřkem je Lagrangianova funkce definována jako ${\ displaystyle {\ mathcal {D}} \ podmnožina \ mathbb {R} ^{n}}$ ${\ Displaystyle \ Lambda: \ mathbb {R} ^{n} \ times \ mathbb {R} ^{m} \ times \ mathbb {R} ^{p} \ to \ mathbb {R}}$

{\ Displaystyle \ Lambda (x, \ lambda, \ nu) = f_ {0} (x)+\ sum _ {i = 1}^{m} \ lambda _ {i} f_ {i} (x)+\ součet _ {i = 1}^{p} \ nu _ {i} h_ {i} (x).}

Vektory a jsou nazývány duální proměnné nebo Lagrangeova multiplikátoru vektory spojené s tímto problémem. Dvojí Lagrangeova funkce je definována jako ${\ displaystyle \ lambda}$ ${\ displaystyle \ nu}$ ${\ Displaystyle g: \ mathbb {R} ^{m} \ times \ mathbb {R} ^{p} \ to \ mathbb {R}}$

{\ Displaystyle g (\ lambda, \ nu) = \ inf _ {x \ in {\ mathcal {D}}} \ Lambda (x, \ lambda, \ nu) = \ inf _ {x \ in {\ mathcal { D}}} \ left (f_ {0} (x)+\ sum _ {i = 1}^{m} \ lambda _ {i} f_ {i} (x)+\ sum _ {i = 1}^ {p} \ nu _ {i} h_ {i} (x) \ right).}

Duální funkce g je konkávní, i když počáteční problém není konvexní, protože jde o bodový infimum afinních funkcí. Duální funkce poskytuje dolní hranice optimální hodnoty počátečního problému; pro cokoli a cokoli, co máme . ${\ displaystyle p^{*}}$ ${\ displaystyle \ lambda \ geq 0}$ ${\ displaystyle \ nu}$ ${\ Displaystyle g (\ lambda, \ nu) \ leq p^{*}}$

Pokud platí omezující kvalifikace, jako je Slaterův stav, a původní problém je konvexní, pak máme silnou dualitu , tzn . ${\ Displaystyle d^{*} = \ max _ {\ lambda \ geq 0, \ nu} g (\ lambda, \ nu) = \ inf f_ {0} = p^{*}}$

Konvexní problémy

Pokud jde o problém konvexní minimalizace s omezeními nerovnosti,

{\ displaystyle {\ begin {aligned} & {\ underset {x} {\ operatorname {minimal}}} && f (x) \\ & \ operatorname {subject \; to} && g_ {i} (x) \ leq 0, \ quad i = 1, \ ldots, m \ end {zarovnáno}}}

Lagrangeův duální problém je

{\ displaystyle {\ begin {aligned} & {\ underset {u} {\ operatorname {maximize}}} && \ inf _ {x} \ left (f (x)+\ sum _ {j = 1}^{m } u_ {j} g_ {j} (x) \ right) \\ & \ operatorname {subject \; to} && u_ {i} \ geq 0, \ quad i = 1, \ ldots, m \ end {aligned}} }

kde objektivní funkcí je Lagrangeova dvojí funkce. Za předpokladu, že funkce a jsou spojitě diferencovatelné, dojde k infimu tam, kde je gradient roven nule. Problém ${\ displaystyle f}$ ${\ displaystyle g_ {1}, \ ldots, g_ {m}}$

{\ displaystyle {\ begin {aligned} & {\ underset {x, u} {\ operatorname {maximize}}} && f (x)+\ sum _ {j = 1}^{m} u_ {j} g_ {j } (x) \\ & \ operatorname {subject \; to} && \ nabla f (x)+\ sum _ {j = 1}^{m} u_ {j} \, \ nabla g_ {j} (x) = 0 \\ &&& u_ {i} \ geq 0, \ quad i = 1, \ ldots, m \ end {aligned}}}

se nazývá duální problém Wolfe. Tento problém může být obtížné řešit výpočetně, protože objektivní funkce není ve společných proměnných konkávní . Rovněž omezení rovnosti je obecně nelineární, takže duální problém Wolfe je obvykle problém nekonvexní optimalizace. V každém případě platí slabá dualita . ${\ displaystyle (u, x)}$ ${\ Displaystyle \ nabla f (x)+\ sum _ {j = 1}^{m} u_ {j} \, \ nabla g_ {j} (x)}$

Dějiny

Podle George Dantziga teorii duality pro lineární optimalizaci navrhl John von Neumann bezprostředně poté, co Dantzig představil problém lineárního programování. Von Neumann poznamenal, že používá informace ze své teorie her , a domníval se, že maticová hra pro dvě osoby s nulovým součtem je ekvivalentní lineárnímu programování. Rigorózní důkazy poprvé publikoval v roce 1948 Albert W. Tucker a jeho skupina. (Dantzigova předmluva k Neringovi a Tuckerovi, 1993)

Viz také

Poznámky

Reference

Knihy

Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Síťové toky: teorie, algoritmy a aplikace . Prentický sál. ISBN 0-13-617549-X.
Bertsekas, Dimitri; Nedic, Angelia; Ozdaglar, Asuman (2003). Konvexní analýza a optimalizace . Athena Scientific. ISBN 1-886529-45-0.
Bertsekas, Dimitri P. (1999). Nelineární programování (2. vyd.). Athena Scientific. ISBN 1-886529-00-0.
Bertsekas, Dimitri P. (2009). Konvexní teorie optimalizace . Athena Scientific. ISBN 978-1-886529-31-1.
Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Numerická optimalizace: Teoretické a praktické aspekty . Universitext (druhé přepracované vydání překladu francouzského vydání z roku 1997). Berlín: Springer-Verlag. s. xiv+490. doi : 10,1007/978-3-540-35447-5 . ISBN 3-540-35445-X. MR 2265882 .
Cook, William J .; Cunningham, William H .; Pulleyblank, William R .; Schrijver, Alexander (12. listopadu 1997). Kombinatorická optimalizace (1. vyd.). John Wiley & Sons. ISBN 0-471-55894-X.
Dantzig, George B. (1963). Lineární programování a rozšíření . Princeton, New Jersey: Princeton University Press.
Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Konvexní algoritmy pro analýzu a minimalizaci, svazek I: Základy . Grundlehren der Mathematischen Wissenschaften [Základní principy matematických věd]. 305 . Berlín: Springer-Verlag. s. xviii+417. ISBN 3-540-56850-6. MR 1261420 .
Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). „14 Dualita pro praktiky“. Konvexní algoritmy pro analýzu a minimalizaci, Volume II: Advanced theory and bundle methods . Grundlehren der Mathematischen Wissenschaften [Základní principy matematických věd]. 306 . Berlín: Springer-Verlag. s. xviii+346. ISBN 3-540-56852-2. MR 1295240 .
Lasdon, Leon S. (2002) [Dotisk Macmillana z roku 1970]. Optimalizační teorie pro velké systémy . Mineola, New York: Dover Publications, Inc., str. Xiii+523. ISBN 978-0-486-41999-2. MR 1888251 .
Lawler, Eugene (2001). „4.5. Kombinatorické důsledky věty o minimálním řezu Max-Flow, 4.6. Interpretace lineární věty o minimálním řezu lineárním programováním“. Kombinatorická optimalizace: Sítě a matroidy . Dover. s. 117–120. ISBN 0-486-41453-1.
Lemaréchal, Claude (2001). „Lagrangeova relaxace“. V Jünger, Michael; Naddef, Denis (eds.). Výpočetní kombinatorická optimalizace: Příspěvky z jarní školy konané v Schloß Dagstuhl, 15. - 19. května 2000 . Lecture Notes in Computer Science (LNCS). 2241 . Berlín: Springer-Verlag. s. 112–156. doi : 10,1007/3-540-45586-8_4 . ISBN 3-540-42877-1. MR 1900016 .
Minoux, Michel (1986). Matematické programování: Teorie a algoritmy . Egon Balas (vpřed); Steven Vajda (trans) z francouzštiny (1983 Paris: Dunod). Chichester: Publikace Wiley-Interscience. John Wiley & Sons, Ltd. str. Xxviii+489. ISBN 0-471-90170-9. MR 0868279 . (2008 Second ed., In French: Programmation mathématique: Théorie et Algorithmes , Éditions Tec & Doc, Paris, 2008. xxx+711 pp.)).
Nering, Evar D .; Tucker, Albert W. (1993). Lineární programování a související problémy . Boston, MA: Academic Press. ISBN 978-0-12-515440-6.
Papadimitriou, Christos H .; Steiglitz, Kenneth (červenec 1998). Combinatorial Optimization: Algorithms and Complexity (Unabridged ed.). Dover. ISBN 0-486-40258-4.
Ruszczyński, Andrzej (2006). Nelineární optimalizace . Princeton, New Jersey: Princeton University Press . s. xii+454. ISBN 978-0691119151. MR 2199043 .

Články

Everett, Hugh, III (1963). „Zobecněná Lagrangeova multiplikační metoda pro řešení problémů optimálního přidělování zdrojů“ . Operační výzkum . 11 (3): 399–417. doi : 10,1287/opre.11.3.399 . JSTOR 168028 . MR 0152360 . Archivováno od originálu dne 24. července 2011.
Kiwiel, Krzysztof C .; Larsson, Torbjörn; Lindberg, P. O. (srpen 2007). „Lagrangeova relaxace pomocí subgradientních metod Ballstep“ . Matematika operačního výzkumu . 32 (3): 669–686. doi : 10,1287/moor.1070.0261 . MR 2348241 .
Dualita v lineárním programování Gary D. Knott

Languages

In other projects