Konveks analyse

Konveks analyse er en gren af matematik , der er viet til studiet af egenskaberne af konvekse funktioner og konvekse mængder , der ofte har applikationer i konveks programmering , et underområde af optimeringsteori .

Konvekse sæt

Et konveks sæt er et sæt for et eller andet vektorrum X , således at for enhver og [1] $C\subseteq X$ $x,y\in C$ $\lambda \in[0,1]$

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

Konveks funktion

En konveks funktion er enhver udvidet funktion med reel værdi , der opfylder Jensen-uligheden , det vil sige for enhver ${\displaystyle f:X\to \mathbb {R} \cup \{\pm \infty \))$ $x,y\i X$ $\lambda \in[0,1]$

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

[1] .

Tilsvarende er en konveks funktion enhver (udvidet) funktion med reel værdi, således at dens epigraf

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

er et konveks sæt [1] .

Konveks konjugation

Den konvekse konjugation af en udvidet funktion med reel værdi (ikke nødvendigvis konveks) er en funktion , hvor X* er det dobbelte rum af X [2] , således at ${\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\}.

Dobbelt parring

Dobbeltbøjningen af en funktion er bøjningsbøjningen, som normalt skrives som . Dobbelt konjugation er nyttig, når man skal vise, at stærk eller svag dualitet gælder (ved at bruge forstyrrelsesfunktionen ). ${\displaystyle f:X\to \mathbb {R} \cup \{\pm \infty \))$ ${\displaystyle f^{**}:X\to \mathbb {R} \cup \{\pm \infty \))$

For enhver ulighed følger af Fenchels ulighed . For en egenfunktion f = f** hvis og kun hvis f er konveks og lavere semikontinuerlig ved Fenchel-Moro-sætningen [2] [3] . $x\i X$ $f^{**}(x)\leqslant f(x)$

Konveks minimering

Det (direkte) konvekse programmeringsproblem er et formproblem

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

sådan, der er en konveks funktion og er en konveks mængde. ${\displaystyle f:X\to \mathbb {R} \cup \{\pm \infty \))$ $M\subseteq X$

Dobbelt problem

Princippet om dualitet i optimering siger, at optimeringsproblemer kan ses fra to synsvinkler, som et direkte problem eller et dobbelt problem .

Generelt, givet et dobbelt par [4] af adskillelige lokalt konvekse rum og en funktion , kan vi definere det direkte problem som at finde sådan , at Med andre ord er infimum (præcis nedre grænse) af funktionen . $\left(X,X^{*}\right)$ ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \))$ ${\hat {x}}$ $f({\hat {x)))=\inf _{x\in X}f(x).\,$ $f({\hat {x)))$ $f$

Hvis der er begrænsninger, kan de indbygges i funktionen, hvis vi sætter , hvor er indikatorfunktionen . Lad nu (for et andet dobbeltpar ) være en forstyrrelsesfunktion , sådan at [5] . $f$ ${\tilde {f}}=f+I_{\mathrm {begrænsninger} }$ $jeg$ ${\displaystyle F:X\ gange Y\til \mathbb {R} \cup \{+\infty \))$ $\left(Y,Y^{*}\right)$ $F(x,0)={\tilde {f))(x)$

Det dobbelte problem for denne forstyrrelsesfunktion i forhold til det valgte problem er defineret som

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

hvor F* er den konvekse konjugation i begge variable af funktionen F .

Dualitetskløften er forskellen mellem højre og venstre side af uligheden

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

hvor er den konvekse konjugation af begge variabler, og betyder supremum (nøjagtig øvre grænse) [6] [7] [5] [6] . $F^{*}$ $\op$

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

Dette princip er det samme som svag dualitet . Hvis begge sider er ens, siges problemet at opfylde betingelserne for stærk dualitet .

Der er mange betingelser for stærk dualitet, såsom:

F = F** , hvor F er perturbationsfunktionen for de primære og dobbelte problemer, og F** er dobbeltkonjugationen af funktionen F ;
det direkte problem er et lineært programmeringsproblem ;
Slater betingelse for konvekse programmeringsproblemer [8] [9] .

Lagrange-dualitet

For et konveks minimeringsproblem med ulighedsbegrænsninger

\min _{x}f(x)

under betingelser for i = 1, …, m .

g_{i}(x)\leqslant 0

det dobbelte Lagrange-problem er

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

under betingelser for i = 1, …, m ,

u_{i}(x)\geqslant 0

hvor objektivfunktionen L ( x , u ) er den dobbelte lagrangefunktion defineret som følger:

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

Noter

↑ 1 2 3 Rockafellar, 1997 .
↑ 1 2 Zălinescu, 2002 , s. 75-79.
↑ Borwein og Lewis, 2006 , s. 76-77.
↑ Det dobbelte par er en tripel , hvor er et vektorrum over et felt , er mængden af alle lineære afbildninger , og det tredje element er en bilineær form . $\left(X,X^{*},\langle,\rangle \right)$ $x$ $F$ $X^{*}$ $\phi \colon X\to F$ $X^{*}\ gange X\til 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 .

Litteratur

Osipenko K.Yu. Optimering. Del 1. Konveks analyse (forelæsningsnotater). M.: MSU. 57 s.
Osipenko K.Yu. Konveks analyse (kursusprogram og forelæsningsnotater). M.: MSU. 68 s.
Petrov N.N. Konveks analyse (forelæsningsnotater) . Izhevsk: UdmGU, 2009. 160 s.
Zhadan VG optimeringsmetoder. Del I. Introduktion til konveks analyse og optimeringsteori: lærebog. afregning til stud. universiteter i retningen ... "Anvendt matematik og fysik". Moskva: MIPT , 2014. ISBN 978-5-7417-0514-8 . (Del I). 271 s. Udgivelse af 300 stk.
Elementer af konveks og stærkt konveks analyse: en lærebog for studerende fra videregående uddannelsesinstitutioner, der studerer i retning af "Anvendt matematik og fysik" og relaterede områder og specialiteter / E. S. Polovinkin , M. V. Balashov. - 2. udg., rettet. og yderligere - Moskva: Fizmatlit, 2007. - 438 s.; 22 cm - (Phystech lærebog).; ISBN 978-5-9221-0896-6
Protasov V.Yu. Konveks analyse (forelæsningsnotater. Mekhmat MGU, økonomisk flow, 2009). M.: MSU.
Jonathan Borwein, Adrian Lewis. Konveks analyse og ikke-lineær optimering: teori og eksempler. - 2. - Springer, 2006. - ISBN 978-0-387-29570-1 .
Stephen Boyd, Lieven Vandenberghe. Konveks optimering . - Cambridge University Press, 2004. - ISBN 978-0-521-83378-3 .
R. Tyrrell Rockafellar. Konveks Analyse. - Princeton, NJ: Princeton University Press, 1997. - ISBN 978-0-691-01586-6 .
Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Dualitet i vektoroptimering. - Springer, 2009. - ISBN 978-3-642-02885-4 .
Constantin Zalinescu. Konveks analyse i generelle vektorrum. — River Edge, NJ: World Scientific Publishing Co., Inc., 2002. — s. 106–113. - ISBN 981-238-067-1 .
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 .
Jonathan Borwein, Adrian Lewis. Konveks analyse og ikke-lineær optimering: teori og eksempler. - 2. - Springer, 2006. - ISBN 978-0-387-29570-1 .
Hiriart-Urruty J.-B., Lemaréchal C. Fundamentals of convex analysis. - Berlin: Springer-Verlag, 2001. - ISBN 978-3-540-42205-1 .
Ivan Singer. Abstrakt konveks analyse. - New York: John Wiley & Sons, Inc., 1997. - s. xxii+491. - (Canadian Mathematical Society serie af monografier og avancerede tekster). - ISBN 0-471-16015-6 .
Stoer J., Witzgall C. Konveksitet og optimering i endelige dimensioner. - Berlin: Springer, 1970. - Vol. 1. - ISBN 978-0-387-04835-2 .
Kusraev AG, Kutateladze SS Subdifferentialer: teori og anvendelser. - Dordrecht: Kluwer Academic Publishers, 1995. - ISBN 978-94-011-0265-0 .
Kusraev A. G., Kutateladze S. S. Subdifferentialer. Teori og anvendelser. Del 2. - 2., revideret .. - Novosibirsk: Matematisk Instituts Publishing House, 2003. - ISBN 5–86134–116–8.