Duality Gap

Kaksinaisuusaukko on ero suoran ja kaksoisratkaisun välillä . Jos on kaksoisongelman optimaalinen arvo ja suoran ongelman optimaalinen arvo, niin kaksinaisuusero on . Tämä arvo on aina suurempi tai yhtä suuri kuin nolla (minimointiongelmia varten). Kaksinaisuusero on nolla, jos ja vain jos on vahvaa kaksinaisuutta . Muuten epäjatkuvuus on ehdottomasti positiivinen ja tapahtuu heikkoa kaksinaisuutta [1] . $d^{*}$ $p^{*}$ $p^{*}-d^{*}$

Kuvaus

Yleisessä tapauksessa olkoon eroteltujen paikallisesti kuperaavaruuksien kaksoispari ja annetaan . Sitten, kun funktio on annettu , voimme määritellä suoran ongelman muodossa $\left(X,X^{*}\right)$ $\left(Y,Y^{*}\right)$ ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \))$

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

Jos rajoituksia on, ne voidaan rakentaa funktioon lisäämällä rajoituksiin indikaattorifunktio . Sitten anna olla häiriöfunktio sellainen, että . Kaksinaisuusaukko on ero, joka saadaan kaavalla $f$ $minä$ $f=f+I$ ${\displaystyle 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^ {*})]

missä on molempien muuttujien konjugaattifunktio [2] [3] [4] . $F^{*}$

Vaihtoehdot

Laskennallisessa optimoinnissa mainitaan usein toinen "kaksoisaukko", joka on minkä tahansa ratkaisun ja suoran ongelman hyväksyttävän, mutta alioptimaalisen arvon välinen ero. Tämä vaihtoehtoinen "kaksoisero" kvantifioi eron suoran ongelman nykyisen mahdollisen mutta alioptimaalisen arvon ja kaksoisongelman arvon välillä. Duaalitehtävän arvo säännöllisyysehtojen mukaan on yhtä suuri kuin suoran ongelman konveksin relaksaation arvo. Konveksi relaksaatio on ongelma, joka saadaan korvaamalla ei-kupera joukko mahdollisia ratkaisuja sen suljetulla kuperalla rungolla ja korvaamalla ei-kupera funktio sen kuperalla sulkemisella eli funktiolla, jonka epigrafi on suljettu kupera runko suoran ongelman alkuperäisen tavoitefunktion epigrafi [5] [6 ] [7] [8] [9] [10] [11] [12] [13] .

Muistiinpanot

↑ 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.

Kirjallisuus

Jonathan Borwein, Qiji Zhu. Variaatioanalyysin tekniikat. - Springer, 2005. - ISBN 978-1-4419-2026-3 .
Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Kaksinaisuus vektorioptimoinnissa. - Springer, 2009. - ISBN 978-3-642-02885-4 .
Ernö Robert Csetnek. Klassisten yleisten sisäpisteen säännönmukaisuusehtojen epäonnistumisen voittaminen kuperassa optimoinnissa. Kaksinaisuusteorian sovellukset maksimaalisten monotonioperaattoreiden suurennoksissa. - Logos Verlag Berlin GmbH, 2010. - ISBN 978-3-8325-2503-3 .
Zălinescu C. Konveksi analyysi yleisissä vektoriavaruuksissa. — River Edge, NJ: World Scientific Publishing Co. Inc, 2002. - ISBN 981-238-067-1 .
Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Verkkovirrat: teoria, algoritmit ja sovellukset. - Prentice Hall, 1993. - ISBN 0-13-617549-X .
Dimitri P. Bertsekas. epälineaarinen ohjelmointi. – 2. - Athena Scientific, 1999. - ISBN 1-886529-00-0 .
J. Fredéric Bonnans, J. Charles Gilbert, Claude Lemaréchal, Claudia A. Sagastizábal. Numeerinen optimointi: Teoreettiset ja käytännön näkökohdat . — Toinen tarkistettu painos. 1997 ranskan kielen käännöksestä. - Berliini: Springer-Verlag, 2006. - (Universitex). — ISBN 3-540-35445-X . - doi : 10.1007/978-3-540-35447-5 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Kupera analyysi ja minimointialgoritmit, osa I: Fundamentals. - Berlin: Springer-Verlag, 1993. - V. 305. - (Grundlehren der Mathematischen Wissenschaften [Matemaattisten tieteiden perusperiaatteet]). — ISBN 3-540-56850-6 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. XII. Abstract Duality for Practitioners // Konveksianalyysi- ja minimointialgoritmit, osa II: Kehittynyt teoria ja nippumenetelmät. - Berlin: Springer-Verlag, 1993. - V. 306. - (Grundlehren der Mathematischen Wissenschaften [Matemaattisten tieteiden perusperiaatteet]). — ISBN 3-540-56852-2 . - doi : 10.1007/978-3-662-06409-2_4 .
Leon S Lasdon. Optimointiteoria suurille järjestelmille . - Mineola, New York: Dover Publications, Inc., 2002. - ISBN 978-0-486-41999-2 .
Claude Lemarechal. Lagrangian rentoutuminen // Laskennallinen kombinatorinen optimointi: Papers from the Spring School, joka pidettiin Schloß Dagstuhlissa, 15.–19. toukokuuta 2000 / Michael Jünger, Denis Naddef. - Berlin: Springer-Verlag, 2001. - T. 2241. - (Luentomuistiinpanot tietojenkäsittelytieteessä (LNCS)). — ISBN 3-540-42877-1 . - doi : 10.1007/3-540-45586-8_4 .
Michel Minoux. Matemaattinen ohjelmointi: Teoria ja algoritmit / Egon Balas (eteenpäin); Steven Vajda (trans) elokuvasta (1983 Paris: Dunod). - Chichester: Wiley-Interscience-julkaisu. John Wiley & Sons, Ltd., 1986. - ISBN 0-471-90170-9 . Kirjan käännös
- Ohjelmoinnin matematiikka: teoria ja algoritmit. – 2. - Paris: Tec & Doc, 2008. - s. xxx+711 s. - ISBN 978-2-7430-1000-3 .
Jeremy F. Shapiro. Matemaattinen ohjelmointi: rakenteet ja algoritmit . - New York: Wiley-Interscience [John Wiley & Sons], 1979. - ISBN 0-471-77886-9 .