Rango uno simétrico

El método Symmetric Rank 1 ( SR1 ) es un método cuasi-Newton para actualizar la segunda derivada (hessiana) en función de las derivadas (gradientes) calculadas en dos puntos. Es una generalización del método de la secante para un problema multidimensional. Esta actualización mantiene la simetría de la matriz pero no garantiza que la actualización sea positiva definida .

La secuencia de aproximaciones hessianas generadas por el método SR1 converge al verdadero hessiano en condiciones suaves, en teoría; en la práctica, los hessianos aproximados generados por el método SR1 muestran un progreso más rápido hacia el hessiano verdadero que las alternativas populares ( BFGS o DFP ), en experimentos numéricos preliminares. ^{[1] [2]} El método SR1 tiene ventajas computacionales para problemas dispersos o parcialmente separables . ^[3]

Una función dos veces diferenciable de forma continua ${\displaystyle x\mapsto f(x)}$tiene un gradiente (${\displaystyle \nabla f}$) y matriz de Hesse ${\displaystyle B}$: La función ${\displaystyle f}$tiene una expansión como una serie de Taylor en${\displaystyle x_{0}}$, que se puede truncar

${\displaystyle f(x_{0}+\Delta x)\approx f(x_{0})+\nabla f(x_{0})^{T}\Delta x+{\frac {1}{2}}\Delta x^{T}{B}\Delta x}$;

su gradiente tiene una aproximación de la serie de Taylor también

${\displaystyle \nabla f(x_{0}+\Delta x)\approx \nabla f(x_{0})+B\Delta x}$,

que se usa para actualizar ${\displaystyle B}$. La ecuación de la secante anterior no necesita tener una solución única ${\displaystyle B}$. La fórmula SR1 calcula (mediante una actualización del rango 1) la solución simétrica más cercana al valor aproximado actual ${\displaystyle B_{k}}$:

${\displaystyle B_{k+1}=B_{k}+{\frac {(y_{k}-B_{k}\Delta x_{k})(y_{k}-B_{k}\Delta x_{k})^{T}}{(y_{k}-B_{k}\Delta x_{k})^{T}\Delta x_{k}}}}$,

donde

${\displaystyle y_{k}=\nabla f(x_{k}+\Delta x_{k})-\nabla f(x_{k})}$.

La actualización correspondiente al hessiano inverso aproximado ${\displaystyle H_{k}=B_{k}^{-1}}$ es

${\displaystyle H_{k+1}=H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})(\Delta x_{k}-H_{k}y_{k})^{T}}{(\Delta x_{k}-H_{k}y_{k})^{T}y_{k}}}}$.

La fórmula SR1 se ha redescubierto varias veces. Un inconveniente es que el denominador puede desaparecer. Algunos autores han sugerido que la actualización se aplique solo si

${\displaystyle |\Delta x_{k}^{T}(y_{k}-B_{k}\Delta x_{k})|\geq r\|\Delta x_{k}\|\cdot \|y_{k}-B_{k}\Delta x_{k}\|}$,

donde ${\displaystyle r\in (0,1)}$ es un número pequeño, p. ej. ${\displaystyle 10^{-8}}$. ^[4]

Ver también

• Método cuasi-Newton
• El método de Broyden
• El método de Newton en optimización
• Método de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
• Método L-BFGS

Referencias

1. Conn, AR; Gould, NIM; Toint, Ph. L. (marzo de 1991). "Convergencia de matrices de cuasi-Newton generadas por la actualización simétrica de rango uno". Programación matemática . Springer Berlín / Heidelberg. 50 (1): 177-195. doi : 10.1007 / BF01594934 . ISSN  0025-5610 .
2. Khalfan, H. Fayez; et al. (1993). "Un estudio teórico y experimental de la actualización simétrica de Rank-One". Revista SIAM de Optimización . 3 (1): 1–24. doi : 10.1137 / 0803001 .
3. Byrd, Richard H .; et al. (1996). "Análisis de un método de región de confianza de rango uno simétrico". Revista SIAM de Optimización . 6 (4): 1025–1039. doi : 10.1137 / S1052623493252985 .
4. Nocedal, Jorge; Wright, Stephen J. (1999). Optimización numérica . Saltador. ISBN 0-387-98793-2.