Kupera konjugaatio

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 4. lokakuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Funktion kupera konjugaatti on yleistys Legendre-muunnoksesta , joka koskee ei-konveksia funktioita. Se tunnetaan myös nimellä Legendre-Fenchel- muunnos tai Fennel-muunnos ( Adrien Marie Legendren ja Werner Fenchelin mukaan ). Konjugaatiolla muunnetaan optimointitehtävä vastaavaksi kaksoisongelmaksi , joka on ehkä helpompi ratkaista.

Määritelmä

Antaa olla todellinen topologinen vektoriavaruus ja antaa olla kaksoisavaruus . Merkitse kaksoispari ] $X$ $X^{*}$ $X$

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

Toiminnan vuoksi

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

arvojen ottaminen laajennetulta numeroviivalta , kupera konjugaatio

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

määritellään supremumin kannalta kaavalla

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

tai vastaavasti kaavan infimumin mukaan

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

Tämän määritelmän voidaan tulkita koodaavan funktion epigrafin kuperaa runkoa sen tukevien hypertasojen suhteen [1] [2] .

Esimerkkejä

Affiinin funktion kupera konjugaatio

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

on yhtä suuri

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

Potenssifunktion kupera konjugaatio

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

on yhtä suuri

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

missä ${\tfrac {1}{p}}+{\tfrac {1}{q}}=1.$

Itseisarvofunktion kupera konjugaatio

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

on yhtä suuri

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

Eksponentiaalisen funktion konjugaatti on yhtä suuri kuin $f(x)=\,\!e^{x}$

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

Eksponentiaalisen funktion konveksi konjugaatio ja Legendre-muunnos ovat samat, paitsi että konveksin konjugaation alue on tiukasti leveämpi, koska Legendre-muunnos määritellään vain positiivisille reaaliluvuille.

Suhde odotettuihin tappioihin (keskimääräiset riskin kustannukset)

Olkoon F satunnaismuuttujan X integraalijakaumafunktio . _ Sitten (integrointi osilla),

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

on kupera konjugaatio

f^{*}(p)=\int _{0}^{p}F^{-1}(q)\,dq=(p-1)F^{-1}(p)+ \operaattorinimi {E} \vasen[\min(F^{-1}(p),X)\oikea]=pF^{-1}(p)-\operaattorinimi {E} \vasen[\max(0, F^{-1}(p)-X)\oikea].

Tilaus

Konkreettisella tulkinnalla on muunnos

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

alkuperäisen funktion f ei-laskevana uudelleenjärjestelynä. Erityisesti ei vähennä. $f^{\text{inc}}=f$ $f$

Ominaisuudet

Suljetun konveksin funktion konjugaatti on jälleen suljettu konveksi funktio . Monitahoisen kuperan funktion kupera konjugaatti (kupera funktio, jossa on monitahoinen epigrafi ) on jälleen monitahoinen kupera funktio.

Tilauksen peruutus

Kupera konjugaatio kääntää järjestyksen - jos , niin . Tässä $f\leqslant g$ $f^{*}\geqslant g^{*}$

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

Toimintoperheelle tämä johtuu siitä tosiasiasta, että suprema voidaan vaihtaa keskenään ${\displaystyle \left(f_{\alpha }\right)_{\alpha ))$

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

ja maksimi-min epäyhtälöstä

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

Kaksinkertainen pariliitos

Funktion kupera konjugaatti on aina alempi puolijatkuva . Kaksoiskonjugaatio (kuperan konjugaation kupera konjugaatio) on myös suljettu kupera runko , eli suurin alempi puolijatkuva kupera funktio, jossa on . Konveksille ominaisfunktioille jos ja vain jos f on konveksi ja alempi puolijatkuva Fenchel -Moron lauseen mukaan . $f^{**}$ $f^{**}\leqslant f$ $f=f^{**}$

Fenchelin epätasa-arvo

Jokaiselle funktiolle f ja sen konveksille konjugaatille Fenchelin epäyhtälö (tunnetaan myös nimellä Fenchel-Moro-epäyhtälö ) pätee mihin tahansa ja : $f^{*}$ $x\in X$ $p\in X^{*}$

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

Todistus seuraa välittömästi konveksin konjugaation määritelmästä: . $f^{*}(p)=\sup _{\tilde {x}}\{\langle p,{\tilde {x}}\rangle -f({\tilde {x}})\} \geqslant \langle p,x\rangle -f(x)$

Pullo

kahdelle funktiolle ja numerolle , $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}^{*}

Tässä operaatio on kupera kartoitus itseensä. ${*}$

Lopullinen konvoluutio

Kahden funktion f ja g lopullinen konvoluutio määritellään seuraavasti

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

Olkoot f 1 , …, f m säännölliset konveksit alemmat puolijatkuvat funktiot . Tällöin lopullinen konvoluutio on kupera ja alempi puolijatkuva (mutta ei välttämättä säännöllinen funktio) [3] ja täyttää yhtälön $\mathbb {R} ^{n}$

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

Kahden funktion loppukonvoluutiolla on geometrinen tulkinta – kahden funktion loppukonvoluution (tiukka) epigrafi on yhtä suuri kuin näiden funktioiden (tiukkojen) epigrafien Minkowskin summa [4] .

Argumentin maksimointi

Jos funktio on differentioituva, niin sen derivaatta on maksimoiva argumentti konveksia konjugaatiota laskettaessa: $f$

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

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

missä

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

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

ja lisäksi,

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

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

Skaalausominaisuudet

Jos joillekin , niin $\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 }}\oikea).

Jos kyseessä on lisäparametri (esimerkiksi, ), lisäksi $\alpha$

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

missä missä valitaan maksimoiva argumentti. ${\tilde x}$

Käyttäytyminen lineaaristen muunnosten alla

Olkoon A rajoitettu lineaarinen operaattori X : stä Y :ään . Jokaiselle konveksille funktiolle f X : ssä meillä on

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

missä

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

on f : n esikuva A :lle ja A * on A:n adjoint - operaattori [ 5] .

Suljettu konveksi funktio f on symmetrinen annetulle ortogonaalisten lineaaristen muunnosten joukolle G

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

jos ja vain jos konveksi konjugaatio f * on symmetrinen G :lle.

Joidenkin kuperoiden konjugaatioiden taulukko

Seuraava taulukko sisältää Legendre-muunnokset monille yleisesti käytetyille funktioille sekä useille hyödyllisille ominaisuuksille [6] .

$g(x)$	${\näyttötyyli \operaattorin nimi {dom} (g)}$	$g^{}(x^{})$	$\operaattorin nimi {dom} (g^{*})$
$f(ax)$ (missä ) $a \neq 0$	$X$	$f^{}\left({\frac {x^{}}{a}}\oikea)$	$X^{*}$
$f(x+b)$	$X$	$f^{}(x^{})-\langle b,x^{*}\rangle$	$X^{*}$
$af(x)$ (missä ) $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 }}\right)\quad (\gamma >0)$	$X^{*}$
${\frac {\|x\|^{p}}{p}}$ (missä ) $p>1$	$\mathbb {R}$	${\frac {\|x^{*}\|^{q}}{q}}$ (missä ) ${\frac {1}{p}}+{\frac {1}{q}}=1$	$\mathbb {R}$
${\frac {-x^{p}}{p}}$ (missä ) $0<p<1$	${\displaystyle \mathbb {R} _{+))$	${\frac {-(-x^{*})^{q}}{q}}$ (missä ) ${\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} _{+))$

Katso myös

Muistiinpanot

↑ Legendre Transform . Haettu 14. huhtikuuta 2019. Arkistoitu alkuperäisestä 28. heinäkuuta 2020. (määrätön)
↑ Frank Nielsen. Legendre-muunnos ja informaatiogeometria . Haettu 19. huhtikuuta 2019. Arkistoitu alkuperäisestä 11. marraskuuta 2013. (määrätön)
↑ Phelps, 1991 , s. 42.
↑ Bauschke, Goebel, Lucet, Wang, 2008 , s. 766.
↑ Ioff, Tikhomirov, 1974 , s. lausunto 3.4.3.
↑ Borwein ja Lewis, 2006 , s. 50–51.

Kirjallisuus

Robert R. Phelps. Kuperat funktiot, yksitoikkoiset operaattorit ja erotettavuus. - Springer, 1991. - ISBN 0-387-56715-1 .
Heinz H. Bauschke, Rafal Goebel, Yves Lucet, Xianfu Wang. Proksimaalinen keskiarvo: Perusteoria // SIAM Journal on Optimization. - 2008. - T. 19 , numero. 2 . - doi : 10.1137/070687542 .
Ioffe A. D., Tikhomirov V. M. Extremaalisten ongelmien teoria. - M . : "Nauka", 1974.
Jonathan Borwein, Adrian Lewis. Kupera analyysi ja epälineaarinen optimointi: teoria ja esimerkit. - Springer, 2006. - ISBN 978-0-387-29570-1 .
Vladimir Igorevitš Arnold. Klassisen mekaniikan matemaattiset menetelmät. - M . : "Nauka", 1989.
R. Tyrrell Rockafellar. Kupera analyysi . - Princeton: Princeton University Press, 1970. - ISBN 0-691-01586-4 .

Linkit

Touchette, Hugo Legendre-Fenchel muuttuu pähkinänkuoressa (PDF) (linkkiä ei saatavilla) (16. lokakuuta 2014). Haettu 9. tammikuuta 2017. Arkistoitu alkuperäisestä 7. huhtikuuta 2017. (määrätön)
Touchette, Hugo Elements of convex analysis (PDF) (linkki ei saatavilla) (21.11.2006). Haettu 26. maaliskuuta 2008. Arkistoitu alkuperäisestä 26. toukokuuta 2015. (määrätön)
Legendre ja Legendre-Fenchel muuttuvat vaiheittaisessa selityksessä . Haettu: 18. toukokuuta 2013. (määrätön)