Dualitate Gap

Decalajul de dualitate este diferența dintre soluțiile directe și cele duale . Dacă este valoarea optimă a problemei duale și este valoarea optimă a problemei directe, atunci decalajul de dualitate este . Această valoare este întotdeauna mai mare sau egală cu zero (pentru probleme de minimizare). Decalajul de dualitate este zero dacă și numai dacă există o dualitate puternică . În caz contrar, discontinuitatea este strict pozitivă, iar dualitatea slabă are loc [1] . $d^{*}$ $p^{*}$ $p^{*}-d^{*}$

Descriere

În cazul general, fie perechea duală spații separate local convexe și să fie dat . Apoi, dată fiind o funcție , putem defini problema directă ca $\left(X,X^{*}\right)$ $\left(Y,Y^{*}\right)$ $f:X\la \mathbb {R} \cup \{+\infty \)$

\inf _{x\in X}f(x).\,

Dacă există constrângeri, acestea pot fi integrate în funcție adăugând o funcție indicator pe constrângeri — . Atunci să fie o funcție de perturbare astfel încât . Decalajul de dualitate este diferența, care este dată de formulă $f$ $eu$ $f=f+I$ $F:X\times Y\to \mathbb {R} \cup \{+\infty \)$ $F(x,0)=f(x)$

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

unde este funcția conjugată a ambelor variabile [2] [3] [4] . $F^{*}$

Alternative

În optimizarea computațională , este adesea menționat un alt „decalaj de dualitate”, care este diferența de valori dintre orice soluție și valoarea unei valori admisibile, dar suboptimale a problemei directe. Această alternativă „decalaj de dualitate” cuantifică discrepanța dintre valoarea valorii curente fezabile, dar suboptimale, a problemei directe și valoarea problemei duale. Valoarea problemei duale, conform condițiilor de regularitate, este egală cu valoarea relaxării convexe a problemei directe. Relaxarea convexă este o problemă care se obține prin înlocuirea unui set neconvex de soluții fezabile cu carcasa sa convexă închisă și înlocuirea unei funcții neconvexe cu închiderea sa convexă , adică cu o funcție a cărei epigraf este o carcasă convexă închisă a epigrafa funcției obiective inițiale a problemei directe [5] [6 ] [7] [8] [9] [10] [11] [12] [13] .

Note

↑ Borwein, Zhu, 2005 .
↑ Boţ, Wanka, Grad, 2009 .
↑ Csetnek, 2010 .
↑ Zălinescu, 2002 , p. 106–113.
↑ Ahuja, Magnanti, Orlin, 1993 .
↑ Bertsekas, 1999 .
↑ 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.

Literatură

Jonathan Borwein, Qiji Zhu. Tehnici de analiză variațională. - Springer, 2005. - ISBN 978-1-4419-2026-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 .
Zălinescu C. Analiza convexă în spații vectoriale generale. — River Edge, NJ: World Scientific Publishing Co. Inc, 2002. - 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 P. Bertsekas. programare neliniară. — al 2-lea. - Athena Scientific, 1999. - ISBN 1-886529-00-0 .
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 franceza. - Berlin: Springer-Verlag, 2006. - (Universitex). — ISBN 3-540-35445-X . - doi : 10.1007/978-3-540-35447-5 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Algoritmi de analiză convexă și minimizare, Volumul I: Fundamente. - Berlin: Springer-Verlag, 1993. - V. 305. - (Grundlehren der Mathematischen Wissenschaften [Principii fundamentale ale științelor matematice]). — ISBN 3-540-56850-6 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. XII. Abstract Duality for Practitioners // Algoritmi de analiză și minimizare convexă, Volumul II: Teorie avansată și metode de pachet. - Berlin: Springer-Verlag, 1993. - V. 306. - (Grundlehren der Mathematischen Wissenschaften [Principii fundamentale ale științelor matematice]). — ISBN 3-540-56852-2 . - doi : 10.1007/978-3-662-06409-2_4 .
Leon S Lasdon. Teoria optimizării pentru sisteme mari . - Mineola, New York: Dover Publications, Inc., 2002. - 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 / Michael Jünger, Denis Naddef. - Berlin: Springer-Verlag, 2001. - T. 2241. - (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 / Egon Balas (înainte); Steven Vajda (trad) din (1983 Paris: Dunod). - Chichester: O publicație Wiley-Interscience. John Wiley & Sons, Ltd., 1986. - ISBN 0-471-90170-9 . Traducerea cărții
- Programare matematică: Teorie și algoritmi. — al 2-lea. - Paris: Tec & Doc, 2008. - p. xxx+711 p. - ISBN 978-2-7430-1000-3 .
Jeremy F. Shapiro. Programare matematică: Structuri și algoritmi . - New York: Wiley-Interscience [John Wiley & Sons], 1979. - ISBN 0-471-77886-9 .