Kupera analyysi

Konveksi analyysi on matematiikan haara, joka on omistettu konveksien funktioiden ja konveksijoukkojen ominaisuuksien tutkimiselle , jolla on usein sovelluksia konveksissa ohjelmoinnissa , joka on optimointiteorian alakenttä .

Kupera joukko

Konveksi joukko on joukko jollekin vektoriavaruudelle X siten, että mille tahansa ja [1] $C\subseteq X$ $x,y\in C$ $\lambda \in[0,1]$

\lambda x+(1-\lambda )y\in C

Kupera funktio

Konveksi funktio on mikä tahansa laajennettu reaaliarvoinen funktio , joka täyttää Jensenin epäyhtälön , eli mille tahansa ${\displaystyle f:X\to \mathbb {R} \cup \{\pm \infty \))$ $x,y\in X$ $\lambda \in[0,1]$

f(\lambda x+(1-\lambda )y)\leqslant \lambda f(x)+(1-\lambda )f(y)

[1] .

Vastaavasti kupera funktio on mikä tahansa (laajennettu) reaaliarvoinen funktio, jonka epigrafi

{\displaystyle \left\{(x,r)\in X\times \mathbf {R} :f(x)\leqslant r\right\))

on kupera joukko [1] .

Kupera konjugaatio

Laajennetun reaaliarvoisen (ei välttämättä konveksin) funktion konjugaatio on funktio , jossa X* on X :n [2] kaksoisavaruus , jolloin ${\displaystyle f:X\to \mathbb {R} \cup \{\pm \infty \))$ ${\displaystyle f^{*}:X^{*}\to \mathbb {R} \cup \{\pm \infty \))$

f^{*}(x^{*})=\sup _{x\in X}\left\{\langle x^{*},x\rangle -f(x)\right\}.

Kaksinkertainen pariliitos

Funktion kaksoiskonjugaatio on konjugaatiokonjugaatio, joka kirjoitetaan yleensä muodossa . Kaksoiskonjugaatio on hyödyllinen, kun on osoitettava, että vahva tai heikko kaksinaisuus pätee (käyttämällä häiriöfunktiota ). ${\displaystyle f:X\to \mathbb {R} \cup \{\pm \infty \))$ ${\displaystyle f^{**}:X\to \mathbb {R} \cup \{\pm \infty \))$

Sillä mikä tahansa epätasa -arvo seuraa Fenchelin epätasa-arvosta . Ominaisuusfunktiolle f = f** jos ja vain jos f on konveksi ja alempi puolijatkuva Fenchel - Moron lauseen [2] [3] mukaan . $x\in X$ $f^{**}(x)\leqslant f(x)$

Kupera minimointi

(Suora) konveksi ohjelmointiongelma on muodon ongelma

\inf _{x\in M}f(x)

sellainen, joka on kupera funktio ja on kupera joukko. ${\displaystyle f:X\to \mathbb {R} \cup \{\pm \infty \))$ $M\subseteq X$

Kaksoisongelma

Kaksinaisuuden periaate optimoinnissa sanoo, että optimointiongelmia voidaan tarkastella kahdesta näkökulmasta, joko suorana ongelmana tai kaksoisongelmana .

Yleisesti ottaen, kun otetaan huomioon erotettavien paikallisesti konveksiavaruuksien kaksoispari [4], ja funktio , voidaan määritellä suora ongelma sellaisen löytämiseksi, että 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ä [5] . $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)$

Tämän häiriöfunktion kaksoisongelma suhteessa valittuun ongelmaan määritellään seuraavasti

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

jossa F* on funktion F kummankin muuttujan kupera konjugaatio .

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 konjugaatio ja tarkoittaa supremumia (tarkka yläraja) [6] [7] [5] [6] . $F^{*}$ $\ylös$

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

Tämä periaate on sama kuin heikko kaksinaisuus . Jos molemmat osapuolet ovat tasa-arvoisia, ongelman sanotaan täyttävän vahvan kaksinaisuuden ehdot .

Vahvalle kaksinaisuudesta on monia ehtoja, kuten:

F = F** , jossa F on primaali- ja duaaliongelmien häiriöfunktio ja F** on funktion F kaksoiskonjugaatio ;
suora ongelma on lineaarinen ohjelmointiongelma ;
Hitaampi ehto kuperalle ohjelmointitehtävälle [ 8 ] [9] .

Lagrangen kaksinaisuus

Kuperalle minimointiongelmalle epäyhtälörajoitteilla

{\näyttötyyli \min _{x}f(x)}

olosuhteissa i = 1, … , m .

g_{i}(x)\leqslant 0

Lagrangen kaksoisongelma on

\sup _{u}\inf _{x}L(x,u)

olosuhteissa i = 1, … , m ,

u_{i}(x)\geqslant 0

jossa tavoitefunktio L ( x , u ) on kaksois-Lagrange-funktio, joka määritellään seuraavasti:

L(x,u)=f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)

Muistiinpanot

↑ 1 2 3 Rockafellar, 1997 .
↑ 1 2 Zălinescu, 2002 , s. 75–79.
↑ Borwein ja Lewis, 2006 , s. 76–77.
↑ 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 .
↑ 12. Csetnek , 2010 .
↑ Zălinescu, 2002 , s. 106–113.
↑ Borwein, Lewis, 2006 .
↑ Boyd, Vandenberghe, 2004 .

Kirjallisuus

Osipenko K.Yu. Optimointi. Osa 1. Kupera analyysi (luentomuistiinpanot). M.: MGU. 57 s.
Osipenko K.Yu. Kupera analyysi (kurssiohjelma ja luentomuistiinpanot). M.: MGU. 68 s.
Petrov N.N. Kupera analyysi (luentomuistiinpanot) . Izhevsk: UdmGU, 2009. 160 s.
Zhadan VG Optimointimenetelmät. Osa I. Johdatus kuperaan analyysiin ja optimointiteoriaan: oppikirja. ratkaisu nastalle. yliopistot suuntaan ... "Soveltava matematiikka ja fysiikka". Moskova: MIPT , 2014. ISBN 978-5-7417-0514-8 . (Osa I). 271 s. Julkaisu 300 kpl.
Konveksin ja vahvasti kuperan analyysin elementit: oppikirja "Soveltavan matematiikan ja fysiikan" ja siihen liittyvien alojen ja erikoisalojen opiskelijoille / E. S. Polovinkin , M. V. Balashov. - 2. painos, korjattu. ja ylimääräistä - Moskova: Fizmatlit, 2007. - 438 s.; 22 cm - (fysiikan oppikirja).; ISBN 978-5-9221-0896-6
Protasov V. Yu. Kupera analyysi (luentomuistiinpanot. Mekhmat MGU, talousvirta, 2009). M.: MGU.
Jonathan Borwein, Adrian Lewis. Kupera analyysi ja epälineaarinen optimointi: teoria ja esimerkit. - 2. - Springer, 2006. - ISBN 978-0-387-29570-1 .
Stephen Boyd, Lieven Vandenberghe. Kupera optimointi . - Cambridge University Press, 2004. - ISBN 978-0-521-83378-3 .
R. Tyrrell Rockafellar. Kupera analyysi. - Princeton, NJ: Princeton University Press, 1997. - ISBN 978-0-691-01586-6 .
Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Kaksinaisuus vektorioptimoinnissa. - Springer, 2009. - ISBN 978-3-642-02885-4 .
Constantin Zalinescu. Konveksi analyysi yleisissä vektoriavaruuksissa. — River Edge, NJ: World Scientific Publishing Co., Inc., 2002. — s. 106–113. - ISBN 981-238-067-1 .
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 .
Jonathan Borwein, Adrian Lewis. Kupera analyysi ja epälineaarinen optimointi: teoria ja esimerkit. - 2. - Springer, 2006. - ISBN 978-0-387-29570-1 .
Hiriart-Urruty J.-B., Lemaréchal C. Convex- analyysin perusteet. - Berliini: Springer-Verlag, 2001. - ISBN 978-3-540-42205-1 .
Ivan Singer. Abstrakti kupera analyysi. - New York: John Wiley & Sons, Inc., 1997. - s. xxii+491. - (Canadian Mathematical Societyn monografioiden ja edistyneiden tekstien sarja). - ISBN 0-471-16015-6 .
Stoer J., Witzgall C. Konveksiteetti ja optimointi äärellisissä ulottuvuuksissa. - Berlin: Springer, 1970. - Vol. 1. - ISBN 978-0-387-04835-2 .
Kusraev AG, Kutateladze SS :n aladifferentiaalit: teoria ja sovellukset. - Dordrecht: Kluwer Academic Publishers, 1995. - ISBN 978-94-011-0265-0 .
Kusraev A. G., Kutateladze S. S. Subdifferentiaalit. Teoria ja sovellukset. Osa 2. - 2., tarkistettu .. - Novosibirsk: Matematiikan instituutin kustantamo, 2003. - ISBN 5-86134-116-8.