Kaksinaisuus (optimointi)

Kaksinaisuus eli kaksinaisuuden periaate on periaate, jolla optimointiongelmia voidaan tarkastella kahdesta näkökulmasta, joko suorana ongelmana tai kaksoisongelmana . Kaksoistehtävän ratkaisu antaa suoran ongelman alarajan (minimoitaessa) [1] . Yleisessä tapauksessa suorien ja kaksoisongelmien optimaalisten ratkaisujen tavoitefunktioiden arvot eivät kuitenkaan välttämättä täsmää. Näiden arvojen eroa, jos se havaitaan, kutsutaan kaksinaisuusrakoksi . Konveksin ohjelmoinnin ongelmissa duaalisuusrako on yhtä suuri kuin nolla , kun rajoitusten säännöllisyyden ehdot täyttyvät .

Kaksoisongelma

Yleensä termi "kaksoisongelma" tarkoittaa Lagrangin kaksoisongelmaa , mutta käytetään myös muita kaksoisongelmia, kuten Wolfen kaksoisongelma ja Fenchelin kaksoisongelma . Kaksois-Lagrange-tehtävä saadaan generoimalla Lagrangen funktio, käyttämällä ei-negatiivisia Lagrangen kertoimia rajoitusten lisäämiseksi tavoitefunktioon ja minimoimalla Lagrangen tiettyjen suoran ongelman muuttujien suhteen. Tällainen ratkaisu antaa suoran ongelman muuttujat Lagrange-kertoimien funktioina, joita kutsutaan kaksoismuuttujiksi, niin että uudeksi ongelmaksi muodostuu tavoitefunktion maksimoimisen ongelma kaksoismuuttujien suhteen kaksoismuuttujien generoitujen rajoitusten alaisena ( ainakin ei-negatiivisuus).

Yleisesti ottaen, kun otetaan huomioon erotettavan paikallisen konveksin avaruuden ja funktion kaksoispari [2] , voimme määritellä suoran ongelman löydökseksi , joka toisin sanoen on funktion infimum (tarkka alaraja). . $\left(X,X^{*}\right)$ ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \))$ ${\hattu {x}}$ $f({\hat {x)))=\inf _{x\in X}f(x).\,$ $f({\hat {x)))$ $f$

Jos rajoituksia on, ne voidaan rakentaa funktioon , jos laitamme , missä on indikaattorifunktio . Olkoon nyt (toiselle kaksoisparille ) sellainen häiriöfunktio , että [3] . $f$ ${\tilde {f}}=f+I_{\mathrm {constraints} }$ $minä$ ${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \))$ $\left(Y,Y^{*}\right)$ $F(x,0)={\tilde {f))(x)$

Kaksinaisuusero on ero epätasa-arvon oikean ja vasemman puolen välillä

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

missä on molempien muuttujien konjugaattifunktio ja tarkoittaa supremumia (tarkka yläraja) [3] [4] [5] . $F^{*}$ $\ylös$

Duality Gap

Kaksinaisuusaukko on ero kaikkien alkuperäisen ongelman ratkaisujen arvojen ja kaksoisongelman ratkaisujen arvojen välillä. Jos on kaksoisongelman optimaalinen arvo ja suoran ongelman optimaalinen arvo, kaksinaisuusero on . Tämä arvo on aina suurempi tai yhtä suuri kuin 0. Kaksinaisuusero on nolla, jos ja vain jos kaksinaisuus on vahvaa . Muuten epäjatkuvuus on ehdottomasti positiivinen ja tapahtuu heikkoa kaksinaisuutta [6] . $d^{*}$ $p^{*}$ $p^{*}-d^{*}$

Numeerisissa optimointitehtävissä käytetään usein toista "kaksoisvälieroa", joka on yhtä suuri kuin minkä tahansa kaksoisratkaisun ja suoran ongelman hyväksyttävän, mutta ei paikallisesti optimaalisen iteraation arvon välinen ero. Vaihtoehtoinen "kaksoisero" ilmaisee eron alkuperäisen ongelman nykyisen mahdollisen, mutta ei paikallisesti optimaalisen ratkaisun arvon ja kaksoisongelman arvon välillä. Duaalitehtävän arvo on rajoitusten säännöllisyyden ehdolla yhtä suuri kuin suoran ongelman konveksin heikennyksen arvo , jossa konveksi heikkeneminen syntyy, kun ei-kupera toteutettavissa olevien ratkaisujen joukko korvataan suljetuilla ratkaisuilla. kupera runko ja ei-kupera funktio korvaamalla sen konveksilla sulkemisella , eli funktiolla, jonka epigrafi on suljettu konveksi, sulkemalla suoran ongelman alkuperäinen tavoitefunktio [7] [8] [9] [10] [11 ] [12] [13] [14] [15] [16] [17] .

Lineaarinen tapaus

Lineaariset ohjelmointiongelmat ovat optimointiongelmia , joissa tavoitefunktio ja rajoitteet ovat lineaarisia. Suorassa tehtävässä tavoitefunktio on n muuttujan lineaarinen yhdistelmä . On m rajoitusta, joista jokainen rajoittaa n muuttujan lineaarista yhdistelmää ylhäältä. Tavoitteena on maksimoida tavoitefunktion arvo rajoituksin. Ratkaisu on n arvon vektori (luettelo), joka antaa tavoitefunktion maksimiarvon.

Kaksoistehtävässä tavoitefunktio on lineaarinen yhdistelmä m arvoista, jotka ovat alkuongelman m rajoitteen oikeat puolet . On n kaksoisrajoitetta, joista jokainen rajoittaa m kaksoismuuttujan lineaarista yhdistelmää alhaalta.

Alku- ja kaksoisongelmien välinen suhde

Lineaarisessa tapauksessa suorassa ongelmassa paikallisen optimin jokaisesta pisteestä, joka täyttää kaikki rajoitukset, on suunta tai aliavaruus , ja liike tähän suuntaan lisää tavoitefunktiota. Liikkeen mihin tahansa sellaiseen suuntaan sanotaan vähentävän kuilua toteuttamiskelpoisen ratkaisun (tai toteuttamiskelpoisen suunnitelman ) ja yhden rajoitteen välillä. Virheellinen mahdollinen ratkaisu on ratkaisu, joka rikkoo yhtä tai useampaa rajoitusta.

Duaalitehtävässä duaalivektorin elementit kerrotaan sarakkeilla, jotka vastaavat alkutehtävän rajoituksia. Duaalivektorin häiriö duaalitehtävässä vastaa alkuongelman ylärajan tarkistamista. Duaalitehtävää ratkaistaessa etsitään pienintä ylärajaa, eli duaalivektori muuttuu siten, että se pienentää mahdollisen ratkaisun ja todellisen optimin välistä kuilua.

Lisätietoja primaalien ja kaksoisongelmien välisestä yhteydestä on artikkelissa " Lineaarisen ohjelmoinnin kaksoisongelmat ".

Taloudellinen tulkinta

Jos ymmärrämme primaarisen lineaarisen ohjelmoinnin ongelmamme klassisena "resurssien allokointi" -ongelmana, sen kaksoisongelma voidaan tulkita " resurssien estimointi " -ongelmaksi .

Epälineaarinen tapaus

Epälineaarisessa ohjelmoinnissa rajoitukset eivät välttämättä ole lineaarisia. Monet lineaarisen tapauksen periaatteet ovat kuitenkin voimassa.

Varmistaakseen, että epälineaarisen ongelman globaali maksimi voidaan määrittää helposti, ongelman kuvaus edellyttää usein, että funktiot ovat kuperia ja niillä on kompakteja alempia tasoja (eli joukkoja, joissa funktio saa arvon, joka on pienempi kuin jokin taso). .

Tämä on Karush-Kuhn-Tucker-ehto . Ne osoittivat tarvittavat ehdot epälineaaristen ongelmien paikallisen optimin määrittämiseksi. On olemassa lisäehtoja (rajoitusten säännöllisyysehto), jotka ovat välttämättömiä optimaalisen ratkaisun suunnan määrittämiseksi. Tässä optimaalinen ratkaisu on yksi paikallisista optimeista, joka ei välttämättä ole globaali.

Tiukka Lagrangen periaate: Lagrangen kaksinaisuus

Jos epälineaarinen ohjelmointitehtävä annetaan vakiomuodossa

minimoida	$f_{0}(x)$
olosuhteissa	${\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\))$

kun verkkotunnuksen sisäpuoli ei ole tyhjä, Lagrange-funktio määritellään seuraavasti ${\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)+\ summa _{i=1}^{p}\nu _{i}h_{i}(x).

Vektoreita ja kutsutaan ongelmaan liittyviksi Lagrange-kertoimien kaksoismuuttujiksi tai vektoreiksi. Kaksois Lagrange -funktio määritellään seuraavasti $\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)+\sum _{i=1}^ {p}\nu _{i}h_{i}(x)\oikea).

Duaalifunktio g on kovera, vaikka alkutehtävä ei olisi konveksi, koska se on affiinisten funktioiden pisteittäinen infimumi. Kaksoisfunktio antaa alemmat rajat alkuperäisen ongelman optimiarvolle . Kaikille ja kaikille, joita meillä on . $p^{*}$ $\lambda \geqslant 0$ $\nu$ $g(\lambda ,\nu )\leqslant p^{*}$

Jos rajoitteen säännönmukaisuusehdot , kuten Slaterin ehto , täyttyvät ja alkuperäinen tehtävä on kupera, niin meillä on tiukka kaksinaisuus , eli . $d^{*}=\max _{\lambda \geqslant 0,\nu }g(\lambda ,\nu )=\inf f_{0}=p^{*}$

Kupera ongelmat

Kuperalle minimointiongelmalle, jossa on rajoituksia – epäyhtälöjä,

minimoida	$f(x)$
olosuhteissa	$g_{i}(x)\leqslant 0,\quad i=1,\dots ,m$

Lagrangin kaksoisongelma on

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

jossa tavoitefunktio on kaksois-Lagrange-funktio. Jos funktioiden ja tiedetään olevan jatkuvasti differentioituvia, niin infimum on kohdissa, joissa gradientti on nolla. Tehtävä $f$ ${\displaystyle g_{1},\cdots ,g_{m))$

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

kutsutaan dual Wolfe -ongelmaksi. Tämä tehtävä voi olla laskennallisesti vaikea, koska tavoitefunktio ei ole konveksi koordinaateissa . Lisäksi rajoitus on yleensä epälineaarinen, joten dual Wolfe -tehtävä on yleensä ei-kupera optimointitehtävä. Joka tapauksessa heikko kaksinaisuus on olemassa [18] . ${\näyttötyyli (u,x)}$ $\nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)$

Historia

George Danzigin mukaan kaksinaisuuslause lineaarista optimointia varten esitettiin John von Neumannin arveluna heti Danzigin esiteltyä lineaarisen ohjelmointiongelman. Von Neumann huomasi käyttäneensä tietoa peliteoriastaan ja ehdotti, että kahden hengen nollasummamatriisipeli vastaa lineaarista ohjelmointiongelmaa. Albert Tucker ja hänen ryhmänsä julkaisivat ensimmäisen tiukan todisteen tästä tosiasiasta vuonna 1948 [19] .

Katso myös

Kaksinaisuuden periaate
Vaimennus (likimääräinen)

Muistiinpanot

↑ Boyd, Vandenberghe, 2004 .
↑ Duaalipari on kolmio , jossa on vektoriavaruus kentän päällä , on kaikkien lineaaristen kuvausten joukko ja kolmas elementti on bilineaarinen muoto . $\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 , s. 106–113.
↑ Borwein, Zhu, 2005 .
↑ Ahuja, Magnanti, Orlin, 1993 .
↑ Bertsekas, Nedic, Ozdaglar, 2003 .
↑ Bertsekas, 1999 .
↑ Bertsekas, 2009 .
↑ 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.
↑ Geoffrion, 1971 , s. 1–37.
↑ Nering ja Tucker 1993 , s. esipuhe Danzig.

Kirjallisuus

Kirjat

Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Kupera analyysi ja minimointialgoritmit. Osa I: Perusteet. - Berliini: Springer-Verlag, 1993. - T. 305. - S. xviii + 417. — (Grundlehren der Mathematischen Wissenschaften [Matematiikan tieteiden perusperiaatteet]). — ISBN 3-540-56850-6 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. 14 Duality for Practitioners // Konveksianalyysi- ja minimointialgoritmit. Osa II: Kehittynyt teoria ja nippumenetelmät. - Berliini: Springer-Verlag, 1993. - T. 306. - S. xviii + 346. — (Grundlehren der Mathematischen Wissenschaften [Matematiikan tieteiden perusperiaatteet]). — ISBN 3-540-56852-2 .
Leon S Lasdon. Optimointiteoria suurille järjestelmille . - Mineola, New York: Dover Publications, Inc., 2002. - s. xiii+523. — 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. - 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. Matemaattinen ohjelmointi: teoria ja algoritmit. - Chichester: Wiley-Interscience-julkaisu. John Wiley & Sons, Ltd., 1986. - s. xxviii+489. — ISBN 0-471-90170-9 .
- M. Minu. Matemaattinen ohjelmointi. Teoria ja algoritmit.
Evar D. Nering, Albert W. Tucker. Lineaarinen ohjelmointi ja siihen liittyvät ongelmat . - Boston, MA: Academic Press, 1993. - ISBN 978-0-12-515440-6 .
Stephen P. Boyd, Lieven Vandenberghe. Kupera optimointi . - Cambridge University Press, 2004. - ISBN 978-0-521-83378-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 .
Constantin Zalinescu. Konveksi analyysi yleisissä vektoriavaruuksissa. — 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. Verkkovirrat: teoria, algoritmit ja sovellukset. - Prentice Hall, 1993. - ISBN 0-13-617549-X .
Dimitri Bertsekas, Angelia Nedic, Asuman Ozdaglar. Kupera analyysi ja optimointi. - Athena Scientific, 2003. - ISBN 1-886529-45-0 .
Dimitri P. Bertsekas. epälineaarinen ohjelmointi. – 2. - Athena Scientific, 1999. - ISBN 1-886529-00-0 .
Dimitri P. Bertsekas. Kupera optimointiteoria. - Athena Scientific, 2009. - ISBN 978-1-886529-31-1 .
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. käännös vuodelta 1997. - Berlin: Springer-Verlag, 2006. - s. xiv+490. — (Yliopistoteksti). — ISBN 3-540-35445-X . - doi : 10.1007/978-3-540-35447-5 .
Jeremy F. Shapiro. Matemaattinen ohjelmointi: rakenteet ja algoritmit . - New York: Wiley-Interscience [John Wiley & Sons], 1979. - s. xvi + 388. — ISBN 0-471-77886-9 .
Jonathan Borwein, Qiji Zhu. Variaatioanalyysin tekniikat. - Springer, 2005. - ISBN 978-1-4419-2026-3 .

Artikkelit

Lineaarisen ohjelmoinnin kaksinaisuus Gary D. Knott
Arthur M. Geoffrion. Kaksinaisuus epälineaarisessa ohjelmoinnissa: yksinkertaistettu sovelluslähtöinen kehitys // SIAM Review. - 1971. - T. 13 , no. 1 . - doi : 10.1137/1013001 . — .

Lue lisää

William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver. kombinatorinen optimointi. – 1. - John Wiley & Sons, 1997. - ISBN 0-471-55894-X .
Xugang Ye, Shih-Ping Han, Anhua Lin. Huomautus Primal-Dual- ja A*-algoritmien välisestä yhteydestä // International Journal of Operations Research and Information Systems. - 2010. - Vol. 1 , numero. 1 . — s. 73–85 .
George B. Dantzig. Lineaarinen ohjelmointi ja laajennukset. — Princeton, NJ: Princeton University Press, 1963.
Eugene Lawler. 4.5. Max-Flow Min-Cut -lauseen kombinatoriset implikaatiot, 4.6. Max-Flow Min-Cut -lauseen lineaarinen ohjelmointitulkinta // Kombinatorinen optimointi: verkot ja matroidit. - Dover, 2001. - S. 117-120. - ISBN 0-486-41453-1 .
Andrzej Piotr Ruszczyński. epälineaarinen optimointi. — Princeton, NJ: Princeton University Press , 2006. — s. xii+454. - ISBN 978-0691119151 .
Christos H. Papadimitriou, Kenneth Steiglitz. Kombinatorinen optimointi: Algoritmit ja monimutkaisuus. - Dover, 1998. - ISBN 0-486-40258-4 .
Krzysztof C. Kiwiel, Torbjörn Larsson, P. O. Lindberg. Lagrangin rentoutuminen ballstep-alagradienttimenetelmillä // Operaatiotutkimuksen matematiikka. - 2007. - elokuu ( nide 32 , numero 3 ). — S. 669–686 . - doi : 10.1287/moor.1070.0261 .