Suggest edit — Broyden's Method

Title

Name

Note

---
title: "Broyden's Method"
type: concept
source: https://www.jemoka.com/posts/kbhbroyden_s_method/
confidence: high
status: active
---

Broyden&rsquo;s method is an approximate method to estimate the Jacobian. We give the root-finding variant here (i.e. the search direction is for finding \(F\qty(x) = 0\) instead of \(\min F\)).
For function \(F\), let: \(J^{(0)} = I\). For every step
compute \(\Delta c^{(q)}\) from \(J^{(q)}\Delta c^{(q)} = -F\qty(c^{(q)})\) compute \(\arg\min_{\alpha} F\qty(c^{(q)} + \alpha \Delta c^{(q)})^{T}F\qty(c^{(q)} + \alpha \Delta c^{(q)})\) for root finding compute \(c^{(q+1)} = c^{(q)} + \alpha \Delta c^{(q)}\) set \(\Delta c^{(q)} = c^{(q+1)} - c^{(q)}\) finally, we can update \(J\) such that&hellip; \begin{equation} J^{(q+1)} = J^{(q)} + \frac{1}{\qty(\Delta c^{(q)})^{T} \Delta c^{(q)}} \qty(F\qty(c^{(q+1)}) - F\qty(c^{(q)}) - J^{(q)}\Delta c^{(q)}) \qty(\Delta c^{(q)})^{T} \end{equation}
The definition for \(J\) the Jacobian above is only valid for the search direction that was just taken:
\begin{equation} J^{(q+1)}\qty(c^{(q+1)} - c^{(q)}) = F\qty(c^{(q+1)}) - F\qty(c^{(q)}) \end{equation}
but is not true generally (i.e. the Jacobian should give you the change in every direction, but the estimate above could only work with one Jacobian).
We can adapt this for minimization of some function \(G\qty(x)\) by setting \(F\qty(x) = J(G)\) and solve for the Hessian by replacing \(J^{(q)} \implies H^{(j)}\).