Broyden's method

From Wikipedia, the free encyclopedia

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

Newton's method for solving $\displaystyle {\vec {F}}({\vec {x}})={\vec {0}}$ uses the Jacobian matrix, $\displaystyle 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 x n, it terminates in 2n 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 $\displaystyle f'(x_{n})$ with the finite difference approximation:

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

and proceeds similar to Newton's Method ( $n$ is the index for the iterations):

$x_{{n+1}}=x_{n}-{\frac {1}{f'(x_{n})}}f(x_{n}).$

Solving a set of nonlinear equations

To solve a set of nonlinear equations

$\displaystyle {\vec {F}}({\vec {x}})={\vec {0}}$ ,

where the vector ${\vec {F}}$ is a function of vector ${\vec {x}}$ as (if we have $k$ equations):

${\vec {x}}=(x_{1},x_{2},x_{3},...,x_{k})$

${\vec {F}}({\vec {x}})=(f_{1}(x_{1},x_{2},...,x_{k}),f_{2}(x_{1},x_{2},...,x_{k})...,f_{k}(x_{1},x_{2},...,x_{k}))$

For such problems, Broyden gives a generalization of above formula, replacing the derivative $\displaystyle {\vec F}'$ with the Jacobian $\displaystyle J$ . The Jacobian matrix is determined iteratively based on the secant equation with the finite difference approximation:

$J_{n}\cdot ({\vec {x}}_{n}-{\vec {x}}_{{n-1}})\simeq {\vec {F}}({\vec {x}}_{n})-{\vec {F}}({\vec {x}}_{{n-1}}),$

where $n$ is the index of iterations. However above equation is under determined in more than one dimension. Broyden suggests using the current estimate of the Jacobian matrix $\displaystyle J_{{n-1}}$ and improving upon it by taking the solution to the secant equation that is a minimal modification to $\displaystyle J_{{n-1}}$ (minimal in the sense of minimizing the Frobenius norm $\displaystyle \|J_{{n}}-J_{{n-1}}\|_{{F}}$ ):

$J_{n}=J_{{n-1}}+{\frac {\Delta {\vec {F}}_{n}-J_{{n-1}}\Delta {\vec {x}}_{n}}{\|\Delta {\vec {x}}_{n}\|^{2}}}\Delta {\vec {x}}_{n}^{T}$

where

$\Delta {\vec {x}}={\vec {x}}_{{n}}-{\vec {x}}_{{n-1}}$

$\Delta {\vec {F}}={\vec {F}}_{{n}}-{\vec {F}}_{{n-1}}$

then we proceed in the Newton direction as:

${\vec {x}}_{{n+1}}={\vec {x}}_{n}-J_{n}^{{-1}}{\vec {F}}({\vec {x}}_{n}).$

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

$J_{n}^{{-1}}=J_{{n-1}}^{{-1}}+{\frac {\Delta {\vec {x}}_{n}-J_{{n-1}}^{{-1}}\Delta {\vec {F}}_{n}}{\Delta {\vec {x}}_{n}^{T}J_{{n-1}}^{{-1}}\Delta {\vec {F}}_{n}}}(\Delta {\vec {x}}_{n}^{T}J_{{n-1}}^{{-1}})$

This 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}}$ (which minimizes $\displaystyle \|J_{{n}}^{{-1}}-J_{{n-1}}^{{-1}}\|_{{F}}$ instead); this yields the so-called "bad Broyden's method" (but see^[3]):

$J_{n}^{{-1}}=J_{{n-1}}^{{-1}}+{\frac {\Delta {\vec {x}}_{n}-J_{{n-1}}^{{-1}}\Delta {\vec {F}}_{n}}{\Delta {\vec {F}}_{n}^{T}\Delta {\vec {F}}_{n}}}\Delta {\vec {F}}_{n}^{T}$

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 upgrade.

References

↑ 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.2307/2003941. JSTOR 2003941. |accessdate= requires |url= (help)
↑ 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.
↑ Kvaalen, Eric (November 1991). "A faster Broyden method". BIT Numerical Mathematics (SIAM) 31 (2): 369–372. doi:10.1007/BF01931297.

External links

Module for Broyden's Method by John H. Mathews

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear: Methods calling ...

... functions

... 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

... and Hessians

Newton's method

The graph of a strictly concave quadratic function is shown in blue, with its unique maximum shown as a red dot. Below the graph appears the contours of the function: The level sets are nested ellipses.

Constrained nonlinear

General	Barrier methods Penalty methods

Differentiable	Augmented Lagrangian methods Sequential quadratic programming Successive linear programming

Convex optimization

Convex
minimization

Linear and
quadratic

Interior point	Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar

Basis-Exchange	Simplex algorithm of Dantzig Criss-cross algorithm Principal pivoting algorithm of Lemke

Combinatorial

Paradigms

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

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.