Konvex ragozás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. október 4-én felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

Egy függvény konvex konjugáltja a Legendre transzformáció általánosítása, amely nem konvex függvényekre vonatkozik. Legendre-Fenchel transzformációként vagy Fennel transzformációként is ismert ( Adrien Marie Legendre és Werner Fenchel nyomán ). A konjugáció arra szolgál, hogy egy optimalizálási feladatot megfelelő kettős problémává alakítsanak át , ami talán könnyebben megoldható.

Definíció

Legyen egy valós topológiai vektortér, és legyen a kettős tere . A kettős párt jelölje $x$ $X^{*}$ $x$

\langle \cdot ,\cdot \rangle :X^{*}\times X\to \mathbb {R} .

A funkcióért

{\displaystyle f:X\to \mathbb {R} \cup \{-\infty ,+\infty \))

értékek felvétele a kiterjesztett számegyenesen , konvex konjugáció

{\displaystyle f^{*}:X^{*}\to \mathbb {R} \cup \{-\infty ,+\infty \))

képlettel határozzuk meg a szuprémum szempontjából

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

vagy ezzel egyenértékűen a képlet szerinti infimum kifejezésével

f^{*}\left(x^{*}\right):=-\inf \left\{\left.f\left(x\right)-\left\langle x^{*}, x\right\rangle \right|x\in X\right\}.

Ez a definíció úgy értelmezhető, hogy egy függvény epigráfjának konvex burkot kódolja a támasztó hipersíkjai szempontjából [1] [2] .

Példák

Egy affin függvény konvex konjugációja

f(x)=\left\langle a,x\right\rangle -b,\,a\in \mathbb {R} ^{n},b\in \mathbb {R}

egyenlő

f^{*}\left(x^{*}\right)={\begin{cases}b,&x^{*}=a\\+\infty ,&x^{*}\neq a. \end{cases}}

Hatványfüggvény konvex konjugációja

f(x)={\frac {1}{p}}|x|^{p},\,1<p<\infty

egyenlő

f^{*}\left(x^{*}\right)={\frac {1}{q}}|x^{*}|^{q},\,1<q<\infty

ahol ${\tfrac {1}{p}}+{\tfrac {1}{q}}=1.$

Az abszolút érték függvény konvex konjugációja

f(x)=\left|x\right|

egyenlő

f^{*}\left(x^{*}\right)={\begin{cases}0,&\left|x^{*}\right|\leqslant 1\\\infty ,&\ left|x^{*}\right|>1.\end{cases}}

Az exponenciális függvény konvex konjugáltja egyenlő ${\displaystyle f(x)=\,\!e^{x))$

f^{*}\left(x^{*}\right)={\begin{cases}x^{*}\ln x^{*}-x^{*},&x^{*} >0\\0,&x^{*}=0\\\infty ,&x^{*}<0.\end{cases}}

A konvex konjugáció és az exponenciális függvény Legendre-transzformációja megegyezik, kivéve, hogy a konvex konjugáció tartománya szigorúan szélesebb, mivel a Legendre-transzformáció csak pozitív valós számokra van definiálva.

Kapcsolat a várható veszteségekkel (átlagos kockázati költség)

Jelölje F az X valószínűségi változó integráleloszlásfüggvényét . Ezután (alkatrészenként integrálva),

f(x):=\int _{-\infty }^{x}F(u)\,du=\operátornév {E} \left[\max(0,xX)\right]=x- \operátornév {E} \left[\min(x,X)\right]

konvex ragozása van

f^{*}(p)=\int _{0}^{p}F^{-1}(q)\,dq=(p-1)F^{-1}(p)+ \operátornév {E} \left[\min(F^{-1}(p),X)\right]=pF^{-1}(p)-\operátornév {E} \left[\max(0, F^{-1}(p)-X)\jobbra].

Rendelés

A konkrét értelmezésnek átalakulása van

f^{\text{inc}}(x):=\arg \sup _{t}\,t\cdot x-\int _{0}^{1}\max\{tf(u) ,0\}\,\mathrm {d} u,

az f kezdeti függvény nem csökkenő átrendezéseként. Különösen a nem csökken. $f^{\text{inc}}=f$ $f$

Tulajdonságok

Egy zárt konvex függvény konvex konjugáltja ismét egy zárt konvex függvény . Egy poliéder konvex függvény konvex konjugáltja (konvex függvény poliéder epigráftal ) ismét poliéder konvex függvény.

Rendelés visszavonása

A konvex konjugáció megfordítja a sorrendet - ha , akkor . Itt $f\leqslant g$ $f^{*}\geqslant g^{*}$

(f\leqslant g):\iff (\forall x,f(x)\leqslant g(x)).

Egy függvénycsalád esetében ez abból következik, hogy a suprema felcserélhető ${\displaystyle \left(f_{\alpha }\right)_{\alpha ))$

\left(\inf _{\alpha }f_{\alpha }\right)^{*}(x^{*})=\sup _{\alpha }f_{\alpha }^{*}( x^{*}),

és a max-min egyenlőtlenségből

\left(\sup _{\alpha }f_{\alpha }\right)^{*}(x^{*})\leqslant \inf _{\alpha }f_{\alpha }^{*} (x^{*}).

Kettős párosítás

Egy függvény konvex konjugáltja mindig alsó félfolytonos . A kettős konjugáció (a konvex konjugáció konvex konjugációja) szintén egy zárt konvex burok , azaz a legnagyobb alsó félfolyamatos konvex függvény -val . Konvex sajátfüggvényekre akkor és csak akkor, ha f konvex és alsó félfolytonos a Fenchel-Moro tétel szerint . $f^{**}$ $f^{**}\leqslant f$ $f=f^{**}$

Fenchel egyenlőtlensége

Bármely f függvényre és konvex konjugátumára a Fenchel-egyenlőtlenség (más néven Fenchel-Moro egyenlőtlenség ) érvényes bármely és : $f^{*}$ $x\X-ben$ $p\in X^{*}$

\left\langle p,x\right\rangle \leqslant f(x)+f^{*}(p).

A bizonyítás közvetlenül a konvex ragozás definíciójából következik: . $f^{*}(p)=\sup _{\tilde {x}}\{\langle p,{\tilde {x}}\rangle -f({\tilde {x}})\} \geqslant \langle p,x\rangle -f(x)$

Kidudorodás

Két függvény és egy szám esetén $f_0$ $f_1$ $0\leqslant \lambda \leqslant 1$

\left((1-\lambda )f_{0}+\lambda f_{1}\right)^{*}\leqslant (1-\lambda )f_{0}^{*}+\lambda f_ {1}^{*}

Itt a művelet önmaga konvex leképezése. ${*}$

Végső konvolúció

Két f és g függvény végső konvolúcióját a következőképpen definiáljuk

\left(f\Box g\right)(x)=\inf \left\{f(xy)+g(y)\,|\,y\in \mathbb {R} ^{n}\ jobb\}.

Legyenek f 1 , …, f m szabályos konvex alsó félfolyamatos függvények -on . Ekkor a végső konvolúció konvex és alsó félfolytonos (de nem feltétlenül reguláris függvény) [3] és kielégíti az egyenlőséget $\mathbb {R} ^{n}$

\left(f_{1}\Box \cdots \Box f_{m}\right)^{*}=f_{1}^{*}+\cdots +f_{m}^{*}.

Két függvény végső konvolúciójának geometriai értelmezése van – két függvény végső konvolúciójának (szigorú) epigráfja egyenlő e függvények (szigorú) epigráfjainak Minkowski összegével [4] .

Az argumentum maximalizálása

Ha a függvény differenciálható, akkor a deriváltja a maximalizáló argumentum a konvex konjugáció számításakor: $f$

f^{\prime }(x)=x^{*}(x):=\arg \sup _{x^{*}}{\langle x,x^{*}\rangle }-f ^{*}(x^{*})

és

f^{{*}\prime }(x^{*})=x(x^{*}):=\arg \sup _{x}{\langle x,x^{*}\rangle }-f(x);

ahol

x=\nabla f^{*}(\nabla f(x)),

x^{*}=\nabla f(\nabla f^{*}(x^{*})),

és ráadásul

f^{\prime \prime }(x)\cdot f^{{*}\prime \prime }(x^{*}(x))=1,

f^{{*}\prime \prime }(x^{*})\cdot f^{\prime \prime }(x(x^{*}))=1.

Méretezési tulajdonságok

Ha egyeseknek , akkor $\gamma >0$ $\,g(x)=\alpha +\beta x+\gamma \cdot f(\lambda x+\delta )$

g^{*}(x^{*})=-\alpha -\delta {\frac {x^{*}-\beta }{\lambda ))+\gamma \cdot f^{*} \left({\frac {x^{*}-\beta }{\lambda \gamma }}\right).

Egy további paraméter (mondjuk, ) esetén ráadásul $\alpha$

f_{\alpha }(x)=-f_{\alpha }({\tilde {x)))

ahol ahol a maximalizáló argumentum választja. ${\tilde x}$

Viselkedés lineáris transzformációk alatt

Legyen A egy korlátos lineáris operátor X - től Y - ig . Bármely f konvex függvényre X -en van

\left(Af\right)^{*}=f^{*}A^{*}

ahol

{\displaystyle (Af)(y)=\inf\{f(x):x\in X,Ax=y\))

az f előképe A esetén , és A * az A adjunkt operátora [ 5] .

Egy f zárt konvex függvény szimmetrikus az ortogonális lineáris transzformációk adott G halmazára

f\left(Ax\right)=f(x),\;\forall x,\;\forall A\in G

akkor és csak akkor, ha az f * konvex konjugáció szimmetrikus G -re .

Néhány konvex ragozás táblázata

A következő táblázat a Legendre transzformációkat tartalmazza számos gyakran használt függvényhez, valamint számos hasznos tulajdonsághoz [6] .

$g(x)$	$\operatorname {dom} (g)$	$g^{}(x^{})$	$\operatorname {dom} (g^{*})$
$f(ax)$ (hol ) $a \neq 0$	$x$	$f^{}\left({\frac {x^{}}{a}}\right)$	$X^{*}$
$f(x+b)$	$x$	$f^{}(x^{})-\langle b,x^{*}\rangle$	$X^{*}$
$af(x)$ (hol ) $a>0$	$x$	$af^{}\left({\frac {x^{}}{a}}\right)$	$X^{*}$
$\alpha +\beta x+\gamma \cdot f(\lambda x+\delta )$	$x$	$-\alpha -\delta {\frac {x^{}-\beta }{\lambda }}+\gamma \cdot f^{}\left({\frac {x^{*}- \beta }{\gamma \lambda }}\jobbra)\quad (\gamma >0)$	$X^{*}$
${\frac {\|x\|^{p}}{p}}$ (hol ) $p>1$	$\mathbb {R}$	${\frac {\|x^{*}\|^{q}}{q}}$ (hol ) ${\frac {1}{p}}+{\frac {1}{q}}=1$	$\mathbb {R}$
${\frac {-x^{p}}{p}}$ (hol ) $0<p<1$	${\displaystyle \mathbb {R} _{+))$	${\frac {-(-x^{*})^{q}}{q}}$ (hol ) ${\frac {1}{p}}+{\frac {1}{q}}=1$	$\mathbb {R} _{-}$
${\displaystyle {\sqrt {1+x^{2))))$	$\mathbb {R}$	${\displaystyle -{\sqrt {1-(x^{*})^{2))))$	$[-1,1]$
$-\log(x)$	$\mathbb {R} _{++}$	$-(1+\log(-x^{*}))$	$\mathbb {R} _{--}$
$e^{x}$	$\mathbb {R}$	${\begin{cases}x^{}\log(x^{})-x^{}&{\text{if }}x^{}>0\\0&{\text {if }}x^{*}=0\end{cases}}$	${\displaystyle \mathbb {R} _{+))$
$\log \left(1+e^{x}\right)$	$\mathbb {R}$	${\begin{cases}x^{}\log(x^{})+(1-x^{})\log(1-x^{})&{\text{if }}0<x^{}<1\\0&{\text{if }}x^{}=0,1\end{cases}}$	$[0,1]$
$-\log \left(1-e^{x}\right)$	$\mathbb {R}$	${\begin{cases}x^{}\log(x^{})-(1+x^{})\log(1+x^{})&{\text{if }}x^{}>0\\0&{\text{if }}x^{}=0\end{cases}}$	${\displaystyle \mathbb {R} _{+))$

Lásd még

Jegyzetek

↑ Legendre Transform . Letöltve: 2019. április 14. Az eredetiből archiválva : 2020. július 28. (határozatlan)
↑ Frank Nielsen. Legendre transzformáció és információgeometria . Letöltve: 2019. április 19. Az eredetiből archiválva : 2013. november 11.. (határozatlan)
↑ Phelps, 1991 , p. 42.
↑ Bauschke, Goebel, Lucet, Wang, 2008 , p. 766.
↑ Ioff, Tyihomirov, 1974 , p. nyilatkozat 3.4.3.
↑ Borwein és Lewis, 2006 , p. 50–51.

Irodalom

Robert R. Phelps. Konvex függvények, monoton operátorok és differenciálhatóság. - Springer, 1991. - ISBN 0-387-56715-1 .
Heinz H. Bauschke, Rafal Goebel, Yves Lucet, Xianfu Wang. A proximális átlag: alapvető elmélet // SIAM Journal on Optimization. - 2008. - T. 19 , szám. 2 . - doi : 10.1137/070687542 .
Ioffe A. D., Tikhomirov V. M. Az extrém problémák elmélete. - M . : "Nauka", 1974.
Jonathan Borwein, Adrian Lewis. Konvex elemzés és nemlineáris optimalizálás: elmélet és példák. - Springer, 2006. - ISBN 978-0-387-29570-1 .
Vladimir Igorevics Arnold. A klasszikus mechanika matematikai módszerei. - M . : "Nauka", 1989.
R. Tyrrell Rockafellar. Konvex elemzés . - Princeton: Princeton University Press, 1970. - ISBN 0-691-01586-4 .

Linkek

Touchette, Hugo Legendre-Fenchel dióhéjban átalakul (PDF) (a hivatkozás nem elérhető) (2014. október 16.). Letöltve: 2017. január 9. Az eredetiből archiválva : 2017. április 7.. (határozatlan)
Touchette, Hugo A konvex elemzés elemei (PDF) (hivatkozás nem elérhető) (2006. november 21.). Letöltve: 2008. március 26. Az eredetiből archiválva : 2015. május 26.. (határozatlan)
Legendre és Legendre-Fenchel átalakul egy lépésről lépésre magyarázatban . Letöltve: 2013. május 18. (határozatlan)