Dualitetsgap

Dualitetskløften er forskellen mellem de direkte og dobbelte løsninger . Hvis er den optimale værdi af det dobbelte problem, og er den optimale værdi af det direkte problem, så er dualitetsgabet . Denne værdi er altid større end eller lig med nul (for minimeringsproblemer). Dualitetsgabet er nul, hvis og kun hvis der er stærk dualitet . Ellers er diskontinuiteten strengt taget positiv, og svag dualitet finder sted [1] . $d^{*}$ $p^{*}$ $p^{*}-d^{*}$

Beskrivelse

I det generelle tilfælde, lad det dobbelte par adskilte lokalt konvekse mellemrum og gives . Så, givet en funktion , kan vi definere det direkte problem som $\left(X,X^{*}\right)$ $\left(Y,Y^{*}\right)$ ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \))$

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

Hvis der er begrænsninger, kan de indbygges i funktionen ved at tilføje en indikatorfunktion på begrænsningerne — . Lad derefter være en forstyrrelsesfunktion sådan, at . Dualitetsgabet er forskellen, som er givet af formlen $f$ $jeg$ $f=f+I$ ${\displaystyle F:X\ gange Y\til \mathbb {R} \cup \{+\infty \))$ $F(x,0)=f(x)$

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

hvor er den konjugerede funktion af begge variabler [2] [3] [4] . $F^{*}$

Alternativer

I beregningsmæssig optimering nævnes ofte et andet "dualitetsgab", som er forskellen i værdier mellem enhver løsning og værdien af en tilladelig, men suboptimal værdi af det direkte problem. Dette alternative "dualitetsgab" kvantificerer uoverensstemmelsen mellem værdien af den nuværende gennemførlige, men suboptimale værdi af det direkte problem og værdien af det dobbelte problem. Værdien af det dobbelte problem er ifølge regularitetsbetingelserne lig med værdien af den konvekse afslapning af det direkte problem. Konveks afslapning er et problem, der opnås ved at erstatte et ikke-konveks sæt af gennemførlige løsninger med dets lukkede konvekse skrog og erstatte en ikke-konveks funktion med dets konvekse lukning , det vil sige med en funktion, hvis epigraf er et lukket konveks skrog af epigraf af den oprindelige objektive funktion af det direkte problem [5] [6 ] [7] [8] [9] [10] [11] [12] [13] .

Noter

↑ Borwein, Zhu, 2005 .
↑ Boţ, Wanka, Grad, 2009 .
↑ Csetnek, 2010 .
↑ Zălinescu, 2002 , s. 106-113.
↑ Ahuja, Magnanti, Orlin, 1993 .
↑ Bertsekas, 1999 .
↑ Bonnans, Gilbert, Lemaréchal, Sagastizábal, 2006 , s. xiv+490.
↑ Hiriart-Urruty, Lemaréchal, 1993 , s. xviii+417.
↑ Hiriart-Urruty, Lemaréchal, 1993 , s. xviii+346.
↑ Lasdon, 2002 , s. xiii+523.
↑ Lemarechal, 2001 , s. 112-156.
↑ Minoux, 1986 , s. xxviii+489.
↑ Shapiro, 1979 , s. xvi+388.

Litteratur

Jonathan Borwein, Qiji Zhu. Teknikker til variationsanalyse. - Springer, 2005. - ISBN 978-1-4419-2026-3 .
Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Dualitet i vektoroptimering. - Springer, 2009. - ISBN 978-3-642-02885-4 .
Ernö Robert Csetnek. Overvinde svigtet af de klassiske generaliserede indvendige punktregularitetsbetingelser i konveks optimering. Anvendelser af dualitetsteorien til forstørrelser af maksimale monotone operatorer. - Logos Verlag Berlin GmbH, 2010. - ISBN 978-3-8325-2503-3 .
Zălinescu C. Konveks analyse i generelle vektorrum. — River Edge, NJ: World Scientific Publishing Co. Inc, 2002. - ISBN 981-238-067-1 .
Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Netværksflow: Teori, algoritmer og applikationer. - Prentice Hall, 1993. - ISBN 0-13-617549-X .
Dimitri P. Bertsekas. ikke-lineær programmering. — 2. - Athena Scientific, 1999. - ISBN 1-886529-00-0 .
J. Fredéric Bonnans, J. Charles Gilbert, Claude Lemaréchal, Claudia A. Sagastizábal. Numerisk optimering: Teoretiske og praktiske aspekter . — Anden reviderede udg. oversættelse af fransk fra 1997. - Berlin: Springer-Verlag, 2006. - (Universitex). — ISBN 3-540-35445-X . - doi : 10.1007/978-3-540-35447-5 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Konvekse analyse- og minimeringsalgoritmer, bind I: Fundamentals. - Berlin: Springer-Verlag, 1993. - V. 305. - (Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]). — ISBN 3-540-56850-6 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. XII. Abstrakt dualitet for praktikere // Konvekse analyse- og minimeringsalgoritmer, bind II: Avanceret teori og bundlemetoder. - Berlin: Springer-Verlag, 1993. - V. 306. - (Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]). — ISBN 3-540-56852-2 . - doi : 10.1007/978-3-662-06409-2_4 .
Leon S Lasdon. Optimeringsteori for store systemer . - Mineola, New York: Dover Publications, Inc., 2002. - ISBN 978-0-486-41999-2 .
Claude Lemarechal. Lagrangian relaxation // Computational combinatorial optimization: Papers from the Spring School afholdt i Schloß Dagstuhl, 15.-19. maj 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. Matematisk programmering: Teori og algoritmer / Egon Balas (fremad); Steven Vajda (oversat) fra (1983 Paris: Dunod). - Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd., 1986. - ISBN 0-471-90170-9 . Bogoversættelse
- Programmeringsmatematik: Teori og algoritmer. — 2. - Paris: Tec & Doc, 2008. - s. xxx+711 s. - ISBN 978-2-7430-1000-3 .
Jeremy F. Shapiro. Matematisk programmering: Strukturer og algoritmer . - New York: Wiley-Interscience [John Wiley & Sons], 1979. - ISBN 0-471-77886-9 .