Broyden's method

In numerical analysis, Broyden's method is a quasi-Newton method for finding roots in k variables. It was originally described by C. G. Broyden in 1965. ^[1]

Newton's method for solving f(x) = 0 uses the Jacobian matrix, J, at every iteration. However, computing this Jacobian can be a difficult and expensive operation; for large problems such as those involving solving the Kohn–Sham equations in quantum mechanics the 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 size n × n, it terminates in 2 n steps, ^[2] although like all quasi-Newton methods, it may not converge for nonlinear systems.

Description of the method

Solving single-variable nonlinear equation

In the secant method, we replace the first derivative f′ at x_n with the finite-difference approximation:

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

and proceed similar to Newton's method:

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

where n is the iteration index.

Solving a system of nonlinear equations

Consider a system of k nonlinear equations in ${\displaystyle k}$ unknowns

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

where f is a vector-valued function of vector x

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

${\displaystyle \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 approximate Jacobian J. The approximate Jacobian matrix is determined iteratively based on the secant equation, a finite-difference approximation:

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

where n is the iteration index. For clarity, define

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

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

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

so the above may be rewritten as

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

The above equation is underdetermined when k is 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 to J_n−1:

${\displaystyle \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 the Frobenius norm

${\displaystyle \|\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.

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

If ${\displaystyle \alpha =1}$ this is the full Newton step; commonly a line search or trust region method is used to control ${\displaystyle \alpha }$. The initial Jacobian can be taken as a diagonal, unit matrix, although more common is to scale it based upon the first step. ^[3] Broyden also suggested using the Sherman–Morrison formula ^[4] to directly update the inverse of the approximate Jacobian matrix:

${\displaystyle \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 to J_n−1. This yields a second method, the so-called "bad Broyden's method":

${\displaystyle \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

${\displaystyle \|\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 does ^[5] for which several explanations have been proposed. ^{[6] [7]} Many other quasi-Newton schemes have been suggested in optimization such as the BFGS, where one seeks a maximum or minimum by finding zeros of the first derivatives (zeros of the gradient in multiple dimensions). The Jacobian of the gradient is called the Hessian and 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. ^{[1] : 578} In general, methods in the Broyden class are given in the form ^{[8] : 150}$${\displaystyle \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 ${\displaystyle y_{k}:=\mathbf {f} (\mathbf {x} _{k+1})-\mathbf {f} (\mathbf {x} _{k}),}$${\displaystyle s_{k}:=\mathbf {x} _{k+1}-\mathbf {x} _{k},}$ and $${\displaystyle 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 ${\displaystyle \phi _{k}\in \mathbb {R} }$ for each ${\displaystyle k=1,2,...}$. The choice of ${\displaystyle \phi _{k}}$ determines the method.

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

• The Davidon–Fletcher–Powell (DFP) method, which is the only member of this class being published before the two methods defined by Broyden. ^{[1] : 582} For the DFP method, ${\displaystyle \phi _{k}=1}$. ^{[8] : 150}
• Anderson's iterative method, which uses a least squares approach to the Jacobian. ^[9]
• Schubert's or sparse Broyden algorithm – a modification for sparse Jacobian matrices. ^[10]
• The Pulay approach, often used in density functional theory. ^{[11] [12]}
• A limited memory method by Srivastava for the root finding problem which only uses a few recent iterations. ^[13]
• Klement (2014) – uses fewer iterations to solve some systems. ^{[14] [15]}
• Multisecant methods for density functional theory problems ^{[7] [16]}

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

References

1. Broyden, C. G. (1965). "A Class of Methods for Solving Nonlinear Simultaneous Equations". Mathematics of Computation. 19 (92). American Mathematical Society: 577–593. doi: 10.1090/S0025-5718-1965-0198670-6 . JSTOR   2003941.
2. Gay, D. M. (1979). "Some convergence properties of Broyden's method". SIAM Journal on Numerical Analysis. 16 (4). SIAM: 623–630. doi:10.1137/0716047.
3. Shanno, D. F.; Phua, Kang -Hoh (1978). "Matrix conditioning and nonlinear optimization". Mathematical Programming. 14 (1): 149–160. doi:10.1007/BF01588962. ISSN   0025-5610.
4. Sherman, Jack; Morrison, Winifred J. (1950). "Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix". The Annals of Mathematical Statistics. 21 (1): 124–127. doi:10.1214/aoms/1177729893. ISSN   0003-4851.
5. Kvaalen, Eric (1991). "A faster Broyden method". BIT Numerical Mathematics. 31 (2). SIAM: 369–372. doi:10.1007/BF01931297.
6. Martı́nez, José Mario (2000). "Practical quasi-Newton methods for solving nonlinear systems". Journal of Computational and Applied Mathematics. 124 (1–2): 97–121. doi:10.1016/s0377-0427(00)00434-9. ISSN   0377-0427.
7. Marks, L. D.; Luke, D. R. (2008). "Robust mixing for ab initio quantum mechanical calculations". Physical Review B. 78 (7). doi:10.1103/physrevb.78.075114. ISSN   1098-0121.
8. Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization. Springer Series in Operations Research and Financial Engineering. Springer New York. doi:10.1007/978-0-387-40065-5. ISBN   978-0-387-30303-1.
9. Anderson, Donald G. (1965). "Iterative Procedures for Nonlinear Integral Equations". Journal of the ACM. 12 (4): 547–560. doi:10.1145/321296.321305. ISSN   0004-5411.
10. Schubert, L. K. (1970). "Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian". Mathematics of Computation. 24 (109): 27–30. doi: 10.1090/S0025-5718-1970-0258276-9 . ISSN   0025-5718.
11. Pulay, Péter (1980). "Convergence acceleration of iterative sequences. the case of scf iteration". Chemical Physics Letters. 73 (2): 393–398. doi:10.1016/0009-2614(80)80396-4.
12. Kresse, G.; Furthmüller, J. (1996). "Efficient iterative schemes for ab initio total-energy calculations using a plane-wave basis set". Physical Review B. 54 (16): 11169–11186. doi:10.1103/PhysRevB.54.11169. ISSN   0163-1829.
13. Srivastava, G P (1984). "Broyden's method for self-consistent field convergence acceleration". Journal of Physics A: Mathematical and General. 17 (6): L317–L321. doi:10.1088/0305-4470/17/6/002. ISSN   0305-4470.
14. Klement, Jan (2014). "On Using Quasi-Newton Algorithms of the Broyden Class for Model-to-Test Correlation". Journal of Aerospace Technology and Management. 6 (4): 407–414. doi: 10.5028/jatm.v6i4.373 . ISSN   2175-9146.
15. "Broyden class methods – File Exchange – MATLAB Central". www.mathworks.com. Retrieved 2016-02-04.
16. Woods, N D; Payne, M C; Hasnip, P J (2019). "Computing the self-consistent field in Kohn–Sham density functional theory". Journal of Physics: Condensed Matter. 31 (45): 453001. doi:10.1088/1361-648X/ab31c0. ISSN   0953-8984.

Further reading

• Dennis, J. E.; Schnabel, Robert B. (1983). Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Englewood Cliffs: Prentice Hall. pp. 168–193. ISBN   0-13-627216-9.
• Fletcher, R. (1987). Practical Methods of Optimization (Second ed.). New York: John Wiley & Sons. pp.  44–79. ISBN   0-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. ISBN   978-0-89871-352-7.

External links

• Simple basic explanation: The story of the blind archer