Quasi Newton Method
Quasi-Newton methodIt is an optimization method based on Newton's method, which is mainly used to solve the zero, maximum and minimum value problems of nonlinear equations or continuous functions.
When the Jacobian matrix in Newton's method or Hessian When the matrix is difficult or even impossible to calculate, the quasi-Newton method comes into play. It is one of the most effective methods for solving nonlinear optimization problems. The quasi-Newton method was first proposed by the United States. Argonne Physicist at the National Laboratory WCDavidon At 20 century 50 The era proposed.
The idea of quasi-Newton method
Newton's method solves Hessian When calculating the matrix, the inverse matrix must be calculated first, which will lead to a decrease in efficiency, but the quasi-Newton method uses a positive definite matrix to approximate Hessian The inverse matrix of the matrix is obtained, thereby reducing the algorithm complexity and improving the efficiency.
Common quasi-Newton algorithms
- DFP (Davidon-Fletcher-Powell) algorithm
In the DFP algorithm, we choose as an approximation of , assuming that in each iteration the matrix is composed of plus two additional terms, namely
in,
and
is a matrix to be determined. Then
To make
Satisfying the quasi-Newton condition, we canandsatisfy
Desirable
The matrixIterative formula
It can be proved that if the initial matrix
is positive definite, then each matrix in the iterative process
They are all positive.
- BFGS (Broyden-Fletcher-Goldfard-Shano) algorithm
DFP is aApproximating the inverse of the Hessian matrix
, while in the BFGS algorithm,
Approximation to the Hessian Matrix
, the corresponding quasi-Newton condition
Assume that in each iteration the matrix
IsPlus two additional terms, namely
in,andis a matrix to be determined. Then
To makeSatisfying the quasi-Newton condition, we canandsatisfy
Desirable
The matrixIterative formula
It can be proved that if the initial matrix
is positive definite, then each matrix in the iterative processThey are all positive.
- Broyden (Broyden's algorithm) type algorithm
We can get the BFGS algorithm matrixThe iterative formula of BFGS algorithm isIteration formula of .
remember
Applying the Sherman-Morrison formula twice, we get
It is called the BFGS algorithm.Iteration formula of .
The Sherman-Morrison formula: Assume
is an n-order reversible matrix,
is an n-dimensional vector, and
is also a reversible matrix, then:
Let the iterative formula obtained by the DFP algorithm beRecorded as
, according to the iterative formula of the BFGS algorithmWhat you getDenoted as, since and both satisfy the quasi-Newton condition, the linear combination of the two
It also satisfies the quasi-Newton condition and is positive definite.
. This type of algorithm is called Broyden type algorithm.