Kettősség (optimalizálás)

A dualitás vagy a dualitás elve az az elv, amely alapján az optimalizálási problémákat két szempontból tekinthetjük, közvetlen vagy kettős problémaként . A duális probléma megoldása adja a direkt probléma alsó korlátját (minimalizáláskor) [1] . Általános esetben azonban a közvetlen és a kettős problémák optimális megoldásának célfüggvényeinek értékei nem feltétlenül esnek egybe. Ezen értékek különbségét, ha megfigyeljük, dualitásrésnek nevezzük . A konvex programozás problémáinál a dualitási rés egyenlő nullával, ha a megszorítások szabályszerűségének feltételei teljesülnek .

Kettős probléma

Általában a "kettős probléma" kifejezés a Lagrange-féle kettős problémát jelenti , de más kettős problémákat is használnak, mint például a Wolfe-féle kettős probléma és a Fenchel-féle kettős probléma . A kettős Lagrange-problémát úgy kapjuk meg, hogy létrehozunk egy Lagrange -féle szorzót, nem negatív Lagrange-szorzókat használunk a célfüggvény megszorításaihoz, és a Lagrange-problémát a közvetlen probléma néhány változója tekintetében minimalizáljuk. Egy ilyen megoldás a direkt probléma változóit Lagrange-szorzók függvényeiként adja meg, amelyeket duális változóknak nevezünk, így az új probléma a célfüggvény maximalizálásának problémája lesz a kettős változók vonatkozásában a kettős változókra generált megszorítások mellett. legalábbis nem negativitás).

Általánosságban elmondható, hogy egy elválasztható lokális konvex tér és egy függvény duális párja [2] alapján a direkt problémát úgy definiálhatjuk, mint a keresést , úgy, hogy más szóval a függvény infimuma (pontos alsó korlátja) . $\left(X,X^{*}\right)$ ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \))$ ${\kalap {x}}$ $f({\hat {x)))=\inf _{x\in X}f(x).\,$ $f({\hat {x)))$ $f$

Ha vannak megkötések, akkor beépíthetők a függvénybe , ha tesszük , ahol az indikátorfüggvény . Legyen most (egy másik kettős pár esetén) egy olyan perturbációs függvény , hogy [3] . $f$ ${\tilde {f}}=f+I_{\mathrm {constraints} }$ $én$ ${\displaystyle F:X\time Y\to \mathbb {R} \cup \{+\infty \))$ $\left(Y,Y^{*}\right)$ $F(x,0)={\tilde {f))(x)$

A dualitási rés az egyenlőtlenség jobb és bal oldala közötti különbség

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

ahol mindkét változó konjugált függvénye , és a felső határt jelenti (pontos felső korlát) [3] [4] [5] . $F^{*}$ $\fel$

Duality Gap

A kettősség rés az elsődleges probléma bármely megoldásának értéke és a kettős probléma megoldásának értékei közötti különbség. Ha a duális probléma optimális értéke, és a direkt probléma optimális értéke, akkor a dualitási rés . Ez az érték mindig nagyobb, mint 0, vagy egyenlő azzal. A dualitási rés akkor és csak akkor nulla, ha erős dualitás van . Ellenkező esetben a diszkontinuitás szigorúan pozitív, és gyenge kettősség lép fel [6] . $d^{*}$ $p^{*}$ $p^{*}-d^{*}$

A numerikus optimalizálási feladatokban gyakran használnak egy másik "kettős rést", amely egyenlő a kettős megoldás és a direkt probléma elfogadható, de lokálisan nem optimális iterációja közötti különbséggel. Az alternatív "dualitási rés" az elsődleges probléma jelenlegi megvalósítható, de lokálisan nem optimális megoldásának értéke és a duális probléma értéke közötti eltérést fejezi ki. A duális probléma értéke a megszorítások szabályossága feltétele mellett egyenlő a direkt probléma konvex gyengülésének értékével , ahol a konvex gyengülés abból adódik, hogy a megvalósítható megoldások nem konvex halmazát a zártjával helyettesítjük. konvex burok , és a nem konvex függvényt a konvex lezárásával cseréljük le , vagyis egy olyan függvényre, amelynek epigráfja zárt konvex a direkt probléma eredeti célfüggvényének bezárásával [7] [8] [9] [10] [11 ] [12] [13] [14] [15] [16] [17] .

Lineáris eset

A lineáris programozási problémák olyan optimalizálási problémák , amelyekben a célfüggvény és a megszorítások lineárisak. A közvetlen feladatban a célfüggvény n változó lineáris kombinációja . M megszorítás létezik, amelyek mindegyike felülről korlátozza n változó lineáris kombinációját . A cél a célfüggvény értékének maximalizálása megszorítások mellett. A megoldás egy n értékből álló vektor (lista), amely megadja a célfüggvény maximális értékét.

A kettős feladatban a célfüggvény olyan m érték lineáris kombinációja, amely az elsődleges probléma m kényszerének jobb oldala . n kettős megkötés létezik, amelyek mindegyike alulról korlátozza m kettős változó lineáris kombinációját .

Az elsődleges és a duális problémák kapcsolata

Lineáris esetben a direkt feladatban a lokális optimum minden korlátot kielégítő pontjáról van egy irány vagy altere , és az ilyen irányú mozgás növeli a célfüggvényt. Bármely ilyen irányú elmozdulás csökkenti a szakadékot a megvalósítható megoldás (vagy megvalósítható terv ) és az egyik korlát között. Érvénytelen lehetséges megoldás az a megoldás, amely megsért egy vagy több megkötést.

A duális feladatban a duálvektor elemeit megszorozzuk azokkal az oszlopokkal, amelyek megfelelnek a primálfeladatban szereplő kényszereknek. A duális vektor perturbációja a duális feladatban egyenértékű az elsődleges probléma felső határának felülvizsgálatával. A duális feladat megoldása során a legkisebb felső korlátot keresik, vagyis a duális vektor úgy változik, hogy a megvalósítható megoldás és a tényleges optimum közötti különbség csökkenjen.

Az elsődleges és a kettős problémák közötti kapcsolattal kapcsolatos további információkért lásd a " Lineáris programozás kettős problémái " című cikket .

Közgazdasági értelmezés

Ha az elsődleges lineáris programozási problémánkat klasszikus „erőforrás-allokációs” problémaként értelmezzük, akkor annak kettős problémája „ Resource estimation ” problémaként értelmezhető .

Nemlineáris eset

A nemlineáris programozásban a megszorítások nem feltétlenül lineárisak. Azonban a lineáris eset sok elve érvényesül.

Annak biztosítására, hogy egy nemlineáris probléma globális maximuma könnyen meghatározható legyen, a problémafelvetés gyakran megköveteli, hogy a függvények konvexek legyenek, és kompakt halmazaik legyenek alacsonyabb szintekből (vagyis olyan halmazokból, amelyeken a függvény valamely szintnél kisebb értéket vesz fel). .

Ez a Karush-Kuhn-Tucker állapot . Bizonyították a szükséges feltételeket a nemlineáris problémák lokális optimumának meghatározásához. Vannak további feltételek (korlátozás szabályszerűségi feltétele), amelyek szükségesek az optimális megoldás irányának meghatározásához. Itt az optimális megoldás a lokális optimumok egyike, amely nem biztos, hogy globális.

Szigorú Lagrange-elv: Lagrange kettősség

Ha egy nemlineáris programozási feladatot szabványos formában adunk meg

minimalizálni	$f_{0}(x)$
feltételek mellett	${\displaystyle f_{i}(x)\leqslant 0,\ i\in \left\{1,\dots ,m\right\))$
	${\displaystyle h_{i}(x)=0,\ i\in \left\{1,\dots ,p\right\))$

ha a tartomány nem üres belsővel rendelkezik, a Lagrange függvényt a következőképpen határozzuk meg ${\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)+\ összeg _{i=1}^{p}\nu _{i}h_{i}(x).

A és a vektorokat kettős változóknak vagy a problémához kapcsolódó Lagrange-szorzók vektorainak nevezzük . A kettős Lagrange függvényt a következőképpen határozzuk meg $\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)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^ {p}\nu _{i}h_{i}(x)\jobbra).

A g duális függvény akkor is konkáv, ha a kezdeti probléma nem konvex, mivel az affin függvények pontszerű infimuma. A kettős függvény alsó határokat ad az eredeti probléma optimális értékére. Bárkinek és bárkinek, amink van . $p^{*}$ $\lambda \geqslant 0$ $\nu$ $g(\lambda ,\nu )\leqslant p^{*}$

Ha a kényszer szabályossági feltételek , mint például a Slater feltétel teljesülnek , és az eredeti probléma konvex, akkor szigorú dualitásunk , azaz . $d^{*}=\max _{\lambda \geqslant 0,\nu }g(\lambda ,\nu )=\inf f_{0}=p^{*}$

Konvex problémák

Egy konvex minimalizálási probléma megszorításokkal – egyenlőtlenségekkel,

minimalizálni	$f(x)$
feltételek mellett	$g_{i}(x)\leqslant 0,\quad i=1,\dots ,m$

A Lagrange-féle kettős probléma az

maximalizálni	$\inf _{x}\left(f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\right)$
feltételek mellett	$u_{i}\geqslant 0,\quad i=1,\dots ,m$

ahol a célfüggvény a kettős Lagrange-függvény. Ha a és függvényekről ismert, hogy folyamatosan differenciálhatóak, akkor az infimum azokon a pontokon van, ahol a gradiens nulla. Egy feladat $f$ ${\displaystyle g_{1},\cdots ,g_{m))$

maximalizálni	$f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)$
feltételek mellett	$\nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)=0$
$u_{i}\geqslant 0,\quad i=1,\dots ,m$

duális Wolfe-problémának nevezik. Ez a feladat számításilag nehéz lehet, mivel a célfüggvény nem konvex a koordinátákban . Ezenkívül a megszorítás általában nem lineáris, így a duális Wolfe-probléma általában nem konvex optimalizálási probléma. Mindenesetre van egy gyenge kettősség [18] . ${\megjelenítési stílus (u,x)}$ $\nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)$

Történelem

George Danzig szerint a lineáris optimalizálás kettősségi tételét John von Neumann terjesztette elő sejtésként közvetlenül azután, hogy Danzig bemutatta a lineáris programozási problémát. Von Neumann észrevette, hogy a játékelméletéből származó információkat használt, és azt javasolta, hogy egy kétszemélyes, nulla összegű mátrixjáték egyenértékű egy lineáris programozási problémával. Ennek a ténynek a szigorú bizonyítékát először 1948-ban publikálta Albert Tucker és csoportja [19] .

Lásd még

A kettősség elve
Csillapítás (közelítő)

Jegyzetek

↑ Boyd, Vandenberghe, 2004 .
↑ A duális pár egy hármas , ahol egy mező feletti vektortér , az összes lineáris leképezés halmaza , a harmadik elem pedig egy bilineáris 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 , p. 106–113.
↑ Borwein, Zhu, 2005 .
↑ Ahuja, Magnanti, Orlin, 1993 .
↑ Bertsekas, Nedic, Ozdaglar, 2003 .
↑ Bertsekas, 1999 .
↑ Bertsekas, 2009 .
↑ Bonnans, Gilbert, Lemaréchal, Sagastizábal, 2006 , p. xiv+490.
↑ Hiriart-Urruty, Lemaréchal, 1993 , p. xviii+417.
↑ Hiriart-Urruty, Lemaréchal, 1993 , p. xviii+346.
↑ Lasdon, 2002 , p. xiii+523.
↑ Lemarechal, 2001 , p. 112–156.
↑ Minoux, 1986 , p. xxviii+489.
↑ Shapiro, 1979 , p. xvi+388.
↑ Geoffrion, 1971 , p. 1–37.
↑ Nering és Tucker 1993 , p. előszó Danzig.

Irodalom

Könyvek

Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Konvex elemzési és minimalizálási algoritmusok. I. rész: Alapok. - Berlin: Springer-Verlag, 1993. - T. 305. - S. xviii + 417. — (Grundlehren der Mathematischen Wissenschaften [A matematikai tudományok alapelvei]). — ISBN 3-540-56850-6 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. 14 Kettősség gyakorlóknak // Konvex elemzési és minimalizálási algoritmusok. II. rész: Fejlett elmélet és köteg módszerek. - Berlin: Springer-Verlag, 1993. - T. 306. - S. xviii + 346. — (Grundlehren der Mathematischen Wissenschaften [A matematikai tudományok alapelvei]). — ISBN 3-540-56852-2 .
Leon S Lasdon. Optimalizációs elmélet nagy rendszerek számára . - Mineola, New York: Dover Publications, Inc., 2002. - xiii+523. — ISBN 978-0-486-41999-2 .
Claude Lemarechal. Lagrange-relaxáció // Számítógépes kombinatorikus optimalizálás: A tavaszi iskola tanulmányai Schloß Dagstuhlban, 2000. május 15–19. - Berlin: Springer-Verlag, 2001. - 2241. kötet - 112-156. - (Lecture Notes in Computer Science (LNCS)). — ISBN 3-540-42877-1 . - doi : 10.1007/3-540-45586-8_4 .
Michel Minoux. Matematikai programozás: elmélet és algoritmusok. - Chichester: A Wiley-Interscience kiadvány. John Wiley & Sons, Ltd., 1986. – xxviii+489. — ISBN 0-471-90170-9 .
- M. Minu. Matematikai programozás. Elmélet és algoritmusok.
Evar D. Nering, Albert W. Tucker. Lineáris programozás és kapcsolódó problémák . - Boston, MA: Academic Press, 1993. - ISBN 978-0-12-515440-6 .
Stephen P. Boyd, Lieven Vandenberghe. Konvex optimalizálás . - Cambridge University Press, 2004. - ISBN 978-0-521-83378-3 .
Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Kettősség a vektoroptimalizálásban. - Springer, 2009. - ISBN 978-3-642-02885-4 .
Ernö Robert Csetnek. A klasszikus általánosított belsőpont szabályossági feltételek kudarcának leküzdése konvex optimalizálásban. A dualitáselmélet alkalmazásai maximális monoton operátorok kinagyítására. - Logos Verlag Berlin GmbH, 2010. - ISBN 978-3-8325-2503-3 .
Constantin Zalinescu. Konvex elemzés általános vektorterekben. – River Edge, NJ: World Scientific Publishing Co., Inc., 2002. – 106–113. - ISBN 981-238-067-1 .
Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Hálózati áramlások: elmélet, algoritmusok és alkalmazások. - Prentice Hall, 1993. - ISBN 0-13-617549-X .
Dimitri Bertsekas, Angelia Nedic, Asuman Ozdaglar. Konvex elemzés és optimalizálás. - Athena Scientific, 2003. - ISBN 1-886529-45-0 .
Dimitri P. Bertsekas. nemlineáris programozás. — 2. - Athena Scientific, 1999. - ISBN 1-886529-00-0 .
Dimitri P. Bertsekas. Konvex optimalizációs elmélet. - Athena Scientific, 2009. - ISBN 978-1-886529-31-1 .
J. Fredéric Bonnans, J. Charles Gilbert, Claude Lemaréchal, Claudia A. Sagastizábal. Numerikus optimalizálás: Elméleti és gyakorlati szempontok . — Második átdolgozott szerk. fordítása 1997. - Berlin: Springer-Verlag, 2006. - xiv+490. — (Egyetemi szöveg). — ISBN 3-540-35445-X . - doi : 10.1007/978-3-540-35447-5 .
Jeremy F. Shapiro. Matematikai programozás: Struktúrák és algoritmusok . - New York: Wiley-Interscience [John Wiley & Sons], 1979. - xvi + 388. o. — ISBN 0-471-77886-9 .
Jonathan Borwein, Qiji Zhu. A variációs elemzés technikái. - Springer, 2005. - ISBN 978-1-4419-2026-3 .

Cikkek

Kettősség a lineáris programozásban Gary D. Knott
Arthur M. Geoffrion. Kettősség a nemlineáris programozásban: egyszerűsített alkalmazás-orientált fejlesztés // SIAM Review. - 1971. - T. 13 , sz. 1 . - doi : 10.1137/1013001 . — .

További olvasnivalók

William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver. kombinatorikus optimalizálás. — 1. - John Wiley & Sons, 1997. - ISBN 0-471-55894-X .
Xugang Ye, Shih-Ping Han, Anhua Lin. Megjegyzés a Primal-Dual és az A* algoritmusok közötti kapcsolatról // International Journal of Operations Research and Information Systems. - 2010. - 1. évf. , szám. 1 . – 73–85 .
George B. Dantzig. Lineáris programozás és bővítmények. – Princeton, NJ: Princeton University Press, 1963.
Eugene Lawler. 4.5. A Max-Flow Min-Cut tétel kombinatorikus implikációi, 4.6. Max-Flow Min-Cut tétel lineáris programozási értelmezése // Kombinatorikus optimalizálás: hálózatok és matroidok. - Dover, 2001. - S. 117-120. - ISBN 0-486-41453-1 .
Andrzej Piotr Ruszczyński. nemlineáris optimalizálás. – Princeton, NJ: Princeton University Press , 2006. – xii+454. - ISBN 978-0691119151 .
Christos H. Papadimitriou, Kenneth Steiglitz. Kombinatorikus optimalizálás: Algoritmusok és komplexitás. - Dover, 1998. - ISBN 0-486-40258-4 .
Krzysztof C. Kiwiel, Torbjörn Larsson, P. O. Lindberg. Lagrange relaxation via ballstep subgradiens módszerek // Mathematics of Operations Research. - 2007. - augusztus ( 32. évf. , 3. szám ). – S. 669–686 . - doi : 10.1287/moor.1070.0261 .