Dualitate (optimizare)

Dualitatea , sau principiul dualității , este principiul prin care problemele de optimizare pot fi considerate din două puncte de vedere, ca o problemă directă sau o problemă duală . Rezolvarea problemei duale dă limita inferioară a problemei directe (la minimizare) [1] . Cu toate acestea, în cazul general, valorile funcțiilor obiective ale soluțiilor optime ale problemelor directe și duale nu coincid neapărat. Diferența dintre aceste valori, dacă este observată, se numește decalaj de dualitate . Pentru problemele de programare convexă , decalajul de dualitate este egal cu zero atunci când sunt îndeplinite condiţiile de regularitate a constrângerilor .

Problemă dublă

De obicei, termenul „problema duală” implică problema duală lagrangiană , dar sunt folosite și alte probleme duale, cum ar fi problema duală a lui Wolfe și problema duală a lui Fenchel . Problema Lagrange duală este obținută prin generarea unui Lagrangian , folosind multiplicatori Lagrange nenegativi pentru a adăuga constrângeri la funcția obiectiv și minimizând Lagrangianul în raport cu unele variabile ale problemei directe. O astfel de soluție dă variabilele problemei directe ca funcții ale multiplicatorilor Lagrange, care se numesc variabile duale, astfel încât noua problemă devine problema maximizării funcției obiectiv în raport cu variabilele duale sub constrângerile generate asupra variabilelor duale ( cel puțin non-negativitatea).

În general, având în vedere perechea duală [2] a unui spațiu convex local separabil și a unei funcții , putem defini problema directă ca găsirea , astfel încât, cu alte cuvinte, este infima (limita inferioară exactă) a funcției . $\left(X,X^{*}\right)$ $f:X\la \mathbb {R} \cup \{+\infty \)$ ${\hat {x}}$ $f({\hat {x)})=\inf _{x\in X}f(x).\,$ $f({\hat {x}))$ $f$

Dacă există restricții, acestea pot fi încorporate în funcție dacă punem , unde este funcția indicator . Fie acum (pentru o altă pereche duală ) o funcție de perturbare astfel încât [3] . $f$ ${\tilde {f}}=f+I_{\mathrm {constrângeri} }$ $eu$ $F:X\times Y\to \mathbb {R} \cup \{+\infty \)$ $\left(Y,Y^{*}\right)$ $F(x,0)={\tilde {f))(x)$

Decalajul de dualitate este diferența dintre partea dreaptă și stângă a inegalității

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

unde este funcția conjugată a ambelor variabile și înseamnă supremul (limită superioară exactă) [3] [4] [5] . $F^{*}$ $\sus$

Duality Gap

Decalajul de dualitate este diferența dintre valorile oricăror soluții la problema primară și valorile oricăror soluții la problema duală. Dacă este valoarea optimă a problemei duale și este valoarea optimă a problemei directe, decalajul de dualitate este . Această valoare este întotdeauna mai mare sau egală cu 0. Intervalul de dualitate este zero dacă și numai dacă există o dualitate puternică . În caz contrar, discontinuitatea este strict pozitivă și are loc o dualitate slabă [6] . $d^{*}$ $p^{*}$ $p^{*}-d^{*}$

În problemele de optimizare numerică, este adesea folosit un alt „decalaj de dualitate”, care este egal cu diferența dintre orice soluție duală și valoarea unei iterații admisibile, dar nu optimă local, pentru problema directă. Alternativa „decalaj de dualitate” exprimă discrepanța dintre valoarea soluției curente fezabile, dar nu optimă local, pentru problema primară și valoarea problemei duale. Valoarea problemei duale este egală, în condiția regularității constrângerilor, cu valoarea slăbirii convexe a problemei directe, unde slăbirea convexă apare ca urmare a înlocuirii mulțimii neconvexe de soluții fezabile cu cea închisă a acesteia. carcasă convexă și înlocuirea funcției neconvexe cu închiderea ei convexă , adică cu o funcție a cărei epigrafă este o convexă închisă prin închiderea funcției obiective inițiale a problemei directe [7] [8] [9] [10] [11 ] [12] [13] [14] [15] [16] [17] .

Caz liniar

Problemele de programare liniară sunt probleme de optimizare în care funcția obiectiv și constrângerile sunt liniare. În problema directă, funcția obiectiv este o combinație liniară de n variabile. Există m constrângeri, fiecare dintre acestea limitând combinația liniară a n variabile de sus. Scopul este de a maximiza valoarea funcției obiectiv sub constrângeri. Soluția este un vector (listă) de n valori care dă valoarea maximă a funcției obiectiv.

În problema duală, funcția obiectiv este o combinație liniară de m valori care sunt părțile din dreapta ale constrângerilor m ale problemei primare. Există n constrângeri duale, fiecare dintre acestea limitând o combinație liniară de m variabile duale de jos.

Relația dintre problemele primare și cele duale

În cazul liniar, în problema directă, din fiecare punct al optimului local care satisface toate constrângerile, există o direcție sau subspațiu de direcții, iar mișcarea în această direcție crește funcția obiectiv. Se spune că o mișcare în orice astfel de direcție reduce decalajul dintre o soluție fezabilă (sau un plan fezabil ) și una dintre constrângeri. O soluție posibilă nevalidă este o soluție care încalcă una sau mai multe constrângeri.

În problema duală, elementele vectorului dual sunt înmulțite cu coloane care corespund constrângerilor din problema primară. Perturbarea vectorului dual în problema duală este echivalentă cu revizuirea limitei superioare a problemei primare. La rezolvarea problemei duale se caută cea mai mică limită superioară, adică vectorul dual se modifică în așa fel încât să reducă decalajul dintre soluția fezabilă și optimul real.

Pentru mai multe informații despre legătura dintre problemele primare și cele duale, consultați articolul „ Probleme duale ale programării liniare ”.

Interpretare economică

Dacă înțelegem problema noastră primară de programare liniară ca o problemă clasică de „alocare a resurselor”, problema sa duală poate fi interpretată ca o de „ estimare a resurselor .

Caz neliniar

În programarea neliniară, constrângerile nu sunt neapărat liniare. Cu toate acestea, se aplică multe dintre principiile cazului liniar.

Pentru a se asigura că maximul global al unei probleme neliniare poate fi definit cu ușurință, enunțul problemei necesită adesea ca funcțiile să fie convexe și să aibă seturi compacte de niveluri inferioare (adică seturi pe care funcția ia o valoare mai mică decât un anumit nivel) .

Aceasta este condiția Karush-Kuhn-Tucker . Au demonstrat condițiile necesare pentru determinarea optimului local al problemelor neliniare. Există condiții suplimentare (condiția de regularitate a constrângerilor) care sunt necesare pentru a determina direcția către soluția optimă . Aici, soluția optimă este una dintre optima locală, care poate să nu fie globală.

Principiul lagrangian strict: dualitatea Lagrange

Dacă o problemă de programare neliniară este dată în forma standard

minimiza	$f_{0}(x)$
in conditii	$f_{i}(x)\leqslant 0,\i\in \left\{1,\dots ,m\right\)$
	$h_{i}(x)=0,\i\in \left\{1,\dots,p\right\)$

cu domeniul având un interior nevid, funcția Lagrange este definită ca ${\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)+\ suma _{i=1}^{p}\nu _{i}h_{i}(x).

Vectorii și sunt numiți variabile duale sau vectori ai multiplicatorilor Lagrange asociați cu problema. Funcția duală Lagrange este definită ca $\lambda$ $\nu$ $g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\la \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)\right).

Funcția duală g este concavă chiar dacă problema inițială nu este convexă, deoarece este infimul punctual al funcțiilor afine. Funcția duală oferă limite inferioare pentru valoarea optimă a problemei inițiale. Pentru oricine și oricine avem . $p^{*}$ $\lambda \geqslant 0$ $\nu$ $g(\lambda ,\nu )\leqslant p^{*}$

Dacă condițiile de regularitate a constrângerii , cum ar fi condiția Slater , sunt îndeplinite , iar problema inițială este convexă, atunci avem dualitate strictă , adică . $d^{*}=\max _{\lambda \geqslant 0,\nu }g(\lambda,\nu )=\inf f_{0}=p^{*}$

Probleme convexe

Pentru o problemă de minimizare convexă cu constrângeri — inegalități,

minimiza	$f(x)$
in conditii	$g_{i}(x)\leqslant 0,\quad i=1,\dots,m$

Problema duală lagrangiană este

maximiza	$\inf _{x}\left(f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\right)$
in conditii	$u_{i}\geqslant 0,\quad i=1,\dots,m$

unde funcția obiectiv este funcția Lagrange duală. Dacă se știe că funcțiile și sunt diferențiabile continuu, atunci infimul este în punctele în care gradientul este zero. O sarcină $f$ $g_{1},\cdots,g_{m)$

maximiza	$f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)$
in conditii	$\nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)=0$
$u_{i}\geqslant 0,\quad i=1,\dots,m$

se numește problema Wolfe duală. Această sarcină poate fi dificilă din punct de vedere computațional, deoarece funcția obiectiv nu este convexă în coordonate . De asemenea, constrângerea este în general neliniară, astfel încât problema Wolfe duală este de obicei o problemă de optimizare neconvexă. În orice caz, există o dualitate slabă [18] . $(u,x)$ $\nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)$

Istorie

Potrivit lui George Danzig , teorema dualității pentru optimizarea liniară a fost prezentată ca o presupunere de către John von Neumann imediat după ce Danzig a introdus problema de programare liniară. Von Neumann a observat că a folosit informații din teoria sa de joc și a sugerat că un joc cu matrice cu sumă zero de două persoane este echivalent cu o problemă de programare liniară. O dovadă riguroasă a acestui fapt a fost publicată pentru prima dată în 1948 de Albert Tucker și grupul său [19] .

Vezi și

Principiul dualității
Atenuare (aproximare)

Note

↑ Boyd, Vandenberghe, 2004 .
↑ Perechea duală este un triplu , unde este un spațiu vectorial peste un câmp , este mulțimea tuturor mapărilor liniare , iar al treilea element este o formă biliniară . $\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 și Tucker 1993 , p. prefaţă de Danzig.

Literatură

Cărți

Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Algoritmi de analiză și minimizare convexă. Partea I: Fundamente. - Berlin: Springer-Verlag, 1993. - T. 305. - S. xviii + 417. — (Grundlehren der Mathematischen Wissenschaften [Principii fundamentale ale științelor matematice]). — ISBN 3-540-56850-6 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. 14 Dualitate pentru practicieni // Algoritmi de analiză și minimizare convexă. Partea a II-a: Teorie avansată și metode de pachet. - Berlin: Springer-Verlag, 1993. - T. 306. - S. xviii + 346. — (Grundlehren der Mathematischen Wissenschaften [Principii fundamentale ale științelor matematice]). — ISBN 3-540-56852-2 .
Leon S Lasdon. Teoria optimizării pentru sisteme mari . - Mineola, New York: Dover Publications, Inc., 2002. - p. xiii+523. — ISBN 978-0-486-41999-2 .
Claude Lemarechal. Relaxare lagrangiană // Optimizare combinatorie computațională: Lucrări de la școala de primăvară ținută în Schloß Dagstuhl, 15–19 mai 2000. - Berlin: Springer-Verlag, 2001. - Vol. 2241. - P. 112-156. - (Lecture Notes in Computer Science (LNCS)). — ISBN 3-540-42877-1 . - doi : 10.1007/3-540-45586-8_4 .
Michel Minoux. Programare matematică: Teorie și algoritmi. - Chichester: O publicație Wiley-Interscience. John Wiley & Sons, Ltd., 1986. - p. xxviii+489. — ISBN 0-471-90170-9 .
- M. Minu. Programare matematică. Teorie și algoritmi.
Evar D. Nering, Albert W. Tucker. Programare liniară și probleme conexe . - Boston, MA: Academic Press, 1993. - ISBN 978-0-12-515440-6 .
Stephen P. Boyd, Lieven Vandenberghe. Optimizare convexă . - Cambridge University Press, 2004. - ISBN 978-0-521-83378-3 .
Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Dualitate în optimizarea vectorială. - Springer, 2009. - ISBN 978-3-642-02885-4 .
Ernö Robert Csetnek. Depășirea eșecului condițiilor clasice de regularitate a punctului interior generalizat în optimizarea convexă. Aplicații ale teoriei dualității la extinderea operatorilor monotoni maximali. - Logos Verlag Berlin GmbH, 2010. - ISBN 978-3-8325-2503-3 .
Constantin Zalinescu. Analiza convexă în spații vectoriale generale. — River Edge, NJ: World Scientific Publishing Co., Inc., 2002. — pp. 106–113. - ISBN 981-238-067-1 .
Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Fluxuri de rețea: teorie, algoritmi și aplicații. - Prentice Hall, 1993. - ISBN 0-13-617549-X .
Dimitri Bertsekas, Angelia Nedic, Asuman Ozdaglar. Analiză și optimizare convexă. - Athena Scientific, 2003. - ISBN 1-886529-45-0 .
Dimitri P. Bertsekas. programare neliniară. — al 2-lea. - Athena Scientific, 1999. - ISBN 1-886529-00-0 .
Dimitri P. Bertsekas. Teoria optimizării convexe. - Athena Scientific, 2009. - ISBN 978-1-886529-31-1 .
J. Fredéric Bonnans, J. Charles Gilbert, Claude Lemaréchal, Claudia A. Sagastizábal. Optimizare numerică: Aspecte teoretice și practice . — Ed. a doua revizuită. de traducere din 1997. - Berlin: Springer-Verlag, 2006. - p. xiv+490. — (text universitar). — ISBN 3-540-35445-X . - doi : 10.1007/978-3-540-35447-5 .
Jeremy F. Shapiro. Programare matematică: Structuri și algoritmi . - New York: Wiley-Interscience [John Wiley & Sons], 1979. - p. xvi + 388. — ISBN 0-471-77886-9 .
Jonathan Borwein, Qiji Zhu. Tehnici de analiză variațională. - Springer, 2005. - ISBN 978-1-4419-2026-3 .

Articole

Dualitate în programarea liniară Gary D. Knott
Arthur M. Geoffrion. Dualitate în programarea neliniară: o dezvoltare simplificată orientată spre aplicații // Revizuirea SIAM. - 1971. - T. 13 , nr. 1 . - doi : 10.1137/1013001 . — .

Lectură suplimentară

William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver. optimizare combinatorie. — 1-a. - John Wiley & Sons, 1997. - ISBN 0-471-55894-X .
Xugang Ye, Shih-Ping Han, Anhua Lin. O notă despre conexiunea dintre primal-dual și algoritmii A* // Jurnalul Internațional de Cercetare Operațională și Sisteme Informaționale. - 2010. - Vol. 1 , numărul. 1 . — p. 73–85 .
George B. Dantzig. Programare liniară și extensii. — Princeton, NJ: Princeton University Press, 1963.
Eugene Lawler. 4.5. Implicații combinatorii ale teoremei Max-Flow Min-Cut, 4.6. Interpretarea programarii liniare a teoremei Max-Flow Min-Cut // Optimizare combinatorie: rețele și matroizi. - Dover, 2001. - S. 117-120. - ISBN 0-486-41453-1 .
Andrzej Piotr Ruszczyński. optimizare neliniară. — Princeton, NJ: Princeton University Press , 2006. — p. xii+454. - ISBN 978-0691119151 .
Christos H. Papadimitriou, Kenneth Steiglitz. Optimizare combinatorie: algoritmi si complexitate. - Dover, 1998. - ISBN 0-486-40258-4 .
Krzysztof C. Kiwiel, Torbjörn Larsson, P. O. Lindberg. Relaxare lagrangiană prin metode de subgradient cu pas de bile // Matematica cercetării operaționale. - 2007. - August ( vol. 32 , numărul 3 ). — S. 669–686 . - doi : 10.1287/moor.1070.0261 .