Función autoconcordante

En optimización , una función autoconcordante es una función ${\displaystyle f:\mathbb {R} \rightarrow \mathbb {R} }$ para cual

${\displaystyle |f'''(x)|\leq 2f''(x)^{3/2}}$

o, de manera equivalente, una función ${\displaystyle f:\mathbb {R} \rightarrow \mathbb {R} }$ que, donde sea ${\displaystyle f''(x)>0}$, satisface

${\displaystyle \left|{\frac {d}{dx}}{\frac {1}{\sqrt {f''(x)}}}\right|\leq 1}$

y que satisface ${\displaystyle f'''(x)=0}$ en otra parte.

De manera más general, una función multivariante ${\displaystyle f(x):\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ es autoconcordante si

${\displaystyle \left.{\frac {d}{d\alpha }}\nabla ^{2}f(x+\alpha y)\right|_{\alpha =0}\preceq 2{\sqrt {y^{T}\nabla ^{2}f(x)\,y}}\,\nabla ^{2}f(x)}$

o, de manera equivalente, si su restricción a cualquier línea arbitraria es autoconcordante. ^[1]

Historia

Como se menciona en los "Comentarios bibliográficos" ^[2] de su libro de 1994, ^[3] las funciones autoconcordantes fueron introducidas en 1988 por Yurii Nesterov ^{[4] [5]} y desarrolladas con Arkadi Nemirovski . ^[6] Como se explica en ^[7], su observación básica fue que el método de Newton es invariante afín, en el sentido de que si para una función${\displaystyle f(x)}$ tenemos pasos de Newton ${\displaystyle x_{k+1}=x_{k}-[f''(x_{k})]^{-1}f'(x_{k})}$ luego para una función ${\displaystyle \phi (y)=f(Ay)}$ donde ${\displaystyle A}$ es una transformación lineal no degenerada, a partir de ${\displaystyle y_{0}=A^{-1}x_{0}}$ tenemos los pasos de Newton ${\displaystyle y_{k}=A^{-1}x_{k}}$ que se puede mostrar de forma recursiva

${\displaystyle y_{k+1}=y_{k}-[\phi ''(y_{k})]^{-1}\phi '(y_{k})=y_{k}-[A^{T}f''(Ay_{k})A]^{-1}A^{T}f'(Ay_{k})=A^{-1}x_{k}-A^{-1}[f''(x_{k})]^{-1}f'(x_{k})=A^{-1}x_{k+1}}$.

Sin embargo, el análisis estándar del método de Newton supone que el hessiano de ${\displaystyle f}$es Lipschitz continuo , es decir${\displaystyle \|f''(x)-f''(y)\|\leq M\|x-y\|}$ por alguna constante ${\displaystyle M}$. Si suponemos que${\displaystyle f}$ es 3 veces continuamente diferenciable, entonces esto es equivalente a

${\displaystyle |\langle f'''(x)[u]v,v\rangle |\leq M\|u\|\|v\|^{2}}$para todos ${\displaystyle u,v\in \mathbb {R} ^{n}}$

donde ${\displaystyle f'''(x)[u]=\lim _{\alpha \to 0}\alpha ^{-1}[f''(x+\alpha u)-f''(x)]}$. Entonces el lado izquierdo de la desigualdad anterior es invariante bajo la transformación afín${\displaystyle f(x)\to \phi (y)=f(Ay),u\to A^{-1}u,v\to A^{-1}v}$, sin embargo, el lado derecho no lo es.

Los autores señalan que el lado derecho también se puede hacer invariante si reemplazamos la métrica euclidiana por el producto escalar definido por el hessiano de ${\displaystyle f}$ definido como ${\displaystyle \|w\|_{f''(x)}=\langle f''(x)w,w\rangle ^{1/2}}$ por ${\displaystyle w\in \mathbb {R} ^{n}}$. Luego llegan a la definición de una función autoconcordante como

${\displaystyle |\langle f'''(x)[u]u,u\rangle |\leq M\langle f''(x)u,u\rangle ^{3/2}}$.

Propiedades

Combinación lineal

Si ${\displaystyle f_{1}}$ y ${\displaystyle f_{2}}$ son autoconcordantes con las constantes ${\displaystyle M_{1}}$ y ${\displaystyle M_{2}}$ y ${\displaystyle \alpha ,\beta >0}$, luego ${\displaystyle \alpha f_{1}+\beta f_{2}}$ es autoconcordante con la constante ${\displaystyle \max(\alpha ^{-1/2}M_{1},\beta ^{-1/2}M_{2})}$.

Transformación afín

Si ${\displaystyle f}$ es autoconcordante con la constante ${\displaystyle M}$ y ${\displaystyle Ax+b}$ es una transformación afín de ${\displaystyle \mathbb {R} ^{n}}$, luego ${\displaystyle \phi (x)=f(Ax+b)}$ también es autoconcordante con el parámetro ${\displaystyle M}$.

Hesse no singular

Si ${\displaystyle f}$ es autoconcordante y el dominio de ${\displaystyle f}$ no contiene una línea recta (infinita en ambas direcciones), entonces ${\displaystyle f''}$ no es singular.

Por el contrario, si para algunos ${\displaystyle x}$ en el dominio de ${\displaystyle f}$ y ${\displaystyle u\in \mathbb {R} ^{n},u\neq 0}$ tenemos ${\displaystyle \langle f''(x)u,u\rangle =0}$, luego ${\displaystyle \langle f''(x+\alpha u)u,u\rangle =0}$ para todos ${\displaystyle \alpha }$ para cual ${\displaystyle x+\alpha u}$ está en el dominio de ${\displaystyle f}$ y luego ${\displaystyle f(x+\alpha u)}$ es lineal y no puede tener un máximo, por lo que todos ${\displaystyle x+\alpha u,\alpha \in \mathbb {R} }$ está en el dominio de ${\displaystyle f}$. También notamos que${\displaystyle f}$ no puede tener un mínimo dentro de su dominio.

Aplicaciones

Entre otras cosas, las funciones autoconcordantes son útiles en el análisis del método de Newton . Las funciones de barrera autoconcordantes se utilizan para desarrollar las funciones de barrera utilizadas en los métodos de puntos interiores para la optimización convexa y no lineal. El análisis habitual del método de Newton no funcionaría para las funciones de barrera ya que su segunda derivada no puede ser continua de Lipschitz, de lo contrario estarían delimitadas en cualquier subconjunto compacto de${\displaystyle \mathbb {R} ^{n}}$.

Funciones de barrera autoconcordantes

• son una clase de funciones que pueden usarse como barreras en métodos de optimización restringidos
• se puede minimizar utilizando el algoritmo de Newton con propiedades de convergencia comprobables análogas al caso habitual (pero estos resultados son algo más difíciles de derivar)
• para tener ambos de los anteriores, la cota constante habitual en la tercera derivada de la función (requerida para obtener los resultados de convergencia habituales para el método de Newton) se reemplaza por una cota relativa al hessiano

Minimizar una función autoconcordante

Una función autoconcordante puede minimizarse con un método de Newton modificado donde tenemos un límite en el número de pasos requeridos para la convergencia. Suponemos aquí que${\displaystyle f}$es una función autoconcordante estándar , es decir, es autoconcordante con el parámetro${\displaystyle M=2}$.

Definimos el decremento de Newton ${\displaystyle \lambda _{f}(x)}$ de ${\displaystyle f}$ a ${\displaystyle x}$ como el tamaño del paso de Newton ${\displaystyle [f''(x)]^{-1}f'(x)}$ en la norma local definida por el hessiano de ${\displaystyle f}$ a ${\displaystyle x}$

${\displaystyle \lambda _{f}(x)=\langle f''(x)[f''(x)]^{-1}f'(x),[f''(x)]^{-1}f'(x)\rangle ^{1/2}=\langle [f''(x)]^{-1}f'(x),f'(x)\rangle ^{1/2}}$

Entonces para ${\displaystyle x}$ en el dominio de ${\displaystyle f}$, Si ${\displaystyle \lambda _{f}(x)<1}$ entonces es posible probar que Newton itera

${\displaystyle x_{+}=x-[f''(x)]^{-1}f'(x)}$

estará también en el dominio de ${\displaystyle f}$. Esto se debe a que, basado en la autoconcordancia de${\displaystyle f}$, es posible dar algunos límites finitos en el valor de ${\displaystyle f(x_{+})}$. Además tenemos

${\displaystyle \lambda _{f}(x_{+})\leq {\Bigg (}{\frac {\lambda _{f}(x)}{1-\lambda _{f}(x)}}{\Bigg )}^{2}}$

Entonces si tenemos

${\displaystyle \lambda _{f}(x)<{\bar {\lambda }}={\frac {3-{\sqrt {5}}}{2}}}$

entonces también se garantiza que ${\displaystyle \lambda _{f}(x_{+})<\lambda _{f}(x)}$, de modo que podamos seguir usando el método de Newton hasta la convergencia. Tenga en cuenta que para${\displaystyle \lambda _{f}(x_{+})<\beta }$ para algunos ${\displaystyle \beta \in (0,{\bar {\lambda }})}$ tenemos convergencia cuadrática de ${\displaystyle \lambda _{f}}$ a 0 como ${\displaystyle \lambda _{f}(x_{+})\leq (1-\beta )^{-2}\lambda _{f}(x)^{2}}$. Esto entonces da una convergencia cuadrática de${\displaystyle f(x_{k})}$ para ${\displaystyle f(x^{*})}$ y de ${\displaystyle x}$ para ${\displaystyle x^{*}}$, donde ${\displaystyle x^{*}=\arg \min f(x)}$, por el siguiente teorema. Si${\displaystyle \lambda _{f}(x)<1}$ luego

${\displaystyle \omega (\lambda _{f}(x))\leq f(x)-f(x^{*})\leq \omega _{*}(\lambda _{f}(x))}$

${\displaystyle \omega '(\lambda _{f}(x))\leq \|x-x^{*}\|_{x}\leq \omega _{*}'(\lambda _{f}(x))}$

con las siguientes definiciones

${\displaystyle \omega (t)=t-\log(1+t)}$

${\displaystyle \omega _{*}(t)=-t-\log(1-t)}$

${\displaystyle \|u\|_{x}=\langle f''(x)u,u\rangle ^{1/2}}$

Si comenzamos el método de Newton de alguna ${\displaystyle x_{0}}$ con ${\displaystyle \lambda _{f}(x_{0})\geq {\bar {\lambda }}}$entonces tenemos que empezar usando un método de Newton amortiguado definido por

${\displaystyle x_{k+1}=x_{k}-{\frac {1}{1+\lambda _{f}(x_{k})}}[f''(x_{k})]^{-1}f'(x_{k})}$

Para esto se puede demostrar que ${\displaystyle f(x_{k+1})\leq f(x_{k})-\omega (\lambda _{f}(x_{k}))}$ con ${\displaystyle \omega }$como se definió anteriormente. Tenga en cuenta que${\displaystyle \omega (t)}$ es una función creciente para ${\displaystyle t>0}$ así que eso ${\displaystyle \omega (t)\geq \omega ({\bar {\lambda }})}$ para cualquier ${\displaystyle t\geq {\bar {\lambda }}}$, entonces el valor de ${\displaystyle f}$ está garantizado que disminuirá en una cierta cantidad en cada iteración, lo que también prueba que ${\displaystyle x_{k+1}}$ está en el dominio de ${\displaystyle f}$.

Ejemplos

Funciones autoconcordantes

• Las funciones cuadráticas lineales y convexas son autoconcordantes con ${\displaystyle M=0}$ ya que su tercera derivada es cero.
• Cualquier función ${\displaystyle f(x)=-\log(-g(x))-\log x}$ donde ${\displaystyle g(x)}$ está definido y convexo para todos ${\displaystyle x>0}$ y verifica ${\displaystyle |g'''(x)|\leq 3g''(x)/x}$, es auto concordante en su dominio que es ${\displaystyle \{x\mid x>0,g(x)<0\}}$. Algunos ejemplos son
  • ${\displaystyle g(x)=-x^{p}}$ por ${\displaystyle 0<p\leq 1}$
  • ${\displaystyle g(x)=-\log x}$
  • ${\displaystyle g(x)=x^{p}}$ por ${\displaystyle -1\leq p\leq 0}$
  • ${\displaystyle g(x)=(ax+b)^{2}/x}$
  • para cualquier función ${\displaystyle g}$ satisfaciendo las condiciones, la función ${\displaystyle g(x)+ax^{2}+bx+c}$ con ${\displaystyle a\geq 0}$ también cumple las condiciones

Funciones que no son autoconcordantes

• ${\displaystyle f(x)=e^{x}}$
• ${\displaystyle f(x)={\frac {1}{x^{p}}},x>0,p>0}$
• ${\displaystyle f(x)=|x^{p}|,p>2}$

Barreras autoconcordantes

• media línea positiva ${\displaystyle \mathbb {R} _{+}}$: ${\displaystyle f(x)=-\log x}$ con dominio ${\displaystyle x>0}$ es una barrera autoconcordante con ${\displaystyle M=2}$.
• orthant positivo ${\displaystyle \mathbb {R} _{+}^{n}}$: ${\displaystyle f(x)=-\sum _{i=1}^{n}\log x_{i}}$ con ${\displaystyle M=n}$
• la barrera logarítmica ${\displaystyle f(x)=\log \phi (x)}$ para la región cuadrática definida por ${\displaystyle \phi (x)>0}$ donde ${\displaystyle \phi (x)=\alpha +\langle a,x\rangle -{\frac {1}{2}}\langle Ax,x\rangle }$ donde ${\displaystyle A=A^{T}\geq 0}$es un semi-definido matriz simétrica es auto-concordantes para${\displaystyle M=2}$
• cono de segundo orden ${\displaystyle \{(x,y)\in \mathbb {R} ^{n-1}\times \mathbb {R} \mid \|x\|\leq y\}}$: ${\displaystyle f(x,y)=-\log(y^{2}-x^{T}x)}$
• cono semi-definido ${\displaystyle A=A^{T}\geq 0}$: ${\displaystyle f(A)=-\log \det A}$
• cono exponencial ${\displaystyle \{(x,y,z)\in \mathbb {R} ^{3}\mid ye^{x/y}\leq z,y>0\}}$: ${\displaystyle f(x,y,z)=-\log(y\log(z/y)-x)-\log z-\log y}$
• cono de poder ${\displaystyle \{(x_{1},x_{2},y)\in \mathbb {R} _{+}^{2}\times \mathbb {R} \mid |y|\leq x_{1}^{\alpha }x_{2}^{1-\alpha }\}}$: ${\displaystyle f(x_{1},x_{2},y)=-\log(x_{1}^{2\alpha }x_{2}^{2(1-\alpha )}-y^{2})-\log x_{1}-\log x_{2}}$

Referencias

1. Boyd, Stephen P .; Vandenberghe, Lieven (2004). Optimización convexa (pdf) . Prensa de la Universidad de Cambridge. ISBN 978-0-521-83378-3. Consultado el 15 de octubre de 2011 .
2. Nesterov, Yurii; Nemirovskii, Arkadii (enero de 1994). Algoritmos polinomiales de punto interior en programación convexa (comentarios de bibliografía) . Sociedad de Matemáticas Industriales y Aplicadas. doi : 10.1137 / 1.9781611970791.bm . ISBN 978-0-89871-319-0.
3. Nesterov, I︠U︡. E. (1994). Algoritmos polinomiales de punto interior en programación convexa . Nemirovskiĭ, Arkadiĭ Semenovich. Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas. ISBN 0-89871-319-6. OCLC  29310677 .
4. Yu. E. NESTEROV, Métodos de tiempo polinomial en programación lineal y cuadrática, Izvestija AN SSSR, Tekhnitcheskaya kibernetika, No. 3, 1988, págs. 324-326. (En ruso.)
5. Yu. E. NESTEROV, Métodos iterativos de tiempo polinómico en programación lineal y cuadrática, Voprosy kibernetiki, Moscú, 1988, págs. 102-125. (En ruso.)
6. YE Nesterov y AS Nemirovski, Funciones autoconcordantes y métodos de tiempo polinómico en programación convexa, Informe técnico, Instituto Central de Economía y Matemáticas, Academia de Ciencias de la URSS, Moscú, URSS, 1989.
7. Nesterov, I︠U︡. E. Conferencias introductorias sobre optimización convexa: un curso básico . Bostón. ISBN 978-1-4419-8853-9. OCLC  883391994 .

Este artículo relacionado con las matemáticas aplicadas es un fragmento . Puedes ayudar a Wikipedia expandiéndolo .

• v
• t
• mi