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 is a difficult and expensive operation. The idea behind Broyden's method is to compute the whole Jacobian only at the first iteration, and to do a rank-one update at the 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 equation

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

and proceed similar to Newton's Method:

where n is the iteration index.

Solving a system of nonlinear equations

To solve a system of k nonlinear equations

where f is a vector-valued function of vector x:

For such problems, Broyden gives a generalization of the one-dimensional Newton's method, replacing the derivative with the Jacobian J. The Jacobian matrix is determined iteratively based on the secant equation in the finite difference approximation:

where n is the iteration index. For clarity, let us define:

so the above may be rewritten as:

The above equation is underdetermined when k is greater than one. Broyden suggests using the current estimate of the Jacobian matrix J_{n − 1} and improving upon it by taking the solution to the secant equation that is a minimal modification to J_{n − 1}:

This minimizes the following Frobenius norm:

We may then proceed in the Newton direction:

Broyden also suggested using the Sherman-Morrison formula to update directly the inverse of the Jacobian matrix:

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" (but see^[3]):

This minimizes a different Frobenius norm:

Many other quasi-Newton schemes have been suggested in optimization, where one seeks a maximum or minimum by finding the root of the first derivative (gradient in multi dimensions). The Jacobian of the gradient is called Hessian and is symmetric, adding further constraints to its update.

Other members of the Broyden class

Broyden has defined not only two methods, but a whole class of methods. Other members of this class have been added by other authors.

• The Davidon–Fletcher–Powell update is the only member of this class being published before the two members defined by Broyden.^[4]
• Schubert's or sparse Broyden algorithm – a modification for sparse Jacobian matrices.^[5]
• Klement (2014) – uses fewer iterations to solve many equation systems.^[6][7]

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. (October 1965). "A Class of Methods for Solving Nonlinear Simultaneous Equations". Mathematics of Computation. American Mathematical Society. 19 (92): 577–593. doi:10.1090/S0025-5718-1965-0198670-6. JSTOR 2003941. 
2. ↑ Gay, D.M. (August 1979). "Some convergence properties of Broyden's method". SIAM Journal of Numerical Analysis. SIAM. 16 (4): 623–630. doi:10.1137/0716047. 
3. ↑ Kvaalen, Eric (November 1991). "A faster Broyden method". BIT Numerical Mathematics. SIAM. 31 (2): 369–372. doi:10.1007/BF01931297. 
4. ↑ Broyden, C. G. (October 1965). "A Class of Methods for Solving Nonlinear Simultaneous Equations". Mathematics of Computation. American Mathematical Society. 19 (92): 577–593. doi:10.1090/S0025-5718-1965-0198670-6. JSTOR 2003941. 
5. ↑ Schubert, L. K. (1970-01-01). "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. 
6. ↑ Klement, Jan (2014-11-23). "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. 
7. ↑ "Broyden class methods – File Exchange – MATLAB Central". www.mathworks.com. Retrieved 2016-02-04. 

External links

Simple basic explanation: The story of the blind archer

Optimization: Algorithms, methods, and heuristics
Unconstrained nonlinear: Methods calling … … functions Golden section search Interpolation methods Line search Nelder–Mead method Successive parabolic interpolation … and gradients Convergence Trust region Wolfe conditions Quasi–Newton BFGS and L-BFGS DFP Symmetric rank-one (SR1) Other methods Gauss–Newton Gradient Levenberg–Marquardt Conjugate gradient Truncated Newton … and Hessians Newton's method
Constrained nonlinear General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming
Convex optimization Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-Exchange Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke
Combinatorial Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch & bound or cut Graph algorithms Minimum spanning tree Bellman–Ford Borůvka Dijkstra Floyd–Warshall Johnson Kruskal Network flows Dinic Edmonds–Karp Ford–Fulkerson Push–relabel maximum flow
Metaheuristics Evolutionary algorithm Hill climbing Local search Simulated annealing Tabu search
Categories Algorithms and methods Heuristics Software