Rango uno simétrico

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

La secuencia de aproximaciones hessianas generadas por el método SR1 converge al hessiano verdadero en condiciones suaves, en teoría; en la práctica, las hessianas aproximadas generadas 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 continuamente diferenciable tiene un gradiente ( ) y una matriz hessiana : La función tiene una expansión como una serie de Taylor en , que se puede truncar ${\displaystyle x\mapsto f(x)}$ ${\displaystyle \nabla f}$ ${\displaystyle B}$ ${\displaystyle f}$ ${\displaystyle x_{0}}$

${\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 también tiene una aproximación de serie de Taylor.

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

que se utiliza para actualizar . La ecuación secante anterior no necesita tener una solución única . La fórmula SR1 calcula (mediante una actualización de rango 1) la solución simétrica más cercana ^{[ se necesita más explicación ]} al valor aproximado actual : ${\displaystyle B}$ ${\displaystyle B}$ ${\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}}}}$,

dónde

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

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

${\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}}}}$.

Uno podría preguntarse por qué no se conserva la definitividad positiva; después de todo, una actualización de rango 1 de la forma es positivamente definida si es. La explicación es que la actualización podría ser de la forma porque el denominador puede ser negativo y, en ese caso, no hay garantías sobre la definitividad positiva. ${\displaystyle B_{k+1}=B_{k}+vv^{T}}$ ${\displaystyle B_{k}}$ ${\displaystyle B_{k+1}=B_{k}-vv^{T}}$

La fórmula SR1 ha sido redescubierta varias veces. Como 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 es un número pequeño, p. ej . ^[4] ${\displaystyle r\in (0,1)}$ ${\displaystyle 10^{-8}}$

Memoria limitada

La actualización SR1 mantiene una matriz densa, lo que puede resultar prohibitivo para problemas grandes. De manera similar al método L-BFGS, también existe un algoritmo SR1 de memoria limitada (L-SR1). ^[5] En lugar de almacenar la aproximación hessiana completa, un método L-SR1 solo almacena los pares más recientes , donde y es un entero mucho más pequeño que el tamaño del problema ( ). La matriz de memoria limitada se basa en una representación matricial compacta. ${\displaystyle m}$ ${\displaystyle \{(s_{i},y_{i})\}_{i=k-m}^{k-1}}$ ${\displaystyle \Delta x_{i}:=s_{i}}$ ${\displaystyle m}$ ${\displaystyle m\ll n}$

$${\displaystyle B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T},\quad J_{k}=Y_{k}-B_{0}S_{k},\quad N_{k}=D_{k}+L_{k}+L_{k}^{T}-S_{k}^{T}B_{0}S_{k}}$$

$${\displaystyle S_{k}={\begin{bmatrix}s_{k-m}&s_{k-m+1}&\ldots &s_{k-1}\end{bmatrix}},}$$ $${\displaystyle Y_{k}={\begin{bmatrix}y_{k-m}&y_{k-m+1}&\ldots &y_{k-1}\end{bmatrix}},}$$

$${\displaystyle {\big (}L_{k}{\big )}_{ij}=s_{i-1}^{T}y_{j-1},\quad D_{k}=s_{i-1}^{T}y_{i-1},\quad k-m\leq i\leq k-1}$$

Dado que la actualización puede ser indefinida, el algoritmo L-SR1 es adecuado para una estrategia de región de confianza . Debido a la matriz de memoria limitada, el algoritmo L-SR1 de región de confianza escala linealmente con el tamaño del problema, al igual que L-BFGS.

Véase también

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

Referencias

1. Conn, AR; Gould, NIM; Toint, Ph. L. (marzo de 1991). "Convergencia de matrices cuasi-Newton generadas por la actualización simétrica de rango uno". Programación matemática . 50 (1). Springer Berlin/ Heidelberg: 177–195. doi :10.1007/BF01594934. ISSN  0025-5610. S2CID  28028770.
2. Khalfan, H. Fayez; et al. (1993). "Un estudio teórico y experimental de la actualización simétrica de rango uno". Revista SIAM sobre 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 sobre optimización . 6 (4): 1025–1039. doi :10.1137/S1052623493252985.
4. Nocedal, Jorge; Wright, Stephen J. (1999). Optimización numérica . Springer. ISBN 0-387-98793-2.
5. Brust, J.; et al. (2017). "Sobre la resolución de subproblemas de la región de confianza L-SR1". Optimización computacional y aplicaciones . 66 : 245–266. doi :10.1007/s10589-016-9868-3.