Konvexní analýza

Konvexní analýza je odvětví matematiky oddané studiu vlastností konvexních funkcí a konvexních množin , často mající aplikace v konvexním programování , což je podpole teorie optimalizace .

Konvexní množiny

Konvexní množina je množina pro nějaký vektorový prostor X taková, že pro libovolné a [1] $C\subseteq X$ $x,y\in C$ $\lambda \in[0,1]$

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

Konvexní funkce

Konvexní funkce je jakákoli rozšířená funkce s reálnou hodnotou , která splňuje Jensenovu nerovnost , tedy pro jakoukoli ${\displaystyle f:X\to \mathbb {R} \cup \{\pm \infty \))$ $x,y\v X$ $\lambda \in[0,1]$

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

[1] .

Ekvivalentně je konvexní funkce jakákoli (rozšířená) funkce s reálnou hodnotou tak, že její epigraf

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

je konvexní množina [1] .

Konvexní konjugace

Konvexní konjugace rozšířené funkce s reálnou hodnotou (ne nutně konvexní) je funkce , kde X* je duální prostor X [ 2] , takže ${\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\}.

Dvojité párování

Dvojitá konjugace funkce je konjugační konjugace, která se obvykle zapisuje jako . Dvojitá konjugace je užitečná, když potřebujeme ukázat, že platí silná nebo slabá dualita (pomocí perturbační funkce ). ${\displaystyle f:X\to \mathbb {R} \cup \{\pm \infty \))$ ${\displaystyle f^{**}:X\to \mathbb {R} \cup \{\pm \infty \))$

Neboť jakákoliv nerovnost vyplývá z Fenchelovy nerovnosti . Pro vlastní funkci f = f** právě tehdy, když je f konvexní a dolní polospojitá podle Fenchel-Moro věty [2] [3] . $x\in X$ $f^{**}(x)\leqslant f(x)$

Konvexní minimalizace

Problém (přímého) konvexního programování je problémem formuláře

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

taková, která je konvexní funkcí a je konvexní množinou. ${\displaystyle f:X\to \mathbb {R} \cup \{\pm \infty \))$ $M\subseteq X$

Duální problém

Princip duality v optimalizaci říká, že na optimalizační problémy lze nahlížet ze dvou úhlů pohledu, jako na přímý problém nebo jako duální problém .

Obecně platí, že vzhledem k duálnímu páru [4] oddělitelných lokálně konvexních prostorů a funkce , můžeme definovat přímý problém jako nalezení takového , že Jinými slovy, je infimum (přesná dolní mez) funkce . $\left(X,X^{*}\right)$ ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \))$ ${\klobouk {x}}$ $f({\hat {x)))=\inf _{x\in X}f(x).\,$ $f({\hat {x)))$ $F$

Pokud existují omezení, lze je zabudovat do funkce , pokud dáme , kde je funkce indikátoru . Nechť nyní (pro další duální pár ) je poruchová funkce taková, že [5] . $F$ ${\tilde {f}}=f+I_{\mathrm {omezení} }$ $já$ ${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \))$ $\left(Y,Y^{*}\right)$ $F(x,0)={\tilda {f))(x)$

Duální problém pro tuto poruchovou funkci vzhledem ke zvolenému problému je definován jako

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

kde F* je konvexní konjugace v obou proměnných funkce F .

Dualitní mezera je rozdíl mezi pravou a levou stranou nerovnosti

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

kde je konvexní konjugace obou proměnných a znamená supremum (přesná horní mez) [6] [7] [5] [6] . $F^{*}$ $\nahoru$

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

Tento princip je stejný jako slabá dualita . Jsou-li obě strany stejné, říká se, že problém splňuje podmínky silné duality .

Existuje mnoho podmínek pro silnou dualitu, jako například:

F = F** , kde F je poruchová funkce pro primární a duální problémy a F** je dvojitá konjugace funkce F ;
přímý problém je problém lineárního programování ;
Slaterova podmínka pro problémy konvexního programování [8] [9] .

Lagrangeova dualita

Pro problém konvexní minimalizace s omezeními nerovnosti

\min _{x}f(x)

za podmínek pro i = 1, …, m .

g_{i}(x)\leqslant 0

duální problém Lagrange je

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

za podmínek pro i = 1, …, m ,

u_{i}(x)\geqslant 0

kde účelová funkce L ( x , u ) je duální Lagrangeova funkce definovaná takto:

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

Poznámky

↑ 1 2 3 Rockafellar, 1997 .
↑ 1 2 Zălinescu, 2002 , s. 75–79.
↑ Borwein a Lewis, 2006 , s. 76–77.
↑ Dvojice je trojice , kde je vektorový prostor nad polem , je množina všech lineárních zobrazení a třetím prvkem je bilineární forma . $\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 .

Literatura

Osipenko K.Yu. Optimalizace. Část 1. Konvexní analýza (poznámky k přednášce). M.: MGU. 57 str.
Osipenko K.Yu. Konvexní analýza (program kurzu a poznámky k přednášce). M.: MGU. 68 str.
Petrov N.N. Konvexní analýza (poznámky z přednášky) . Iževsk: UdmGU, 2009. 160 s.
Metody optimalizace Zhadan VG . Část I. Úvod do konvexní analýzy a teorie optimalizace: učebnice. vyrovnání pro stud. univerzit ve směru ... "Aplikovaná matematika a fyzika". Moskva: MIPT , 2014. ISBN 978-5-7417-0514-8 . (část I). 271 str. Vydání 300 ks.
Prvky konvexní a silně konvexní analýzy: učebnice pro studenty vysokých škol studujících směr "Aplikovaná matematika a fyzika" a související oblasti a specializace / E. S. Polovinkin , M. V. Balashov. - 2. vyd., opraveno. a doplňkové - Moskva: Fizmatlit, 2007. - 438 s.; 22 cm.- (učebnice fyziky).; ISBN 978-5-9221-0896-6
Protasov V.Yu. Konvexní analýza (poznámky z přednášky. Mekhmat MGU, ekonomický tok, 2009). M.: MGU.
Jonathan Borwein, Adrian Lewis. Konvexní analýza a nelineární optimalizace: teorie a příklady. - 2. - Springer, 2006. - ISBN 978-0-387-29570-1 .
Stephen Boyd, Lieven Vandenberghe. Konvexní optimalizace . - Cambridge University Press, 2004. - ISBN 978-0-521-83378-3 .
R. Tyrrell Rockafellar. Konvexní analýza. - Princeton, NJ: Princeton University Press, 1997. - ISBN 978-0-691-01586-6 .
Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Dualita ve vektorové optimalizaci. - Springer, 2009. - ISBN 978-3-642-02885-4 .
Constantin Zalinescu. Konvexní analýza v obecných vektorových prostorech. — River Edge, NJ: World Scientific Publishing Co., Inc., 2002. — s. 106–113. - ISBN 981-238-067-1 .
Ernö Robert Csetnek. Překonání selhání klasických zobecněných podmínek pravidelnosti vnitřního bodu v konvexní optimalizaci. Aplikace teorie duality na zvětšení maximálních monotónních operátorů. - Logos Verlag Berlin GmbH, 2010. - ISBN 978-3-8325-2503-3 .
Jonathan Borwein, Adrian Lewis. Konvexní analýza a nelineární optimalizace: teorie a příklady. - 2. - Springer, 2006. - ISBN 978-0-387-29570-1 .
Hiriart-Urruty J.-B., Lemaréchal C. Základy konvexní analýzy. - Berlin: Springer-Verlag, 2001. - ISBN 978-3-540-42205-1 .
Ivan Singer. Abstraktní konvexní analýza. - New York: John Wiley & Sons, Inc., 1997. - str. xxii+491. - (série monografií a odborných textů Kanadské matematické společnosti). - ISBN 0-471-16015-6 .
Stoer J., Witzgall C. Konvexita a optimalizace v konečných dimenzích. - Berlin: Springer, 1970. - svazek 1. - ISBN 978-0-387-04835-2 .
Kusraev AG, Kutateladze SS Subdiferenciály: Teorie a aplikace. - Dordrecht: Kluwer Academic Publishers, 1995. - ISBN 978-94-011-0265-0 .
Kusraev A. G., Kutateladze S. S. Subdiferenciály. Teorie a aplikace. Část 2. - 2., revidováno .. - Novosibirsk: Nakladatelství Ústavu matematiky, 2003. - ISBN 5–86134–116–8.