Davidon–Fletcher–Powell Formula

Definition

The quasi-Newton method with symmetric and positive-definite condition Update hessian and find inverse using Sherman–Morrison Formula

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 $J_n=J_{n-1}+A$ $\Rightarrow \Delta {\mathbf{f}}_n=(J_{n-1}+A)\Delta {\mathbf{x}}_n=J_{n-1}\Delta {\mathbf{x}}_n+A\Delta {\mathbf{x}}_n\Rightarrow A\Delta {\mathbf{x}}_n=\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_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{x}}_n=\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n$ where $W=M^{⊺}M:=H_k$

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

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