The Symmetric Rank 1 (SR1) method is a

quasi-Newton method Quasi-Newton methods are methods used to either find zeroes or local maxima and minima of functions, as an alternative to Newton's method. They can be used if the Jacobian or Hessian is unavailable or is too expensive to compute at every iteration ...

to update the second derivative (Hessian) based on the derivatives (gradients) calculated at two points. It is a generalization to the

secant method In numerical analysis, the secant method is a root-finding algorithm that uses a succession of roots of secant lines to better approximate a root of a function ''f''. The secant method can be thought of as a finite-difference approximation ...

for a multidimensional problem. This update maintains the ''symmetry'' of the matrix but does ''not'' guarantee that the update be ''positive definite''. The sequence of Hessian approximations generated by the SR1 method converges to the true Hessian under mild conditions, in theory; in practice, the approximate Hessians generated by the SR1 method show faster progress towards the true Hessian than do popular alternatives ( BFGS or DFP), in preliminary numerical experiments. The SR1 method has computational advantages for

sparse Sparse is a computer software tool designed to find possible coding faults in the Linux kernel. Unlike other such tools, this static analysis tool was initially designed to only flag constructs that were likely to be of interest to kernel de ...

or partially separable problems. A twice continuously differentiable function

x \mapsto f(x)

has a

gradient In vector calculus, the gradient of a scalar-valued differentiable function of several variables is the vector field (or vector-valued function) \nabla f whose value at a point p is the "direction and rate of fastest increase". If the gr ...

(

\nabla f

) and

Hessian matrix In mathematics, the Hessian matrix or Hessian is a square matrix of second-order partial derivatives of a scalar-valued function, or scalar field. It describes the local curvature of a function of many variables. The Hessian matrix was developed ...

B

: The function

f

has an expansion as a

Taylor series In mathematics, the Taylor series or Taylor expansion of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common functions, the function and the sum of its Taylor se ...

x_0

, which can be truncated ::

f(x_0+\Delta x) \approx f(x_0)+\nabla f(x_0)^T \Delta x+\frac \Delta x^T  \Delta x

; its gradient has a Taylor-series approximation also ::

\nabla f(x_0+\Delta x) \approx \nabla f(x_0)+B \Delta x

, which is used to update

B

. The above secant-equation need not have a unique solution

B

. The SR1 formula computes (via an update of

rank Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as: Level or position in a hierarchical organization * Academic rank * Diplomatic rank * Hierarchy * H ...

1) the symmetric solution that is closest to the current approximate-value

B_k

: ::

B_=B_+\frac

, where ::

y_k=\nabla f(x_k+\Delta x_k)-\nabla f(x_k)

. The corresponding update to the approximate inverse-Hessian

H_k=B_k^

is ::

H_=H_+\frac

. One might wonder why positive-definiteness is not preserved — after all, a rank-1 update of the form

B_ = B_k + vv^T

is positive-definite if

B_k

is. The explanation is that the update might be of the form

B_ = B_k - vv^T

instead because the denominator can be negative, and in that case there are no guarantees about positive-definiteness. The SR1 formula has been rediscovered a number of times. A drawback is that the denominator can vanish. Some authors have suggested that the update be applied 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

r\in(0,1)

is a small number, e.g.

10^

References

{{Optimization algorithms, unconstrained Quasi-Newton methods

See also

References