Dualita (optimalizace) - Duality (optimization)

v matematická optimalizace teorie, dualita nebo princip duality je princip, že optimalizační problémy lze nahlížet z jednoho ze dvou pohledů, na prvotní problém nebo dvojí problém. Řešení dvojího problému poskytuje dolní mez řešení prvotního (minimalizačního) problému.^[1] 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á rozdíl v dualitě. Pro konvexní optimalizace problémy, rozdíl v dualitě je nulový pod a omezení kvalifikace stav.

Duální problém

Termín „dvojí problém“ se obvykle vztahuje k Lagrangeův dvojí problém ale používají se další duální problémy - například Wolfe dvojí problém a Fenchelův dvojí problém. Lagrangeův dvojí problém se získá vytvořením Lagrangian minimalizačního problému pomocí nezáporného Lagrangeovy multiplikátory přidat omezení do objektivní funkce a poté řešit hodnoty primární proměnné, 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 maximalizovat objektivní funkci s ohledem na duální proměnné za odvozených omezení duálních proměnných (včetně alespoň nezápornosti omezení).

Obecně dány dva dvojice párů z oddělené lokálně konvexní mezery ${ displaystyle left (X, X ^ {*} right)}$ a ${ displaystyle left (Y, Y ^ {*} right)}$ a funkce ${ displaystyle f: X až mathbb {R} pohár {+ infty }}$, můžeme definovat prvotní problém jako nález ${ displaystyle { hat {x}}}$ takhle ${ displaystyle f ({ hat {x}}) = inf _ {x v X} f (x). ,}$Jinými slovy, pokud ${ displaystyle { hat {x}}}$ existuje, ${ displaystyle f ({ hat {x}})}$ je minimální funkce ${ displaystyle f}$ a infimum (největší dolní mez) funkce je dosaženo.

Pokud existují podmínky omezení, lze je integrovat do funkce ${ displaystyle f}$ necháním ${ displaystyle { tilde {f}} = f + I _ { mathrm {omezení}}}$ kde ${ displaystyle I _ { mathrm {omezení}}}$ je vhodná funkce na ${ displaystyle X}$ který má minimální 0 na omezení, a pro které je možné to dokázat ${ displaystyle inf _ {x v X} { tilda {f}} (x) = inf _ {x mathrm {omezený}} f (x)}$. Druhá podmínka je triviálně, ale ne vždy pohodlně, splněna pro charakteristická funkce (tj. ${ displaystyle I _ { mathrm {omezení}} (x) = 0}$ pro ${ displaystyle x}$ splnění omezení a ${ displaystyle I _ { mathrm {omezení}} (x) = infty}$ v opačném případě). Pak prodloužit ${ displaystyle { tilde {f}}}$ do a poruchová funkce ${ displaystyle F: X krát Y to mathbb {R} pohár {+ infty }}$ takhle ${ displaystyle F (x, 0) = { tilda {f}} (x)}$.^[2]

The rozdíl v dualitě je rozdíl pravé a levé strany nerovnosti

${ displaystyle sup _ {y ^ {*} v Y ^ {*}} - F ^ {*} (0, y ^ {*}) leq inf _ {x v X} F (x, 0), ,}$

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

Rozdíl v dualitě

Rozdíl v dualitě je rozdíl mezi hodnotami jakýchkoli prvotních řešení a jakýchkoli duálních řešení. Li ${ displaystyle d ^ {*}}$ je optimální dvojí hodnota a ${ displaystyle p ^ {*}}$ je optimální primární hodnota, potom se rozdíl v dualitě rovná ${ displaystyle p ^ {*} - d ^ {*}}$. Tato hodnota je vždy větší nebo rovna 0. Mezera v dualitě je nulová právě tehdy silná dualita drží. Jinak je rozdíl přísně pozitivní a slabá dualita drží.^[5]

Ve výpočetní optimalizaci se často uvádí další „rozdíl v dualitě“, kterým je rozdíl v hodnotě mezi jakýmkoli duálním řešením a hodnotou proveditelné, ale neoptimální iterace primárního problému. Tato alternativní „mezera v dualitě“ kvantifikuje rozpor mezi hodnotou aktuálního proveditelného, ​​ale neoptimálního iterátu pro primární problém a hodnotou dvojího problému; hodnota dvojího problému se za podmínek pravidelnosti rovná hodnotě konvexní relaxace prvotního problému: Konvexní relaxace je problém vznikající nahrazením nekonvexní proveditelné množiny jejím uzavřeným konvexní obal a nahrazením nekonvexní funkce konvexní uzavření, to je funkce, která má epigraf to je uzavřený konvexní trup původní funkce původního cíle.^{[6][7][8][9][10][11][12][13][14][15][16]}

Lineární případ

Lineární programování problémy jsou optimalizace problémy, ve kterých Objektivní funkce a omezení všichni jsou lineární. V prvotním problému je objektivní funkce lineární kombinací n proměnné. Existují m omezení, z nichž každé umístí horní mez na lineární kombinaci n proměnné. Cílem je maximalizovat hodnotu objektivní funkce s výhradou omezení. A řešení je vektor (seznam n hodnoty, které dosahují maximální hodnoty pro objektivní funkci.

V dvojím problému je objektivní funkce lineární kombinací m hodnoty, které jsou limity v m omezení z prvotního problému. Existují n duální omezení, z nichž každé umístí dolní mez na lineární kombinaci m duální proměnné.

Vztah mezi prvotním problémem a dvojím problémem

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

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

Tato intuice je formována rovnicemi v Lineární programování: Dualita.

Nelineární případ

v nelineární programování, omezení nemusí být nutně lineární. Platí nicméně mnoho stejných zásad.

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

To je význam Karush – Kuhn – Tuckerovy podmínky. Poskytují nezbytné podmínky pro identifikaci lokálních optim optimálních problémů nelineárního programování. K tomu, aby bylo možné definovat směr k, jsou nutné další podmínky (omezení kvalifikace) optimální řešení. Optimální řešení je takové, které je lokálním optimem, ale možná ne globálním optimem.

Silný Lagrangeův princip: Lagrangeova dualita

Vzhledem k tomu, nelineární programování problém ve standardní formě

${ displaystyle { begin {zarovnáno} { text {minimalizovat}} & f_ {0} (x) { text {předmět}} & f_ {i} (x) leq 0, i in vlevo {1, ldots, m right } & h_ {i} (x) = 0, i in left {1, ldots, p right } end {zarovnáno}}}$

s doménou ${ displaystyle { mathcal {D}} podmnožina mathbb {R} ^ {n}}$ s neprázdným interiérem, Lagrangeova funkce ${ displaystyle Lambda: mathbb {R} ^ {n} times mathbb {R} ^ {m} times mathbb {R} ^ {p} to mathbb {R}}$ je definován jako

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

Vektory ${ displaystyle lambda}$ a ${ displaystyle nu}$ se nazývají duální proměnné nebo Lagrangeovy multiplikační vektory spojené s problémem. The Lagrangeova duální funkce ${ displaystyle g: mathbb {R} ^ {m} times mathbb {R} ^ {p} to mathbb {R}}$ je definován jako

${ displaystyle g ( lambda, nu) = inf _ {x v { mathcal {D}}} lambda (x, lambda, nu) = inf _ {x v { 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 se jedná o bodové infimum afinních funkcí. Duální funkce poskytuje nižší meze optimální hodnoty ${ displaystyle p ^ {*}}$ počátečního problému; pro všechny ${ displaystyle lambda geq 0}$ a jakékoli ${ displaystyle nu}$ my máme ${ displaystyle g ( lambda, nu) leq p ^ {*}}$.

Pokud omezení kvalifikace jako Slaterův stav drží a původní problém je konvexní, pak máme silná dualita, tj. ${ displaystyle d ^ {*} = max _ { lambda geq 0, nu} g ( lambda, nu) = inf f_ {0} = p ^ {*}}$.

Konvexní problémy

U konvexního problému minimalizace s omezeními nerovnosti

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

Lagrangeovým dvojím problémem 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 {zarovnáno}} }$

kde objektivní funkcí je Lagrangeova duální funkce. Za předpokladu, že funkce ${ displaystyle f}$ a ${ displaystyle g_ {1}, ldots, g_ {m}}$ jsou průběžně diferencovatelné, infimum nastane tam, kde je gradient roven nule. Problé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 {zarovnáno}}}$

se nazývá dvojí 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í ${ displaystyle (u, x)}$. Také omezení rovnosti ${ displaystyle nabla f (x) + součet _ {j = 1} ^ {m} u_ {j} nabla g_ {j} (x)}$ je nelineární obecně, takže dvojitý problém Wolfe je obvykle nekonvexní optimalizační problém. V každém případě, slabá dualita drží.^[17]

Dějiny

Podle George Dantzig, věta o dualitě pro lineární optimalizaci byla domněnkou John von Neumann bezprostředně poté, co Dantzig představil problém lineárního programování. Von Neumann poznamenal, že používá informace z jeho herní teorie a předpokládali, že hra s maticemi s nulovým součtem pro dvě osoby odpovídá lineárnímu programování. Důkladné důkazy byly poprvé zveřejněny v roce 1948 autorem Albert W. Tucker a jeho skupina. (Dantzigova předmluva Neringovi a Tuckerovi, 1993)

Viz také

• Konvexní dualita
• Dualita
• Relaxace (přibližná)

Poznámky

Reference

Knihy

• Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Síťové toky: teorie, algoritmy a aplikace. Prentice Hall. 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 z roku 1997, francouzské vydání). Berlín: Springer-Verlag. str. xiv + 490. doi:10.1007/978-3-540-35447-5. ISBN  3-540-35445-X. PAN  2265882.CS1 maint: ref = harv (odkaz)
• 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, NJ: Princeton University Press.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Konvexní algoritmy analýzy a minimalizace, svazek I: Základy. Grundlehren der Mathematischen Wissenschaften [Základní principy matematických věd]. 305. Berlín: Springer-Verlag. str. xviii + 417. ISBN  3-540-56850-6. PAN  1261420.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). „14 Dualita pro odborníky“. Konvexní algoritmy analýzy a minimalizace, svazek II: Pokročilá teorie a svazkové metody. Grundlehren der Mathematischen Wissenschaften [Základní principy matematických věd]. 306. Berlín: Springer-Verlag. str. xviii + 346. ISBN  3-540-56852-2. PAN  1295240.
• Lasdon, Leon S. (2002) [Dotisk Macmillana z roku 1970]. Teorie optimalizace pro velké systémy. Mineola, New York: Dover Publications, Inc., str. Xiii + 523. ISBN  978-0-486-41999-2. PAN  1888251.CS1 maint: ref = harv (odkaz)
• Lawler, Eugene (2001). „4.5. Kombinatorické implikace věty o maximálním průtoku Max-Flow, 4.6. Interpretace věty o minimálním řezu o maximálním průtoku“. Kombinatorická optimalizace: Sítě a matroidy. Doveru. 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é ve Schloß Dagstuhl, 15. – 19. Května 2000. Přednášky v informatice (LNCS). 2241. Berlín: Springer-Verlag. str. 112–156. doi:10.1007/3-540-45586-8_4. ISBN  3-540-42877-1. PAN  1900016.CS1 maint: ref = harv (odkaz)
• Minoux, Michel (1986). Matematické programování: Teorie a algoritmy. Egon Balas (vpřed); Steven Vajda (trans) z francouzštiny (1983 Paříž: Dunod). Chichester: Publikace Wiley-Interscience. John Wiley & Sons, Ltd. str. Xxviii + 489. ISBN  0-471-90170-9. PAN  0868279. (2008, druhé vydání, ve francouzštině: Programmation mathématique: Théorie et algorithmes, Éditions Tec & Doc, Paříž, 2008. xxx + 711 s.)).CS1 maint: ref = harv (odkaz)
• 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). Kombinatorická optimalizace: Algoritmy a složitost (Nezkrácené vydání.). Doveru. ISBN  0-486-40258-4.
• Ruszczyński, Andrzej (2006). Nelineární optimalizace. Princeton, NJ: Princeton University Press. str. xii + 454. ISBN  978-0691119151. PAN  2199043.

Články

• Everett, Hugh, III (1963). "Zobecněná Lagrangeova multiplikátorová metoda pro řešení problémů s optimálním přidělováním zdrojů". Operační výzkum. 11 (3): 399–417. doi:10.1287 / opre.11.3.399. JSTOR  168028. PAN  0152360. Archivovány od originál dne 2011-07-24.CS1 maint: ref = harv (odkaz)
• Kiwiel, Krzysztof C .; Larsson, Torbjörn; Lindberg, P. O. (srpen 2007). „Lagrangeova relaxace pomocí kuličkových podstupových metod“. Matematika operačního výzkumu. 32 (3): 669–686. doi:10,1287 / měsíc 1070,0261. PAN  2348241.CS1 maint: ref = harv (odkaz)
• Dualita v lineárním programování Gary D. Knott