Rango uno simétrico

El método de rango simétrico 1 ( SR1 ) es un método cuasi-Newton para actualizar la segunda derivada (hessiana) a partir 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 sea definida positiva .

La secuencia de aproximaciones de la matriz hessiana generada por el método SR1 converge a la matriz hessiana verdadera bajo condiciones leves, en teoría; en la práctica, las matrices hessianas aproximadas generadas por el método SR1 muestran un progreso más rápido hacia la matriz hessiana verdadera 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${\displaystyle x\mapsto f(x)}$tiene un gradiente (${\displaystyle \nabla f}$) y matriz hessiana${\displaystyle B}$: La función${\displaystyle f}$tiene una expansión como serie Taylor en${\displaystyle x_{0}}$, que puede ser truncado

${\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${\displaystyle B}$La ecuación de la secante anterior no tiene por qué tener una solución única. ${\displaystyle B}$La fórmula SR1 calcula (mediante una actualización de rango 1) la solución simétrica que está más cerca del 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}}}}$,

dónde

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

La actualización correspondiente a la inversa aproximada de la matriz hessiana${\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}}}}$.

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

La fórmula SR1 se ha redescubierto varias veces. Dado 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}\|}$,

dónde${\displaystyle r\in (0,1)}$es un número pequeño, por ejemplo${\displaystyle 10^{-8}}$. ^{[ 4 ]}

La actualización SR1 mantiene una matriz densa, lo que puede ser prohibitivo para problemas grandes. 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 completa del Hessiano, un método L-SR1 solo almacena la${\displaystyle m}$pares más recientes${\displaystyle \{(s_{i},y_{i})\}_{i=km}^{k-1}}$, dónde${\displaystyle \Delta x_{i}:=s_{i}}$y${\displaystyle m}$es un número entero mucho menor que el tamaño del problema (${\displaystyle m\ll n}$La matriz de memoria limitada se basa en una representación matricial compacta .

$${\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_{km}&s_{k-m+1}&\ldots &s_{k-1}\end{bmatrix}},}$$$${\displaystyle Y_{k}={\begin{bmatrix}y_{km}&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})_{ii}=s_{i-1}^{T}y_{i-1},\quad km\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.

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