SR1 formula

From Wikipedia, the free encyclopedia

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 ( $\nabla f$ ), and Hessian matrix $B$ , the Taylor series is:

$f(x_0+\Delta x)=f(x_0)+\nabla f(x_0)^T \Delta x+\frac{1}{2} \Delta x^T {B} \Delta x$ ,

and the Taylor series of the gradient itself:

$\nabla f(x_0+\Delta x)=\nabla 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=\nabla f(x_k+\Delta x_k)-\nabla 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||$ ,