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 o ...
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 or
partially separable problems.
A twice continuously differentiable function
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 ...
(
) 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 ...
: The function
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 ser ...
at
, which can be truncated
::
;
its gradient has a Taylor-series approximation also
::
,
which is used to update
. The above secant-equation need not have a unique solution
.
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
* ...
1) the symmetric solution that is closest to the current approximate-value
:
::
,
where
::
.
The corresponding update to the approximate inverse-Hessian
is
::
.
One might wonder why positive-definiteness is not preserved — after all, a rank-1 update of the form
is positive-definite if
is. The explanation is that the update might be of the form
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
::
,
where
is a small number, e.g.
.
See also
*
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. ...
*
Broyden's method
In numerical analysis, Broyden's method is a quasi-Newton method for finding roots in variables. It was originally described by C. G. Broyden in 1965.
Newton's method for solving uses the Jacobian matrix, , at every iteration. However, compu ...
*
Newton's method in optimization
In calculus, Newton's method is an iterative method for finding the roots of a differentiable function , which are solutions to the equation . As such, Newton's method can be applied to the derivative of a twice-differentiable function to fi ...
*
Broyden-Fletcher-Goldfarb-Shanno (BFGS) method
*
L-BFGS method
References
{{Optimization algorithms, unconstrained
Quasi-Newton methods