Analiza convexă

Analiza convexă este o ramură a matematicii dedicată studiului proprietăților funcțiilor convexe și mulțimilor convexe , având adesea aplicații în programarea convexă , un subdomeniu al teoriei optimizării .

Mulțimi convexe

O mulțime convexă este o mulțime pentru un spațiu vectorial X astfel încât pentru orice și [1] $C\subseteq X$ $x,y\în C$ $\lambda \in[0,1]$

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

Funcția convexă

O funcție convexă este orice funcție extinsă cu valori reale care satisface inegalitatea Jensen , adică pentru orice și orice $f:X\la \mathbb {R} \cup \{\pm \infty \)$ $x,y\în X$ $\lambda \in[0,1]$

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

[1] .

În mod echivalent, o funcție convexă este orice funcție cu valoare reală (extinsă), astfel încât epigraful său

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

este o mulțime convexă [1] .

Conjugarea convexă

Conjugarea convexă a unei funcții extinse cu valoare reală (nu neapărat convexă) este o funcție , unde X* este spațiul dual al lui X [2] , astfel încât $f:X\la \mathbb {R} \cup \{\pm \infty \)$ $f^{*}:X^{*}\to \mathbb {R} \cup \{\pm \infty \)$

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

Împerecherea dublă

Conjugarea dublă a unei funcții este conjugarea de conjugare, care se scrie de obicei ca . Conjugarea dublă este utilă atunci când trebuie să arăți că dualitatea puternică sau slabă este valabilă (folosind funcția de perturbare ). $f:X\la \mathbb {R} \cup \{\pm \infty \)$ $f^{**}:X\to \mathbb {R} \cup \{\pm \infty \)$

Căci orice inegalitate rezultă din inegalitatea lui Fenchel . Pentru o funcție proprie f = f** dacă și numai dacă f este convex și semicontinuu inferior după teorema Fenchel-Moro [2] [3] . $x\în X$ $f^{**}(x)\leqslant f(x)$

Minimizare convexă

Problema de programare (directă) convexă este o problemă de formă

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

astfel încât este o funcție convexă și este o mulțime convexă. $f:X\la \mathbb {R} \cup \{\pm \infty \)$ $M\subseteq X$

Problemă dublă

Principiul dualității în optimizare afirmă că problemele de optimizare pot fi privite din două puncte de vedere, ca o problemă directă sau o problemă duală .

În general, având în vedere o pereche duală [4] de spații separabile local convexe și o funcție , putem defini problema directă ca găsirea astfel încât , cu alte cuvinte, este infima (limita inferioară exactă) a funcției . $\left(X,X^{*}\right)$ $f:X\la \mathbb {R} \cup \{+\infty \)$ ${\hat {x}}$ $f({\hat {x)})=\inf _{x\in X}f(x).\,$ $f({\hat {x}))$ $f$

Dacă există restricții, acestea pot fi încorporate în funcție dacă punem , unde este funcția indicator . Fie acum (pentru o altă pereche duală ) o funcție de perturbare astfel încât [5] . $f$ ${\tilde {f}}=f+I_{\mathrm {constrângeri} }$ $eu$ $F:X\times Y\to \mathbb {R} \cup \{+\infty \)$ $\left(Y,Y^{*}\right)$ $F(x,0)={\tilde {f))(x)$

Problema duală pentru această funcție de perturbare în raport cu problema aleasă este definită ca

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

unde F* este conjugarea convexă în ambele variabile ale funcției F .

Decalajul de dualitate este diferența dintre partea dreaptă și stângă a inegalității

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

unde este conjugarea convexă a ambelor variabile și înseamnă supremul (limită superioară exactă) [6] [7] [5] [6] . $F^{*}$ $\sus$

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

Acest principiu este același cu dualitatea slabă . Dacă ambele părți sunt egale, se spune că problema îndeplinește condițiile dualității puternice .

Există multe condiții pentru o dualitate puternică, cum ar fi:

F = F** , unde F este funcția de perturbare pentru problemele primale și duale, iar F** este dubla conjugare a funcției F ;
problema directă este o problemă de programare liniară ;
Condiție Slater pentru probleme de programare convexă [8] [9] .

Dualitate Lagrange

Pentru o problemă de minimizare convexă cu constrângeri de inegalitate

\min _{x}f(x)

în condiții pentru i = 1, …, m .

g_{i}(x)\leqslant 0

problema duală Lagrange este

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

în condițiile pentru i = 1, …, m ,

u_{i}(x)\geqslant 0

unde funcția obiectiv L ( x , u ) este funcția Lagrange duală definită după cum urmează:

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

Note

↑ 1 2 3 Rockafellar, 1997 .
↑ 1 2 Zălinescu, 2002 , p. 75–79.
↑ Borwein și Lewis, 2006 , p. 76–77.
↑ Perechea duală este un triplu , unde este un spațiu vectorial peste un câmp , este mulțimea tuturor mapărilor liniare , iar al treilea element este o formă biliniară . $\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 , p. 106–113.
↑ Borwein, Lewis, 2006 .
↑ Boyd, Vandenberghe, 2004 .

Literatură

Osipenko K.Yu. Optimizare. Partea 1. Analiza convexă (note de curs). M.: MGU. 57 p.
Osipenko K.Yu. Analiză convexă (programul cursului și note de curs). M.: MGU. 68 p.
Petrov N.N. Analiză convexă (note de curs) . Izhevsk: UdmGU, 2009. 160 p.
Metode de optimizare Zhadan VG . Partea I. Introducere în analiza convexă și teoria optimizării: manual. decontare pentru stud. universități în direcția ... „Matematică și Fizică Aplicată”. Moscova: MIPT , 2014. ISBN 978-5-7417-0514-8 . (Partea I). 271 p. Lansare de 300 buc.
Elemente de analiză convexă și puternic convexă: un manual pentru studenții instituțiilor de învățământ superior care studiază în direcția „Matematică aplicată și fizică” și domenii și specialități conexe / E. S. Polovinkin , M. V. Balashov. - Ed. a II-a, corectată. si suplimentare - Moscova: Fizmatlit, 2007. - 438 p.; 22 cm. - (Manual Phystech).; ISBN 978-5-9221-0896-6
Protasov V.Yu. Analiză convexă (note de curs. Mekhmat MGU, flux economic, 2009). M.: MGU.
Jonathan Borwein, Adrian Lewis. Analiza convexă și optimizarea neliniară: teorie și exemple. - 2. - Springer, 2006. - ISBN 978-0-387-29570-1 .
Stephen Boyd, Lieven Vandenberghe. Optimizare convexă . - Cambridge University Press, 2004. - ISBN 978-0-521-83378-3 .
R. Tyrrell Rockafellar. Analiza convexă. - Princeton, NJ: Princeton University Press, 1997. - ISBN 978-0-691-01586-6 .
Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Dualitate în optimizarea vectorială. - Springer, 2009. - ISBN 978-3-642-02885-4 .
Constantin Zalinescu. Analiza convexă în spații vectoriale generale. — River Edge, NJ: World Scientific Publishing Co., Inc., 2002. — pp. 106–113. - ISBN 981-238-067-1 .
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 .
Jonathan Borwein, Adrian Lewis. Analiza convexă și optimizarea neliniară: teorie și exemple. - 2. - Springer, 2006. - ISBN 978-0-387-29570-1 .
Hiriart-Urruty J.-B., Lemaréchal C. Fundamentele analizei convexe. - Berlin: Springer-Verlag, 2001. - ISBN 978-3-540-42205-1 .
Ivan Singer. Analiză abstractă convexă. - New York: John Wiley & Sons, Inc., 1997. - p. xxii+491. - (serie de monografii și texte avansate ale Societății de Matematică din Canada). - ISBN 0-471-16015-6 .
Stoer J., Witzgall C. Convexitate și optimizare în dimensiuni finite. - Berlin: Springer, 1970. - Vol. 1. - ISBN 978-0-387-04835-2 .
Kusraev AG, Kutateladze SS Subdiferențiale: Teorie și aplicații. - Dordrecht: Kluwer Academic Publishers, 1995. - ISBN 978-94-011-0265-0 .
Kusraev A. G., Kutateladze S. S. Subdiferențiale. Teorie și aplicații. Partea 2. - a 2-a, revizuită .. - Novosibirsk: Editura Institutului de Matematică, 2003. - ISBN 5–86134–116–8.