Broyden’s Method

See Also: Unconstrained Optimization Nonlinear Optimization

Recall that a potential shortcoming of Newton’s method for nonlinear equations is that the derivatives required for the Jacobian may not be available or may be difficult to calculate. Secant methods, also known as quasi-Newton methods, do not require the calculation of the Jacobian; they construct an approximation to the matrix, which is updated at each iteration, so that it behaves similarly to the true Jacobian along the step. Broyden’;s method is the most successful secant-method for solving systems of nonlinear equations.

Let \(B_k\) be the Jacobian approximation at iteration \(k\) and let \(s_k = x_{k+1} – x_k\). Then, the updated Jacobian approximation \(B_{k+1}\) must satisfy the secant equation
\[B_{k+1} \, s_k = f(x_{k+1}) – f(x_k). \quad(1) \,\]

Given an initial matrix \(B_0\) (often a finite-difference approximation to the Jacobian matrix), Broyden's method generates subsequent matrices by the update formula
\[B_{k+1} = B_k + \frac{(y_k – B_k s_k)s_k^T} {\|s_k\|_2^2 }, \quad(2) \,\] where \(y_k = f(x_{k+1}) – f(x_k) \,\).

The remarkable feature of Broyden's method is that it is able to generate a reasonable approximation to the Jacobian matrix with no additional evaluations of the function. This feature is partially explained by noting that, because of equation (1), the updated \(B_{k+1}\) mimics the behavior of the true Jacobian along the line joining \(x_k\) to \(x_{k+1}\).