Broyden–Fletcher–Goldfarb–Shanno Algorithm

Definition

The quasi-Newton method with symmetric and positive-definite condition Update inverse of hessian directly

Algorithm

Define $\Delta {\mathbf{f}}_n:={\mathbf{f}}_n-{\mathbf{f}}_{n-1}$ $\Delta {\mathbf{x}}_n:={\mathbf{x}}_n-{\mathbf{x}}_{n-1}$ $J_n\simeq {\nabla }^{2}f(x)$ $H_n=J_n^{-1}\simeq {\nabla }^{2}f(x{)}^{-1}$

Then, $\Delta {\mathbf{f}}_n={\mathbf{J}}_{\mathbf{n}}\Delta {\mathbf{x}}_n$ $\Delta {\mathbf{x}}_n={\mathbf{H}}_{\mathbf{n}}\Delta {\mathbf{f}}_n$

We want to find $A$ satisfying the following expression with the symmetric and positive-definite condition $H_n=H_{n-1}+A$ $\Rightarrow \Delta {\mathbf{x}}_n=(H_{n-1}+A)\Delta {\mathbf{f}}_n=H_{n-1}\Delta {\mathbf{f}}_n+A\Delta {\mathbf{f}}_n\Rightarrow A\Delta {\mathbf{f}}_n=\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n$ by the definition

So, Solve the minimization problem with the symmetric and positive-definite conditions using method of Lagrange multipliers $\min ||A|{|}_w^2=||MA{M}^{⊺}|{|}_F^2$ subject to $A=A^{⊺}$ and $A\Delta {\mathbf{f}}_n=\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n$ where $W=M^{⊺}M:=J_k$

Then, the solution is $A=\frac{(W^{-1}\Delta {\mathbf{f}}_n)(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n{)}^{⊺}+(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n)(W^{-1}\Delta {\mathbf{f}}_n{)}^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}(W^{-1}\Delta {\mathbf{f}}_n)}-\frac{\Delta {\mathbf{f}}_n^{⊺}(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n)(W^{-1}\Delta {\mathbf{f}}_n)(W^{-1}\Delta {\mathbf{f}}_n{)}^{⊺}}{(\Delta {\mathbf{f}}_n^{⊺}(W^{-1}\Delta {\mathbf{f}}_n){)}^2}$ where $W^{-1}\Delta {\mathbf{f}}_n=\Delta {\mathbf{x}}_n$ by the definition $=\frac{\Delta {\mathbf{x}}_n(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n{)}^{⊺}+(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n)\Delta {\mathbf{x}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}-\frac{\Delta {\mathbf{f}}_n^{⊺}(\Delta {\mathbf{x}}_n-H_{n-1}\Delta {\mathbf{f}}_n)\Delta {\mathbf{x}}_n\Delta {\mathbf{x}}_n^{⊺}}{(\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n{)}^2}$ $=\left(I-\frac{\Delta {\mathbf{x}}_n\Delta {\mathbf{f}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}\right)H_{n-1}\left(I-\frac{\Delta {\mathbf{f}}_n\Delta {\mathbf{x}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}\right)+\frac{\Delta {\mathbf{x}}_n\Delta {\mathbf{x}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}$

Therefore, updating formula is $H_n=H_{n-1}+\left(I-\frac{\Delta {\mathbf{x}}_n\Delta {\mathbf{f}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}\right)H_{n-1}\left(I-\frac{\Delta {\mathbf{f}}_n\Delta {\mathbf{x}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}\right)+\frac{\Delta {\mathbf{x}}_n\Delta {\mathbf{x}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}$

And by the Sherman–Morrison Formula, $J_n=J_{n-1}+\frac{\Delta {\mathbf{f}}_n\Delta {\mathbf{f}}_n^{⊺}}{\Delta {\mathbf{f}}_n^{⊺}\Delta {\mathbf{x}}_n}-\frac{J_{n-1}\Delta {\mathbf{x}}_n(J_{n-1}\Delta {\mathbf{x}}_n{)}^{⊺}}{\Delta {\mathbf{x}}_n^{⊺}{J}_{n-1}\Delta {\mathbf{x}}_n}$ and ${\mathbf{x}}_{n+1}={\mathbf{x}}_n-H_n\mathbf{f}({\mathbf{x}}_n)$