Dualitet (optimering)

Dualitet , eller principen om dualitet , är principen genom vilken optimeringsproblem kan betraktas ur två synvinklar, som ett direkt problem eller ett dubbelt problem . Lösningen av det dubbla problemet ger den nedre gränsen för det direkta problemet (vid minimering) [1] . Men i det allmänna fallet sammanfaller inte nödvändigtvis värdena för de objektiva funktionerna för de optimala lösningarna för de direkta och dubbla problemen. Skillnaden i dessa värden, om den observeras, kallas ett dualitetsgap . För problem med konvex programmering är dualitetsgapet lika med noll när villkoren för regelbundenhet hos begränsningarna är uppfyllda .

Dubbla problem

Vanligtvis antyder termen "dubbelproblem" det lagrangska dubbla problemet , men andra dubbla problem används också, som Wolfes dubbla problem och Fenchels dubbla problem . Det dubbla Lagrange-problemet erhålls genom att generera en Lagrange , använda icke-negativa Lagrange-multiplikatorer för att lägga till begränsningar till den objektiva funktionen, och minimera Lagrangian med avseende på några variabler i det direkta problemet. En sådan lösning ger variablerna för det direkta problemet som funktioner av Lagrange-multiplikatorer, som kallas dubbla variabler, så att det nya problemet blir problemet med att maximera objektivfunktionen med avseende på de dubbla variablerna under de genererade begränsningarna på de dubbla variablerna ( åtminstone icke-negativitet).

I allmänhet, givet det dubbla paret [2] av ett separerbart lokalt konvext utrymme och en funktion , kan vi definiera det direkta problemet som att hitta , så att det med andra ord är infimum (exakt nedre gräns) för funktionen . $\left(X,X^{*}\right)$ ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \))$ ${\hat {x}}$ $f({\hat {x)))=\inf _{x\in X}f(x).\,$ $f({\hat {x)))$ $f$

Om det finns restriktioner kan de byggas in i funktionen om vi sätter , var är indikatorfunktionen . Låt nu (för ett annat dubbelpar ) vara en störningsfunktion så att [3] . $f$ ${\tilde {f}}=f+I_{\mathrm {begränsningar} }$ $jag$ ${\displaystyle F:X\ gånger Y\ till \mathbb {R} \cup \{+\infty \))$ $\left(Y,Y^{*}\right)$ $F(x,0)={\tilde {f))(x)$

Dualitetsgapet är skillnaden mellan höger och vänster sida av ojämlikheten

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

där är den konjugerade funktionen för båda variablerna, och betyder supremum (exakt övre gräns) [3] [4] [5] . $F^{*}$ $\upp$

Duality Gap

Dualitetsgapet är skillnaden mellan värdena för alla lösningar på det primära problemet och värdena för alla lösningar på det dubbla problemet. Om är det optimala värdet av det dubbla problemet, och är det optimala värdet av det direkta problemet, är dualitetsgapet . Detta värde är alltid större än eller lika med 0. Dualitetsgapet är noll om och endast om det finns stark dualitet . Annars är diskontinuiteten strikt positiv och svag dualitet äger rum [6] . $d^{*}$ $p^{*}$ $p^{*}-d^{*}$

I numeriska optimeringsproblem används ofta ett annat "dualitetsgap", som är lika med skillnaden mellan valfri dubbellösning och värdet av en tillåten, men inte lokalt optimal, iteration för det direkta problemet. Alternativet "dualitetsgap" uttrycker diskrepansen mellan värdet av den nuvarande genomförbara, men inte lokalt optimala, lösningen för det primära problemet och värdet av det dubbla problemet. Värdet av det dubbla problemet är lika, under villkoret av regelbundenhet av begränsningar, med värdet av den konvexa försvagningen av det direkta problemet, där den konvexa försvagningen uppstår som ett resultat av att den icke-konvexa uppsättningen av genomförbara lösningar ersätts med dess slutna konvext skrov och ersätter den icke-konvexa funktionen med dess konvexa stängning , det vill säga med en funktion vars epigraf är en stängd konvex genom att stänga den ursprungliga objektiva funktionen av det direkta problemet [7] [8] [9] [10] [11 ] [12] [13] [14] [15] [16] [17] .

Linjär skiftläge

Linjära programmeringsproblem är optimeringsproblem där objektivfunktionen och begränsningarna [ en ] är . I det direkta problemet är objektivfunktionen en linjär kombination av n variabler. Det finns m begränsningar, som var och en begränsar den linjära kombinationen av n variabler ovanifrån. Målet är att maximera värdet av målfunktionen under begränsningar. Lösningen är en vektor (lista) med n värden som ger maximivärdet för objektivfunktionen.

I det dubbla problemet är den objektiva funktionen en linjär kombination av m värden som är den högra sidan av primala problemets m begränsningar. Det finns n dubbla begränsningar, som var och en begränsar en linjär kombination av m dubbla variabler underifrån.

Förhållandet mellan primära och dubbla problem

I det linjära fallet, i det direkta problemet, från varje punkt av det lokala optimum som uppfyller alla begränsningar, finns det en riktning eller delrum av riktningar, och rörelse i denna riktning ökar den objektiva funktionen. Ett steg i någon sådan riktning sägs minska gapet mellan en genomförbar lösning (eller genomförbar plan ) och en av begränsningarna. En ogiltig möjlig lösning är en lösning som bryter mot en eller flera begränsningar.

I det dubbla problemet multipliceras elementen i den dubbla vektorn med kolumner som motsvarar begränsningarna i det primära problemet. Störningen av den dubbla vektorn i det dubbla problemet är ekvivalent med att revidera den övre gränsen för det primära problemet. Vid lösning av det dubbla problemet eftersträvas den minsta övre gränsen, det vill säga den dubbla vektorn ändras på ett sådant sätt att gapet mellan den genomförbara lösningen och det faktiska optimum minskar.

För mer information om sambandet mellan de primära och dubbla problemen, se artikeln " Dual Problems of Linear Programming ".

Ekonomisk tolkning

Om vi förstår vårt primära linjära programmeringsproblem som ett klassiskt "resursallokeringsproblem", kan dess dubbla problem tolkas som ett problem med " resursuppskattning " .

Icke-linjärt skiftläge

I icke-linjär programmering är begränsningar inte nödvändigtvis linjära. Men många av principerna för det linjära fallet gäller.

För att säkerställa att det globala maximumet för ett icke-linjärt problem lätt kan definieras kräver problemformuleringen ofta att funktioner är konvexa och har kompakta uppsättningar av lägre nivåer (det vill säga uppsättningar där funktionen har ett värde som är mindre än någon nivå) .

Detta är Karush-Kuhn-Tuckers tillstånd . De visade de nödvändiga förutsättningarna för att bestämma det lokala optimum för icke-linjära problem. Det finns ytterligare villkor (constraints regularity condition) som är nödvändiga för att bestämma riktningen till den optimala lösningen. Här är den optimala lösningen en av de lokala optima, som kanske inte är globala.

Strikt Lagrangiansk princip: Lagrangedualitet

Om ett icke-linjärt programmeringsproblem anges i standardformuläret

minimera	$f_{0}(x)$
under förhållanden	${\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\))$

med en domän som inte är tom, definieras Lagrange -funktionen som ${\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)+\summa _{i=1}^{m}\lambda _{i}f_{i}(x)+\ summa _{i=1}^{p}\nu _{i}h_{i}(x).

Vektorerna och kallas dubbla variabler eller vektorer av Lagrange-multiplikatorer associerade med problemet. Den dubbla Lagrange-funktionen definieras som $\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)+\summa _{i=1}^ {p}\nu _{i}h_{i}(x)\höger).

Den dubbla funktionen g är konkav även om det initiala problemet inte är konvext, eftersom det är punktvis infimum av affina funktioner. Den dubbla funktionen ger lägre gränser för det optimala värdet av det ursprungliga problemet. För vem som helst och alla vi har . $p^{*}$ $\lambda \geqslant 0$ $\nu$ $g(\lambda ,\nu )\leqslant p^{*}$

Om villkoren för begränsningsregelbundenhet , såsom Slater-villkoret , är uppfyllda och det ursprungliga problemet är konvext, så har vi strikt dualitet , det vill säga . $d^{*}=\max _{\lambda \geqslant 0,\nu }g(\lambda ,\nu )=\inf f_{0}=p^{*}$

Konvexa problem

För ett konvext minimeringsproblem med begränsningar — ojämlikheter,

minimera	$f(x)$
under förhållanden	$g_{i}(x)\leqslant 0,\quad i=1,\dots ,m$

Det lagrangska dubbla problemet är

maximera	$\inf _{x}\left(f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\right)$
under förhållanden	$u_{i}\geqslant 0,\quad i=1,\dots ,m$

där objektivfunktionen är den dubbla Lagrangefunktionen. Om funktionerna och är kända för att vara kontinuerligt differentierbara, är infimum vid de punkter där gradienten är noll. En uppgift $f$ ${\displaystyle g_{1},\cdots ,g_{m))$

maximera	$f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)$
under förhållanden	$\nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)=0$
$u_{i}\geqslant 0,\quad i=1,\dots ,m$

kallas det dubbla Wolfe-problemet. Denna uppgift kan vara beräkningsmässigt svår, eftersom objektivfunktionen inte är konvex i koordinaterna . Dessutom är begränsningen i allmänhet icke-linjär, så det dubbla Wolfe-problemet är vanligtvis ett icke-konvext optimeringsproblem. Det finns i alla fall en svag dualitet [18] . $(u,x)$ $\nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)$

Historik

Enligt George Danzig lades dualitetssatsen för linjär optimering fram som en gissning av John von Neumann omedelbart efter att Danzig introducerade det linjära programmeringsproblemet. Von Neumann märkte att han använde information från sin spelteori och föreslog att ett tvåpersoners nollsummematrisspel motsvarar ett linjärt programmeringsproblem. Ett rigoröst bevis på detta faktum publicerades först 1948 av Albert Tucker och hans grupp [19] .

Se även

Dualitetsprincipen
Dämpning (approximation)

Anteckningar

↑ Boyd, Vandenberghe, 2004 .
↑ Det dubbla paret är en trippel , där är ett vektorrum över ett fält , är mängden av alla linjära avbildningar , och det tredje elementet är en bilinjär form . $\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 , sid. 106–113.
↑ Borwein, Zhu, 2005 .
↑ Ahuja, Magnanti, Orlin, 1993 .
↑ Bertsekas, Nedic, Ozdaglar, 2003 .
↑ Bertsekas, 1999 .
↑ Bertsekas, 2009 .
↑ Bonnans, Gilbert, Lemaréchal, Sagastizábal, 2006 , sid. xiv+490.
↑ Hiriart-Urruty, Lemaréchal, 1993 , sid. xviii+417.
↑ Hiriart-Urruty, Lemaréchal, 1993 , sid. xviii+346.
↑ Lasdon, 2002 , sid. xiii+523.
↑ Lemarechal, 2001 , sid. 112–156.
↑ Minoux, 1986 , sid. xxviii+489.
↑ Shapiro, 1979 , sid. xvi+388.
↑ Geoffrion, 1971 , sid. 1–37.
↑ Nering och Tucker 1993 , sid. förord av Danzig.

Litteratur

Böcker

Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Konvex analys och minimeringsalgoritmer. Del I: Grunderna. - Berlin: Springer-Verlag, 1993. - T. 305. - S. xviii + 417. — (Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]). — ISBN 3-540-56850-6 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. 14 Dualitet för utövare // Konvex analys och minimeringsalgoritmer. Del II: Avancerad teori och buntmetoder. - Berlin: Springer-Verlag, 1993. - T. 306. - S. xviii + 346. — (Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]). — ISBN 3-540-56852-2 .
Leon S Lasdon. Optimeringsteori för stora system . - Mineola, New York: Dover Publications, Inc., 2002. - s. xiii+523. — ISBN 978-0-486-41999-2 .
Claude Lemarechal. Lagrangian relaxation // Computational combinatorial optimization: Papers from the Spring School som hölls i Schloß Dagstuhl, 15–19 maj 2000. - Berlin: Springer-Verlag, 2001. - Vol. 2241. - S. 112-156. - (Lecture Notes in Computer Science (LNCS)). — ISBN 3-540-42877-1 . - doi : 10.1007/3-540-45586-8_4 .
Michel Minoux. Matematisk programmering: Teori och algoritmer. - Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd., 1986. - s. xxviii+489. — ISBN 0-471-90170-9 .
- M. Minu. Matematisk programmering. Teori och algoritmer.
Evar D. Nering, Albert W. Tucker. Linjär programmering och relaterade problem . - Boston, MA: Academic Press, 1993. - ISBN 978-0-12-515440-6 .
Stephen P. Boyd, Lieven Vandenberghe. Konvex optimering . - Cambridge University Press, 2004. - ISBN 978-0-521-83378-3 .
Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Dualitet i vektoroptimering. - Springer, 2009. - ISBN 978-3-642-02885-4 .
Ernö Robert Csetnek. Att övervinna misslyckandet med de klassiska generaliserade inre punktreguljäritetsförhållandena i konvex optimering. Tillämpningar av dualitetsteorin på förstoringar av maximala monotona operatorer. - Logos Verlag Berlin GmbH, 2010. - ISBN 978-3-8325-2503-3 .
Constantin Zalinescu. Konvex analys i allmänna vektorrum. — 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. Nätverksflöden: teori, algoritmer och tillämpningar. - Prentice Hall, 1993. - ISBN 0-13-617549-X .
Dimitri Bertsekas, Angelia Nedic, Asuman Ozdaglar. Konvex analys och optimering. - Athena Scientific, 2003. - ISBN 1-886529-45-0 .
Dimitri P. Bertsekas. icke-linjär programmering. — 2:a. - Athena Scientific, 1999. - ISBN 1-886529-00-0 .
Dimitri P. Bertsekas. Konvex optimeringsteori. - Athena Scientific, 2009. - ISBN 978-1-886529-31-1 .
J. Fredéric Bonnans, J. Charles Gilbert, Claude Lemaréchal, Claudia A. Sagastizábal. Numerisk optimering: Teoretiska och praktiska aspekter . — Andra reviderade uppl. översättning av 1997. - Berlin: Springer-Verlag, 2006. - s. xiv+490. — (Universitetstext). — ISBN 3-540-35445-X . - doi : 10.1007/978-3-540-35447-5 .
Jeremy F. Shapiro. Matematisk programmering: Strukturer och algoritmer . - New York: Wiley-Interscience [John Wiley & Sons], 1979. - s. xvi + 388. — ISBN 0-471-77886-9 .
Jonathan Borwein, Qiji Zhu. Tekniker för variationsanalys. - Springer, 2005. - ISBN 978-1-4419-2026-3 .

Artiklar

Dualitet i linjär programmering Gary D. Knott
Arthur M. Geoffrion. Dualitet i icke-linjär programmering: en förenklad applikationsorienterad utveckling // SIAM Review. - 1971. - T. 13 , nr. 1 . - doi : 10.1137/1013001 . — .

Ytterligare läsning

William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver. kombinatorisk optimering. — 1:a. - John Wiley & Sons, 1997. - ISBN 0-471-55894-X .
Xugang Ye, Shih-Ping Han, Anhua Lin. En notering om kopplingen mellan Primal-Dual och A* -algoritmerna // International Journal of Operations Research and Information Systems. - 2010. - Vol. 1 , nummer. 1 . — s. 73–85 .
George B. Dantzig. Linjär programmering och tillägg. — Princeton, NJ: Princeton University Press, 1963.
Eugene Lawler. 4.5. Kombinatoriska implikationer av Max-Flow Min-Cut Theorem, 4.6. Linjär programmeringstolkning av Max-Flow Min-Cut Theorem // Kombinatorisk optimering: nätverk och matroider. - Dover, 2001. - S. 117-120. - ISBN 0-486-41453-1 .
Andrzej Piotr Ruszczyński. icke-linjär optimering. — Princeton, NJ: Princeton University Press , 2006. — s. xii+454. - ISBN 978-0691119151 .
Christos H. Papadimitriou, Kenneth Steiglitz. Kombinatorisk optimering: Algoritmer och komplexitet. - Dover, 1998. - ISBN 0-486-40258-4 .
Krzysztof C. Kiwiel, Torbjörn Larsson, P. O. Lindberg. Lagrangian relaxation via ballstep subgradient methods // Mathematics of Operations Research. - 2007. - Augusti ( vol. 32 , nummer 3 ). — S. 669–686 . - doi : 10.1287/moor.1070.0261 .