Broyden's method

In numerical analysis,Broyden's methodis aquasi-Newton methodforfinding rootsinkvariables. It was originally described byC. G. Broydenin 1965.

Newton's methodfor solvingf(x) =0uses theJacobian matrix,J,at every iteration. However, computing this Jacobian can be a difficult and expensive operation; for large problems such as those involving solving theKohn–Sham equationsinquantum mechanicsthe number of variables can be in the hundreds of thousands. The idea behind Broyden's method is to compute the whole Jacobian at most only at the first iteration, and to do rank-one updates at other iterations.

In 1979 Gay proved that when Broyden's method is applied to a linear system of sizen×n,it terminates in2nsteps,although like all quasi-Newton methods, it may not converge for nonlinear systems.

Description of the method

Solving single-variable nonlinear equation

In thesecant method,we replace the first derivativef′atx_nwith thefinite-differenceapproximation:

$f'(x_{n})\simeq {\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}},$

and proceed similar toNewton's method:

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f^{\prime }(x_{n})}}$

wherenis the iteration index.

Solving a system of nonlinear equations

Consider a system ofknonlinear equations in$k$unknowns

$\mathbf {f} (\mathbf {x} )=\mathbf {0},$

wherefis a vector-valued function of vectorx

$\mathbf {x} =(x_{1},x_{2},x_{3},\dotsc,x_{k}),$

$\mathbf {f} (\mathbf {x} )={\big (}f_{1}(x_{1},x_{2},\dotsc,x_{k}),f_{2}(x_{1},x_{2},\dotsc,x_{k}),\dotsc,f_{k}(x_{1},x_{2},\dotsc,x_{k}){\big )}.$

For such problems, Broyden gives a variation of the one-dimensional Newton's method, replacing the derivative with an approximateJacobianJ.The approximate Jacobian matrix is determined iteratively based on thesecant equation,a finite-difference approximation:

$\mathbf {J} _{n}(\mathbf {x} _{n}-\mathbf {x} _{n-1})\simeq \mathbf {f} (\mathbf {x} _{n})-\mathbf {f} (\mathbf {x} _{n-1}),$

wherenis the iteration index. For clarity, define

$\mathbf {f} _{n}=\mathbf {f} (\mathbf {x} _{n}),$

$\Delta \mathbf {x} _{n}=\mathbf {x} _{n}-\mathbf {x} _{n-1},$

$\Delta \mathbf {f} _{n}=\mathbf {f} _{n}-\mathbf {f} _{n-1},$

so the above may be rewritten as

$\mathbf {J} _{n}\Delta \mathbf {x} _{n}\simeq \Delta \mathbf {f} _{n}.$

The above equation isunderdeterminedwhenkis greater than one. Broyden suggested using the most recent estimate of the Jacobian matrix,J_n−1,and then improving upon it by requiring that the new form is a solution to the most recent secant equation, and that there is minimal modification toJ_n−1:

$\mathbf {J} _{n}=\mathbf {J} _{n-1}+{\frac {\Delta \mathbf {f} _{n}-\mathbf {J} _{n-1}\Delta \mathbf {x} _{n}}{\|\Delta \mathbf {x} _{n}\|^{2}}}\Delta \mathbf {x} _{n}^{\mathrm {T} }.$

This minimizes theFrobenius norm

$\|\mathbf {J} _{n}-\mathbf {J} _{n-1}\|_{\rm {F}}.$

One then updates the variables using the approximate Jacobian, what is called a quasi-Newton approach.

$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\alpha \mathbf {J} _{n}^{-1}\mathbf {f} (\mathbf {x} _{n}).$

If$\alpha =1$this is the full Newton step; commonly aline searchortrust regionmethod is used to control$\alpha$.The initial Jacobian can be taken as a diagonal, unit matrix, although more common is to scale it based upon the first step.Broyden also suggested using theSherman–Morrison formulato directly update the inverse of the approximate Jacobian matrix:

$\mathbf {J} _{n}^{-1}=\mathbf {J} _{n-1}^{-1}+{\frac {\Delta \mathbf {x} _{n}-\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}{\Delta \mathbf {x} _{n}^{\mathrm {T} }\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}}\Delta \mathbf {x} _{n}^{\mathrm {T} }\mathbf {J} _{n-1}^{-1}.$

This first method is commonly known as the "good Broyden's method."

A similar technique can be derived by using a slightly different modification toJ_n−1.This yields a second method, the so-called "bad Broyden's method":

$\mathbf {J} _{n}^{-1}=\mathbf {J} _{n-1}^{-1}+{\frac {\Delta \mathbf {x} _{n}-\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}{\|\Delta \mathbf {f} _{n}\|^{2}}}\Delta \mathbf {f} _{n}^{\mathrm {T} }.$

This minimizes a different Frobenius norm

$\|\mathbf {J} _{n}^{-1}-\mathbf {J} _{n-1}^{-1}\|_{\rm {F}}.$

In his original paper Broyden could not get the bad method to work, but there are cases where it doesfor which several explanations have been proposed.Many other quasi-Newton schemes have been suggested inoptimizationsuch as theBFGS,where one seeks a maximum or minimum by finding zeros of the first derivatives (zeros of thegradientin multiple dimensions). The Jacobian of the gradient is called theHessianand is symmetric, adding further constraints to its approximation.

The Broyden Class of Methods

In addition to the two methods described above, Broyden defined a wider class of related methods.In general, methods in theBroyden classare given in the form $$\mathbf {J} _{k+1}=\mathbf {J} _{k}-{\frac {\mathbf {J} _{k}s_{k}s_{k}^{T}\mathbf {J} _{k}}{s_{k}^{T}\mathbf {J} _{k}s_{k}}}+{\frac {y_{k}y_{k}^{T}}{y_{k}^{T}s_{k}}}+\phi _{k}\left(s_{k}^{T}\mathbf {J} _{k}s_{k}\right)v_{k}v_{k}^{T},$$ where$y_{k}:=\mathbf {f} (\mathbf {x} _{k+1})-\mathbf {f} (\mathbf {x} _{k}),$$s_{k}:=\mathbf {x} _{k+1}-\mathbf {x} _{k},$and$$v_{k}=\left[{\frac {y_{k}}{y_{k}^{T}s_{k}}}-{\frac {\mathbf {J} _{k}s_{k}}{s_{k}^{T}\mathbf {J} _{k}s_{k}}}\right],$$ and$\phi _{k}\in \mathbb {R}$for each$k=1,2,...$. The choice of$\phi _{k}$determines the method.

Other methods in the Broyden class have been introduced by other authors.

• TheDavidon–Fletcher–Powell (DFP) method,which is the only member of this class being published before the two methods defined by Broyden.For the DFP method,$\phi _{k}=1$.
• Anderson's iterative method, which uses a least squares approach to the Jacobian.
• Schubert's or sparse Broyden algorithm – a modification for sparse Jacobian matrices.
• The Pulay approach, often used indensity functional theory.
• A limited memory method by Srivastava for the root finding problem which only uses a few recent iterations.
• Klement (2014) – uses fewer iterations to solve some systems.
• Multisecant methods fordensity functional theoryproblems

See also

• Secant method
• Newton's method
• Quasi-Newton method
• Newton's method in optimization
• Davidon–Fletcher–Powell formula
• Broyden–Fletcher–Goldfarb–Shanno (BFGS) method

Further reading

• Dennis, J. E.;Schnabel, Robert B.(1983).Numerical Methods for Unconstrained Optimization and Nonlinear Equations.Englewood Cliffs: Prentice Hall. pp. 168–193.ISBN0-13-627216-9.
• Fletcher, R. (1987).Practical Methods of Optimization(Second ed.). New York: John Wiley & Sons. pp.44–79.ISBN0-471-91547-5.
• Kelley, C. T. (1995).Iterative Methods for Linear and Nonlinear Equations.Society for Industrial and Applied Mathematics.doi:10.1137/1.9781611970944.ISBN978-0-89871-352-7.

External links

• Simple basic explanation: The story of the blind archer