Dualita (optimalizace)

Dualita neboli princip duality je princip, podle kterého lze optimalizační problémy posuzovat ze dvou hledisek, jako přímý problém nebo duální problém . Řešení duální úlohy udává dolní mez přímé úlohy (při minimalizaci) [1] . V obecném případě se však hodnoty objektivních funkcí optimálních řešení přímých a duálních problémů nemusí nutně shodovat. Rozdíl v těchto hodnotách, pokud je pozorován, se nazývá mezera duality . Pro problémy konvexního programování je mezera duality rovna nule, když jsou splněny podmínky pro pravidelnost omezení .

Duální problém

Obvykle termín "dvojí problém" implikuje Lagrangův duální problém , ale používají se i jiné duální problémy, jako Wolfeův duální problém a Fenchelův duální problém . Duální Lagrangeův problém se získá generováním Lagrangeova , použitím nezáporných Lagrangeových multiplikátorů k přidání omezení k účelové funkci a minimalizací Lagrangeova problému s ohledem na některé proměnné přímého problému. Takové řešení dává proměnné přímého problému jako funkce Lagrangeových multiplikátorů, které se nazývají duální proměnné, takže nový problém se stává problémem maximalizace účelové funkce vzhledem k duálním proměnným pod vygenerovanými omezeními na duální proměnné ( alespoň non-negativita).

Obecně, vzhledem k duálnímu páru [2] oddělitelného lokálního konvexního prostoru a funkce , můžeme definovat přímý problém jako nález , takže jinými slovy je infimum (přesná dolní mez) funkce . $\left(X,X^{*}\right)$ ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \))$ ${\klobouk {x}}$ $f({\hat {x)))=\inf _{x\in X}f(x).\,$ $f({\hat {x)))$ $F$

Pokud existují omezení, lze je zabudovat do funkce , pokud dáme , kde je funkce indikátoru . Nechť nyní (pro další duální pár ) je poruchová funkce taková, že [3] . $F$ ${\tilde {f}}=f+I_{\mathrm {omezení} }$ $já$ ${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \))$ $\left(Y,Y^{*}\right)$ $F(x,0)={\tilda {f))(x)$

Dualitní mezera je rozdíl mezi pravou a levou stranou nerovnosti

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

kde je konjugovaná funkce obou proměnných a znamená supremum (přesná horní mez) [3] [4] [5] . $F^{*}$ $\nahoru$

Duality Gap

Dualitní mezera je rozdíl mezi hodnotami všech řešení primárního problému a hodnotami jakýchkoli řešení duálního problému. Pokud je optimální hodnota duálního problému a je optimální hodnota přímého problému, je mezera duality . Tato hodnota je vždy větší nebo rovna 0. Dualitní mezera je nulová právě tehdy, když existuje silná dualita . Jinak je diskontinuita striktně kladná a dochází ke slabé dualitě [6] . $d^{*}$ $p^{*}$ $p^{*}-d^{*}$

V numerických optimalizačních úlohách se často používá další „mezera duality“, která se rovná rozdílu mezi jakýmkoli duálním řešením a hodnotou přípustné, ale ne lokálně optimální iterace pro přímý problém. Alternativní „dualitní mezera“ vyjadřuje nesoulad mezi hodnotou současného proveditelného, ale ne lokálně optimálního řešení primárního problému a hodnotou duálního problému. Hodnota duálního problému se za podmínky pravidelnosti omezení rovná hodnotě konvexního oslabení přímého problému, kde konvexní oslabení vzniká v důsledku nahrazení nekonvexní množiny proveditelných řešení jeho uzavřeným konvexní obal a nahrazení nekonvexní funkce jejím konvexním uzávěrem , tedy funkcí, jejíž epigraf je uzavřený konvexní uzavřením původní účelové funkce přímé úlohy [7] [8] [9] [10] [11 ] [12] [13] [14] [15] [16] [17] .

Lineární případ

Problémy lineárního programování jsou optimalizační problémy , ve kterých jsou účelová funkce a omezení lineární. V přímé úloze je účelová funkce lineární kombinací n proměnných. Existuje m omezení, z nichž každé omezuje lineární kombinaci n proměnných shora. Cílem je maximalizovat hodnotu účelové funkce při omezeních. Řešením je vektor (seznam) n hodnot, který dává maximální hodnotu účelové funkce.

V duálním problému je cílová funkce lineární kombinací m hodnot, které jsou pravými stranami m omezení primárního problému. Existuje n duálních omezení, z nichž každé omezuje lineární kombinaci m duálních proměnných zdola.

Vztah mezi primárními a duálními problémy

V lineárním případě, v přímé úloze, z každého bodu lokálního optima, který splňuje všechna omezení, existuje směr nebo podprostor směrů a pohyb v tomto směru zvyšuje účelovou funkci. Pohyb v jakémkoli takovém směru údajně snižuje propast mezi proveditelným řešením (nebo proveditelným plánem ) a jedním z omezení. Neplatné možné řešení je řešení, které porušuje jedno nebo více omezení.

V duálním problému jsou prvky duálního vektoru vynásobeny sloupci, které odpovídají omezením v primárním problému. Perturbace duálního vektoru v duálním problému je ekvivalentní revizi horní hranice primárního problému. Při řešení duálního problému se hledá nejmenší horní mez, tedy duální vektor se mění tak, aby se zmenšila mezera mezi proveditelným řešením a skutečným optimem.

Další informace o spojení mezi primárním a duálním problémem naleznete v článku " Duální problémy lineárního programování ".

Ekonomický výklad

Chápeme-li náš primární problém lineárního programování jako klasický problém „přidělování zdrojů“, jeho duální problém lze interpretovat jako problém „ odhadu zdrojů “ .

Nelineární případ

V nelineárním programování nemusí být omezení nutně lineární. Platí však mnoho principů lineárního případu.

Aby bylo zajištěno, že globální maximum nelineárního problému lze snadno definovat, příkaz problému často vyžaduje, aby funkce byly konvexní a měly kompaktní sady nižších úrovní (tj. množiny, na kterých má funkce hodnotu menší než nějaká úroveň) .

Toto je podmínka Karush-Kuhn-Tucker . Prokázali nezbytné podmínky pro určení lokálního optima nelineárních problémů. Existují další podmínky (podmínka pravidelnosti omezení), které jsou nezbytné pro určení směru k optimálnímu řešení. Zde je optimálním řešením jedno z lokálních optim, které nemusí být globální.

Přísný Lagrangeův princip: Lagrangeova dualita

Pokud je problém nelineárního programování uveden ve standardním formuláři

minimalizovat	$f_{0}(x)$
za podmínek	${\displaystyle f_{i}(x)\leqslant 0,\ i\in \left\{1,\tečky ,m\right\))$
	${\displaystyle h_{i}(x)=0,\ i\in \left\{1,\tečky ,p\right\))$

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

\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 se nazývají duální proměnné nebo vektory Lagrangeových multiplikátorů spojených s problémem. Duální Lagrangeova funkce je definována jako $\lambda$ $\nu$ $g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$

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

Duální funkce g je konkávní, i když počáteční problém není konvexní, protože je bodovým infimem afinních funkcí. Duální funkce udává dolní meze pro optimální hodnotu původního problému. Pro kohokoli a kohokoli , koho máme . $p^{*}$ $\lambda \geqslant 0$ $\nu$ $g(\lambda ,\nu )\leqslant p^{*}$

Pokud jsou splněny podmínky pravidelnosti omezení , jako je Slaterova podmínka , a původní problém je konvexní, pak máme přísnou dualitu , tedy . $d^{*}=\max _{\lambda \geqslant 0,\nu }g(\lambda ,\nu )=\inf f_{0}=p^{*}$

Konvexní problémy

Pro problém konvexní minimalizace s omezeními – nerovnostmi,

minimalizovat	$f(x)$
za podmínek	$g_{i}(x)\leqslant 0,\quad i=1,\tečky ,m$

Lagrangeův duální problém je

maximalizovat	$\inf _{x}\left(f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\right)$
za podmínek	$u_{i}\geqslant 0,\quad i=1,\dots ,m$

kde cílová funkce je duální Lagrangeova funkce. Pokud je známo, že funkce a jsou spojitě diferencovatelné, pak je infimum v bodech, kde je gradient nula. Úkol $F$ ${\displaystyle g_{1},\cdots ,g_{m))$

maximalizovat	$f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)$
za podmínek	$\nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)=0$
$u_{i}\geqslant 0,\quad i=1,\dots ,m$

se nazývá duální Wolfův problém. Tento úkol může být výpočetně obtížný, protože účelová funkce není v souřadnicích konvexní . Omezení je také obecně nelineární, takže duální Wolfův problém je obvykle nekonvexní optimalizační problém. V každém případě je zde slabá dualita [18] . $(u,x)$ $\nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)$

Historie

Podle George Danziga byl teorém o dualitě pro lineární optimalizaci předložen jako domněnka Johna von Neumanna bezprostředně poté, co Danzig představil problém lineárního programování. Von Neumann si všiml, že použil informace ze své teorie her a navrhl, že maticová hra pro dvě osoby s nulovým součtem je ekvivalentní problému lineárního programování. Důkladný důkaz této skutečnosti byl poprvé publikován v roce 1948 Albertem Tuckerem a jeho skupinou [19] .

Viz také

Princip duality
Útlum (přiblížení)

Poznámky

↑ Boyd, Vandenberghe, 2004 .
↑ Dvojice je trojice , kde je vektorový prostor nad polem , je množina všech lineárních zobrazení a třetím prvkem je bilineární forma . $\left(X,X^{*},\langle ,\rangle \right)$ $X$ $F$ $X^{*}$ $\phi \colon X\to F$ $X^{*}\times X\to F\colon (\phi ,x)\mapsto \phi (x)$
↑ 1 2 Boţ, Wanka, Grad, 2009 .
↑ Csetnek, 2010 .
↑ Zălinescu, 2002 , s. 106–113.
↑ Borwein, Zhu, 2005 .
↑ Ahuja, Magnanti, Orlin, 1993 .
↑ Bertsekas, Nedic, Ozdaglar, 2003 .
↑ Bertsekas, 1999 .
↑ Bertsekas, 2009 .
↑ Bonnans, Gilbert, Lemaréchal, Sagastizábal, 2006 , str. xiv+490.
↑ Hiriart-Urruty, Lemaréchal, 1993 , s. xviii+417.
↑ Hiriart-Urruty, Lemaréchal, 1993 , s. xviii+346.
↑ Lasdon, 2002 , str. xiii+523.
↑ Lemarechal, 2001 , str. 112–156.
↑ Minoux, 1986 , str. xxviii+489.
↑ Shapiro, 1979 , str. xvi+388.
↑ Geoffrion, 1971 , str. 1–37.
↑ Nering a Tucker 1993 , str. předmluva Danzig.

Literatura

Knihy

Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Konvexní analýza a minimalizační algoritmy. Část I: Základy. - Berlín: Springer-Verlag, 1993. - T. 305. - S. xviii + 417. — (Grundlehren der Mathematischen Wissenschaften [Základní principy matematických věd]). — ISBN 3-540-56850-6 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. 14 Dualita pro praktiky // Konvexní analýza a minimalizační algoritmy. Část II: Pokročilá teorie a svazkové metody. - Berlín: Springer-Verlag, 1993. - T. 306. - S. xviii + 346. — (Grundlehren der Mathematischen Wissenschaften [Základní principy matematických věd]). — ISBN 3-540-56852-2 .
Leon S Lasdon. Teorie optimalizace pro velké systémy . - Mineola, New York: Dover Publications, Inc., 2002. - str. xiii+523. — ISBN 978-0-486-41999-2 .
Claude Lemarechal. Lagrangiánská relaxace // Výpočetní kombinatorická optimalizace: Referáty z jarní školy konané v Schloß Dagstuhl, 15.–19. května 2000. - Berlín: Springer-Verlag, 2001. - Vol. 2241. - S. 112-156. - (Poznámky k přednáškám z informatiky (LNCS)). — ISBN 3-540-42877-1 . - doi : 10.1007/3-540-45586-8_4 .
Michel Minoux. Matematické programování: Teorie a algoritmy. - Chichester: Publikace Wiley-Interscience. John Wiley & Sons, Ltd., 1986. - str. xxviii+489. — ISBN 0-471-90170-9 .
- M. Minu. Matematické programování. Teorie a algoritmy.
Evar D. Nering, Albert W. Tucker. Lineární programování a související problémy . - Boston, MA: Academic Press, 1993. - ISBN 978-0-12-515440-6 .
Stephen P. Boyd, Lieven Vandenberghe. Konvexní optimalizace . - Cambridge University Press, 2004. - ISBN 978-0-521-83378-3 .
Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Dualita ve vektorové optimalizaci. - Springer, 2009. - ISBN 978-3-642-02885-4 .
Ernö Robert Csetnek. Překonání selhání klasických zobecněných podmínek pravidelnosti vnitřního bodu v konvexní optimalizaci. Aplikace teorie duality na zvětšení maximálních monotónních operátorů. - Logos Verlag Berlin GmbH, 2010. - ISBN 978-3-8325-2503-3 .
Constantin Zalinescu. Konvexní analýza v obecných vektorových prostorech. — River Edge, NJ: World Scientific Publishing Co., Inc., 2002. — s. 106–113. - ISBN 981-238-067-1 .
Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Síťové toky: Teorie, algoritmy a aplikace. - Prentice Hall, 1993. - ISBN 0-13-617549-X .
Dimitri Bertsekas, Angelia Nedic, Asuman Ozdaglar. Konvexní analýza a optimalizace. - Athena Scientific, 2003. - ISBN 1-886529-45-0 .
Dimitri P. Bertsekas. nelineární programování. — 2. - Athena Scientific, 1999. - ISBN 1-886529-00-0 .
Dimitri P. Bertsekas. Teorie konvexní optimalizace. - Athena Scientific, 2009. - ISBN 978-1-886529-31-1 .
J. Fredéric Bonnans, J. Charles Gilbert, Claude Lemaréchal, Claudia A. Sagastizábal. Numerická optimalizace: Teoretické a praktické aspekty . — Druhé revidované vyd. překladu z roku 1997. - Berlin: Springer-Verlag, 2006. - str. xiv+490. — (Univerzitní text). — ISBN 3-540-35445-X . - doi : 10.1007/978-3-540-35447-5 .
Jeremy F. Shapiro. Matematické programování: Struktury a algoritmy . - New York: Wiley-Interscience [John Wiley & Sons], 1979. - str. xvi + 388. — ISBN 0-471-77886-9 .
Jonathan Borwein, Qiji Zhu. Techniky variační analýzy. - Springer, 2005. - ISBN 978-1-4419-2026-3 .

Články

Dualita v lineárním programování Gary D. Knott
Arthur M. Geoffrion. Dualita v nelineárním programování: Vývoj orientovaný na zjednodušené aplikace // Recenze SIAM. - 1971. - T. 13 , no. 1 . - doi : 10.1137/1013001 . — .

Další čtení

William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver. kombinatorická optimalizace. — 1. - John Wiley & Sons, 1997. - ISBN 0-471-55894-X .
Xugang Ye, Shih-Ping Han, Anhua Lin. Poznámka ke spojení mezi algoritmy Primal-Dual a A* // International Journal of Operations Research and Information Systems. - 2010. - Vol. 1 , vydání. 1 . — s. 73–85 .
George B. Dantzig. Lineární programování a rozšíření. — Princeton, NJ: Princeton University Press, 1963.
Eugene Lawler. 4.5. Kombinatorické implikace věty o maximálním průtoku a minimálním řezu, 4.6. Lineární programování Interpretace věty o minimálním řezu o maximálním průtoku // Kombinatorická optimalizace: Sítě a matice. - Dover, 2001. - S. 117-120. - ISBN 0-486-41453-1 .
Andrzej Piotr Ruszczyński. nelineární optimalizace. — Princeton, NJ: Princeton University Press , 2006. — s. xii+454. - ISBN 978-0691119151 .
Christos H. Papadimitriou, Kenneth Steiglitz. Kombinatorická optimalizace: Algoritmy a složitost. - Dover, 1998. - ISBN 0-486-40258-4 .
Krzysztof C. Kiwiel, Torbjörn Larsson, P. O. Lindberg. Lagrangiánská relaxace pomocí ballstep subgradientových metod // Matematika operačního výzkumu. - 2007. - Srpen ( díl 32 , číslo 3 ). — S. 669–686 . - doi : 10.1287/moor.1070.0261 .