Conjugación convexa

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 4 de octubre de 2019; las comprobaciones requieren 3 ediciones .

El conjugado convexo de una función es una generalización de la transformada de Legendre que se aplica a funciones no convexas. También se conoce como la transformación de Legendre-Fenchel o la transformación de Fennel (después de Adrien Marie Legendre y Werner Fenchel ). La conjugación se utiliza para transformar un problema de optimización en un problema dual correspondiente , que quizás sea más fácil de resolver.

Definición

Sea un espacio vectorial topológico real y sea el espacio dual para . Denote el par dual por $X$ ${\ estilo de visualización X ^ {*}}$ $X$

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

para la función

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

tomando valores en la recta numérica extendida , conjugación convexa

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

definido en términos del supremo por la fórmula

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

o, de manera equivalente, en términos del mínimo por la fórmula

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

Esta definición puede interpretarse como la codificación de la envolvente convexa del epígrafe de una función en términos de sus hiperplanos de apoyo [1] [2] .

Ejemplos

Conjugación convexa de una función afín

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

es igual

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

Conjugación convexa de una función de potencia

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

es igual

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

dónde ${\tfrac {1}{p}}+{\tfrac {1}{q}}=1.$

Conjugación convexa de la función de valor absoluto

f(x)=\izquierda|x\derecha|

es igual

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

El conjugado convexo de la función exponencial es igual a ${\displaystyle f(x)=\,\!e^{x))$

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

La conjugación convexa y la transformada de Legendre de una función exponencial son lo mismo, excepto que el dominio de la conjugación convexa es estrictamente más amplio, ya que la transformada de Legendre se define solo para números reales positivos.

Relación con las pérdidas esperadas (coste medio del riesgo)

Sea F la función de distribución integral de la variable aleatoria X . Entonces (integrando por partes),

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

tiene una conjugación convexa

f^{*}(p)=\int _{0}^{p}F^{-1}(q)\,dq=(p-1)F^{-1}(p)+ \nombre del operador {E} \left[\min(F^{-1}(p),X)\right]=pF^{-1}(p)-\nombre del operador {E} \left[\max(0, F^{-1}(p)-X)\derecha].

Pedidos

La interpretación concreta tiene una transformación.

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

como un reordenamiento no decreciente de la función inicial f. En particular, para no decrece. $f^{\text{inc}}=f$ $F$

Propiedades

El conjugado convexo de una función convexa cerrada es nuevamente una función convexa cerrada . El conjugado convexo de una función convexa poliédrica (una función convexa con un epígrafe poliédrico ) es nuevamente una función convexa poliédrica.

Reversión de orden

La conjugación convexa invierte el orden : si , entonces . Aquí $f \ leqslant g$ $f^{*}\geqslant g^{*}$

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

Para una familia de funciones , esto se sigue del hecho de que la suprema puede intercambiarse ${\displaystyle \left(f_{\alpha }\right)_{\alpha ))$

\left(\inf_{\alpha }f_{\alpha }\right)^{*}(x^{*})=\sup_{\alpha }f_{\alpha }^{*}( x^{*}),

y de la desigualdad max-min

\left(\sup_{\alpha }f_{\alpha }\right)^{*}(x^{*})\leqslant \inf_{\alpha }f_{\alpha }^{*} (x^{*}).

Doble emparejamiento

El conjugado convexo de una función es siempre semicontinua inferior . La doble conjugación (la conjugación convexa de la conjugación convexa) también es una envolvente convexa cerrada , es decir, la función convexa semicontinua inferior más grande con . Para funciones propias convexas si y solo si f es convexa y semicontinua inferior por el teorema de Fenchel-Moro . ${\ estilo de visualización f ^ {**}}$ $f^{**}\leqslant f$ ${\ estilo de visualización f = f ^ {**}}$

Desigualdad de Fenchel

Para cualquier función f y su conjugado convexo , la desigualdad de Fenchel (también conocida como desigualdad de Fenchel-Moro ) se cumple para cualquier y : ${\ estilo de visualización f ^ {*}}$ $x\en X$ $p\en X^{*}$

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

La demostración se sigue inmediatamente de la definición de conjugación convexa: . $f^{*}(p)=\sup_{\tilde {x}}\{\langle p,{\tilde {x}}\rangle -f({\tilde {x}})\} \geqslant \langle p,x\rangle -f(x)$

Bulto

Para dos funciones y y un número, $f_0$ $f_1$ ${\ estilo de visualización 0 \ leqslant \ lambda \ leqslant 1}$

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

Aquí la operación es un mapeo convexo en sí mismo. ${*}$

Convolución infinal

La convolución final de dos funciones f y g se define como

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

Sean f 1 , …, f m funciones semicontinuas inferiores regulares convexas en . Entonces la convolución final es convexa y semicontinua inferior (pero no necesariamente una función regular) [3] y satisface la igualdad $\mathbb{R} ^{n}$

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

La convolución infinal de dos funciones tiene una interpretación geométrica: el epígrafe (estricto) de la convolución infinal de dos funciones es igual a la suma de Minkowski de los epígrafes (estrictos) de estas funciones [4] .

Argumento de maximización

Si la función es derivable, entonces su derivada es el argumento de maximización al calcular la conjugación convexa: $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);

dónde

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

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

y además,

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

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

Propiedades de escalado

Si para algunos , entonces $\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).

En el caso de un parámetro adicional (por ejemplo, ), además, $\alfa$

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

donde donde es elegido por el argumento de maximización. ${\ tilde x}$

Comportamiento bajo transformaciones lineales

Sea A un operador lineal acotado de X a Y. Para cualquier función convexa f en X , tenemos

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

dónde

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

es la preimagen de f para A , y A * es el operador adjunto para A [5] .

Una función convexa cerrada f es simétrica para un conjunto dado G de transformaciones lineales ortogonales

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

si y solo si la conjugación convexa f * es simétrica para G.

Tabla de algunas conjugaciones convexas

La siguiente tabla proporciona las transformaciones de Legendre para muchas funciones de uso común, así como para varias propiedades útiles [6] .

$g(x)$	${\ estilo de visualización \ nombre del operador {dom} (g)}$	${\ estilo de visualización g^{}(x^{})}$	${\ estilo de visualización \ nombre del operador {dom} (g^{*})}$
${\ Displaystyle f (hacha)}$ (donde ) $un \ neq 0$	$X$	$f^{}\left({\frac {x^{}}{a}}\right)$	$X^{*}$
${\ estilo de visualización f (x + b)}$	$X$	$f^{}(x^{})-\langle b,x^{*}\rangle$	$X^{*}$
${\ estilo de visualización af (x)}$ (donde ) $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}}$ (donde ) $pag>1$	$\matemáticas {R}$	${\frac {\|x^{*}\|^{q}}{q}}$ (donde ) ${\frac{1}{p}}+{\frac{1}{q}}=1$	$\matemáticas {R}$
${\frac{-x^{p}}{p}}$ (donde ) $0<p<1$	${\ estilo de visualización \ mathbb {R} _ {+)}$	${\frac {-(-x^{*})^{q}}{q}}$ (donde ) ${\frac{1}{p}}+{\frac{1}{q}}=1$	${\ estilo de visualización \ mathbb {R} _ {-}}$
${\ estilo de visualización {\ sqrt {1 + x ^ {2}}}}$	$\matemáticas {R}$	${\displaystyle -{\sqrt {1-(x^{*})^{2))))$	$[-1,1]$
${\ estilo de visualización - \ registro (x)}$	${\ estilo de visualización \ mathbb {R} _ {++}}$	$-(1+\log(-x^{*}))$	${\ estilo de visualización \ mathbb {R} _ {--}}$
$e^{x}$	$\matemáticas {R}$	${\begin{casos}x^{}\log(x^{})-x^{}&{\text{if }}x^{}>0\\0&{\text {si}}x^{*}=0\end{casos}}$	${\ estilo de visualización \ mathbb {R} _ {+)}$
${\ estilo de visualización \ registro \ izquierda (1 + e ^ {x} \ derecha)}$	$\matemáticas {R}$	${\begin{casos}x^{}\log(x^{})+(1-x^{})\log(1-x^{})&{\text{si }}0<x^{}<1\\0&{\text{if }}x^{}=0,1\end{casos}}$	$[0,1]$
$-\log \left(1-e^{x}\right)$	$\matemáticas {R}$	${\begin{casos}x^{}\log(x^{})-(1+x^{})\log(1+x^{})&{\text{si }}x^{}>0\\0&{\text{si }}x^{}=0\end{casos}}$	${\ estilo de visualización \ mathbb {R} _ {+)}$

Véase también

Notas

↑ Transformación de Legendre . Consultado el 14 de abril de 2019. Archivado desde el original el 28 de julio de 2020. (indefinido)
↑ Frank Nielsen. Transformación de Legendre y geometría de la información . Consultado el 19 de abril de 2019. Archivado desde el original el 11 de noviembre de 2013. (indefinido)
↑ Phelps, 1991 , pág. 42.
↑ Bauschke, Goebel, Lucet, Wang, 2008 , pág. 766.
↑ Ioffe, Tikhomirov, 1974 , p. declaración 3.4.3.
↑ Borwein y Lewis, 2006 , pág. 50–51.

Literatura

Roberto R. Phelps. Funciones Convexas, Operadores Monótonos y Diferenciabilidad. - Springer, 1991. - ISBN 0-387-56715-1 .
Heinz H. Bauschke, Rafal Goebel, Yves Lucet, Xianfu Wang. El Promedio Proximal: Teoría Básica // SIAM Journal on Optimization. - 2008. - T. 19 , nº. 2 . -doi : 10.1137/ 070687542 .
Ioffe A. D., Tikhomirov V. M. Teoría de problemas extremos. - M. : "Nauka", 1974.
Jonathan Borwein, Adrián Lewis. Análisis Convexo y Optimización No Lineal: Teoría y Ejemplos. - Springer, 2006. - ISBN 978-0-387-29570-1 .
Vladímir Igorevich Arnold. Métodos matemáticos de la mecánica clásica. - M. : "Nauka", 1989.
R. Tyrrell Rockafellar. Análisis convexo . - Princeton: Princeton University Press, 1970. - ISBN 0-691-01586-4 .

Enlaces

Touchette, Hugo Legendre-Fenchel se transforma en pocas palabras (PDF) (enlace no disponible) (16 de octubre de 2014). Consultado el 9 de enero de 2017. Archivado desde el original el 7 de abril de 2017. (indefinido)
Touchette, Hugo Elementos de análisis convexo (PDF) (enlace no disponible) (21 de noviembre de 2006). Consultado el 26 de marzo de 2008. Archivado desde el original el 26 de mayo de 2015. (indefinido)
Transformaciones de Legendre y Legendre-Fenchel en una explicación paso a paso . Recuperado: 18 de mayo de 2013. (indefinido)