SR1 formula

The Symmetric Rank 1 method is a quasi-Newton method to update the second derivative (Hessian)based on the derivatives (gradients) calculated at two points. It is a generalization to the secant method for a multidimensional problem.This update maintains the symmetry of the matrix but does not guarantee the update to be a positive definite matrix.For this reason it is the method of choice for indefinite problems.

Given a function $f(x)$, its gradient ($abla\; f$), and Hessian matrix $B$, the Taylor series is:::$f(x\_0+Delta\; x)=f(x\_0)+\; abla\; f(x\_0)^T\; Delta\; x+frac\{1\}\{2\}\; Delta\; x^T\; \{B\}\; Delta\; x$,and the Taylor series of the gradient itself:::$abla\; f(x\_0+Delta\; x)=\; abla\; f(x\_0)+B\; Delta\; x$,is used to update $B$. Equation above (secant equation) can admit an infinite number of solutions to $B$. The SR1 formula finds a solution of rank 1 that is symmetric and closest to the current approximate value of $B\_k$:::$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\}$,where::$y=\; abla\; f(x\_k+Delta\; x\_k)-\; abla\; f(x\_k)$.The corresponding update to the inverse Hessian approximation $H\_k=B\_k^\{-1\}$ is given by:::$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\}$.

The derivation is simple, and the SR1 formula has been rediscovered a number of times.The main drawback is that the denominator can vanish. It is therefore a good idea to apply the SR1 update only if::$|Delta\; x\_k^T\; (y\_k-B\_k\; Delta\; x\_k)|geq\; r\; ||Delta\; x\_k||cdot\; ||y\_k-B\_k\; Delta\; x\_k||$,where $rin(0,1)$ is a small number, e.g. $10^\{-8\}$.

ee also

* Quasi-Newton method
* Newton's method in optimization
* Broyden-Fletcher-Goldfarb-Shanno (BFGS) method
* L-BFGS method

References

* Nocedal, Jorge & Wright, Stephen J. (1999). Numerical Optimization. Springer-Verlag. ISBN 0-387-98793-2.