Konvex analys

Konvex analys är en gren av matematiken som ägnas åt studier av egenskaperna hos konvexa funktioner och konvexa mängder , ofta med tillämpningar i konvex programmering , ett underområde av optimeringsteori .

Konvexa uppsättningar

En konvex mängd är en mängd för något vektorrum X så att för någon och [1] $C\subseteq X$ $x,y\in C$ $\lambda \in[0,1]$

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

Konvex funktion

En konvex funktion är varje utökad funktion med reellt värde som uppfyller Jensen-ojämlikheten , det vill säga för alla ${\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] .

På motsvarande sätt är en konvex funktion vilken som helst (utökad) funktion med verkligt värde så att dess epigraf

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

är en konvex mängd [1] .

Konvex konjugation

Den konvexa konjugationen av en utökad funktion med reellt värde (inte nödvändigtvis konvex) är en funktion , där X* är det dubbla rummet av X [2] , så att ${\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\}.

Dubbelparning

Den dubbla konjugationen av en funktion är konjugationens konjugation, som vanligtvis skrivs som . Dubbel konjugering är användbar när man behöver visa att stark eller svag dualitet gäller (med hjälp av störningsfunktionen ). ${\displaystyle f:X\to \mathbb {R} \cup \{\pm \infty \))$ ${\displaystyle f^{**}:X\to \mathbb {R} \cup \{\pm \infty \))$

För all ojämlikhet följer av Fenchels ojämlikhet . För en egenfunktion f = f** om och endast om f är konvext och lägre halvkontinuerligt enligt Fenchel-Moros sats [2] [3] . $x\i X$ $f^{**}(x)\leqslant f(x)$

Konvex minimering

Det (direkta) konvexa programmeringsproblemet är ett formproblem

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

sådan som är en konvex funktion och är en konvex mängd. ${\displaystyle f:X\to \mathbb {R} \cup \{\pm \infty \))$ $M\subseteq X$

Dubbla problem

Principen om dualitet i optimering säger att optimeringsproblem kan ses ur två synvinklar, som ett direkt problem eller ett dubbelt problem .

I allmänhet, givet ett dubbelt par [4] av separerbara lokalt konvexa utrymmen och en funktion , kan vi definiera det direkta problemet som att hitta sådant att Med andra ord är infimum (exakt nedre gräns) för 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$

Om det finns restriktioner kan de byggas in i funktionen om vi sätter , var är indikatorfunktionen . Låt nu (för ett annat dubbelpar ) vara en störningsfunktion så att [5] . $f$ ${\tilde {f}}=f+I_{\mathrm {begränsningar} }$ $jag$ ${\displaystyle F:X\ gånger Y\ till \mathbb {R} \cup \{+\infty \))$ $\left(Y,Y^{*}\right)$ $F(x,0)={\tilde {f))(x)$

Det dubbla problemet för denna störningsfunktion med avseende på det valda problemet definieras som

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

där F* är den konvexa konjugationen i båda variablerna för funktionen F .

Dualitetsgapet är skillnaden mellan höger och vänster sida av ojämlikheten

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

där är den konvexa konjugationen av båda variablerna, och betyder supremum (exakt övre gräns) [6] [7] [5] [6] . $F^{*}$ $\upp$

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

Denna princip är detsamma som svag dualitet . Om båda sidor är lika, sägs problemet uppfylla villkoren för stark dualitet .

Det finns många förutsättningar för stark dualitet, såsom:

F = F** , där F är störningsfunktionen för de primära och dubbla problemen, och F** är dubbelkonjugationen av funktionen F ;
det direkta problemet är ett linjärt programmeringsproblem ;
Slater-villkor för konvexa programmeringsproblem [8] [9] .

Lagrange-dualitet

För ett konvext minimeringsproblem med ojämlikhetsbegränsningar

\min _{x}f(x)

under villkor för i = 1, …, m .

g_{i}(x)\leqslant 0

det dubbla Lagrange-problemet är

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

under villkor för i = 1, …, m ,

u_{i}(x)\geqslant 0

där objektivfunktionen L ( x , u ) är den dubbla lagrangefunktionen definierad enligt följande:

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

Anteckningar

↑ 1 2 3 Rockafellar, 1997 .
↑ 1 2 Zălinescu, 2002 , sid. 75–79.
↑ Borwein och Lewis, 2006 , sid. 76–77.
↑ Det dubbla paret är en trippel , där är ett vektorrum över ett fält , är mängden av alla linjära avbildningar , och det tredje elementet är en bilinjär form . $\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 , sid. 106–113.
↑ Borwein, Lewis, 2006 .
↑ Boyd, Vandenberghe, 2004 .

Litteratur

Osipenko K.Yu. Optimering. Del 1. Konvex analys (föreläsningsanteckningar). M.: MSU. 57 sid.
Osipenko K.Yu. Konvex analys (kursprogram och föreläsningsanteckningar). M.: MSU. 68 sid.
Petrov N.N. Konvex analys (föreläsningsanteckningar) . Izhevsk: UdmGU, 2009. 160 sid.
Zhadan VG optimeringsmetoder. Del I. Introduktion till konvex analys och optimeringsteori: lärobok. lösning för stud. universitet i riktning ... "Tillämpad matematik och fysik". Moskva: MIPT , 2014. ISBN 978-5-7417-0514-8 . (Del I). 271 sid. Utgivning av 300 st.
Element av konvex och starkt konvex analys: en lärobok för studenter vid högre utbildningsinstitutioner som studerar i riktning mot "Tillämpad matematik och fysik" och relaterade områden och specialiteter / E. S. Polovinkin , M. V. Balashov. - 2:a uppl., rättad. och ytterligare - Moskva: Fizmatlit, 2007. - 438 s.; 22 cm - (Phystech lärobok).; ISBN 978-5-9221-0896-6
Protasov V.Yu. Konvex analys (föreläsningsanteckningar. Mekhmat MGU, ekonomiskt flöde, 2009). M.: MSU.
Jonathan Borwein, Adrian Lewis. Konvex analys och icke-linjär optimering: teori och exempel. - 2. - Springer, 2006. - ISBN 978-0-387-29570-1 .
Stephen Boyd, Lieven Vandenberghe. Konvex optimering . - Cambridge University Press, 2004. - ISBN 978-0-521-83378-3 .
R. Tyrrell Rockafellar. Konvex analys. - 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. Konvex analys i allmänna vektorrum. — River Edge, NJ: World Scientific Publishing Co., Inc., 2002. — s. 106–113. - ISBN 981-238-067-1 .
Ernö Robert Csetnek. Att övervinna misslyckandet med de klassiska generaliserade inre punktreguljäritetsförhållandena i konvex optimering. Tillämpningar av dualitetsteorin på förstoringar av maximala monotona operatorer. - Logos Verlag Berlin GmbH, 2010. - ISBN 978-3-8325-2503-3 .
Jonathan Borwein, Adrian Lewis. Konvex analys och icke-linjär optimering: teori och exempel. - 2. - Springer, 2006. - ISBN 978-0-387-29570-1 .
Hiriart-Urruty J.-B., Lemaréchal C. Grunderna för konvex analys. - Berlin: Springer-Verlag, 2001. - ISBN 978-3-540-42205-1 .
Ivan Singer. Abstrakt konvex analys. - New York: John Wiley & Sons, Inc., 1997. - s. xxii+491. - (Canadian Mathematical Society serie med monografier och avancerade texter). - ISBN 0-471-16015-6 .
Stoer J., Witzgall C. Konvexitet och optimering i ändliga dimensioner. - Berlin: Springer, 1970. - Vol. 1. - ISBN 978-0-387-04835-2 .
Kusraev AG, Kutateladze SS Underdifferentialer: teori och tillämpningar. - Dordrecht: Kluwer Academic Publishers, 1995. - ISBN 978-94-011-0265-0 .
Kusraev A. G., Kutateladze S. S. Subdifferentials. Teori och tillämpningar. Del 2. - 2:a, reviderad .. - Novosibirsk: Publishing House of the Institute of Mathematics, 2003. - ISBN 5–86134–116–8.