拟牛顿法（Quasi-Newton Method）
- 拟牛顿法（Quasi-Newton Method）
- 得到矩阵 B k + 1 B_{k+1} Bk+1
- 获取 B k + 1 B_{k+1} Bk+1和 H k + 1 H_{k+1} Hk+1
- DFP方法(Davidon-Fletche Powell)
- BFGS方法(Broyden-Fletcher-Goldfarb-Shannon)
- Broyden类算法和Sherman-Morrison公式
- SR-1方法
全部笔记的汇总贴：最优化学习目录
拟牛顿法（Quasi-Newton Method）
Quasi−NewtenMethod d k = − B − 1 ∇ f ( x k ) \text{Quasi−NewtenMethod } d^{k}=-B^{-1} \nabla f\left(x^{k}\right) Quasi−NewtenMethod dk=−B−1∇f(xk)
得到矩阵 B k + 1 B_{k+1} Bk+1
拟牛顿方程 : \text{拟牛顿方程 :} 拟牛顿方程 : ∇ f ( x k + 1 ) − ∇ f ( x k ) = B k + 1 ( x k + 1 − x k ) \nabla f\left(x^{k+1}\right)-\nabla f\left(x^{k}\right)=B_{k+1}\left(x^{k+1}-x^{k}\right) ∇f(xk+1)−∇f(xk)=Bk+1(xk+1−xk) y k = ∇ f ( x k + 1 ) − ∇ f ( x n ) y_{k}=\nabla f\left(x^{k+1}\right)-\nabla f\left(x^{n}\right) yk=∇f(xk+1)−∇f(xn) s k = x k + 1 − x k s_{k}=x^{k+1}-x^{k} sk=xk+1−xk
这样我们就可以得到 y k = B k + 1 s k y_{k}=B_{k+1}s_{k} yk=Bk+1sk，记 H k + 1 = ( B k + 1 ) − 1 H_{k+1}=(B_{k+1})^{-1} Hk+1=(Bk+1)−1
获取 B k + 1 B_{k+1} Bk+1和 H k + 1 H_{k+1} Hk+1
- 第一类方法：选择满足拟牛顿方程且与 B k B_{k} Bk近似的矩阵
- 第二类方法：对 B k B_{k} Bk或 H k H_{k} Hk进行校正，如 B k + 1 = B k + Δ B B_{k+1} = B_{k} + \Delta B Bk+1=Bk+ΔB
- rank-2 校正 Δ B \Delta B ΔB秩为2 DFP方法,BFGS方法
- rank-1 校正 Δ B \Delta B ΔB秩为1 SR-1方法
DFP方法(Davidon-Fletche Powell)
可以看作是rank-2校正
( D F P ) H k + 1 = H k − H k y k y k T H k y k ⊤ H k y k + s k s k ⊤ y k ⊤ s k (D F P) H_{k+1}=H_{k}-\frac{H_{k} y_{k} y_{k}^{T}H_{k}}{y_{k}^{\top} H_{k} y_{k}}+\frac{s_{k} s_{k}^{\top}}{y_{k}^{\top} s_{k}} (DFP)Hk+1=Hk−yk⊤HkykHkykykTHk+yk⊤sksksk⊤
BFGS方法(Broyden-Fletcher-Goldfarb-Shannon)
可以看作是rank-2校正
( B F G S ) B k + 1 = B k − B k s k s k ⊤ B k s k ⊤ B k s k + y k y k ⊤ y k ⊤ s k (B F G S) B_{k+1}=B_{k}-\frac{B_{k} s_{k} s_{k}^{\top} B_{k}}{s_{k}^{\top} B_{k} s_{k}}+\frac{y_{k} y_{k}^{\top}}{y_{k}^{\top} s_{k}} (BFGS)Bk+1=Bk−sk⊤BkskBksksk⊤Bk+yk⊤skykyk⊤
Broyden类算法和Sherman-Morrison公式
Sherman-Morrison公式：
假设 A A A是 n n n阶可逆矩阵, u , v u,v u,v是 n n n维向量，且 ( A + u v T ) \left(A+u v^{T}\right) (A+uvT)也是可逆矩阵，则
( A + u v T ) − 1 = A − 1 − A − 1 u v T A − 1 1 + v T A − 1 u \left(A+u v^{T}\right)^{-1}=A^{-1}-\frac{A^{-1} u v^{T} A^{-1}}{1+v^{T} A^{-1} u} (A+uvT)−1=A−1−1+vTA−1uA−1uvTA−1
SR-1方法
( S R − 1 ) B k + 1 = B k + ( y k − B k k ) ( y k − B k s k ) T ( y h − B u s k ) ⊤ s k (SR-1)B_{k+1}=B_{k}+\frac{\left(y_{k}-B_{k_{k}}\right)\left(y_{k}-B_{k}s_{k}\right)^{T}}{\left(y_{h}-B_{u} s_{k}\right)^{\top} s_{k}} (SR−1)Bk+1=Bk+(yh−Busk)⊤sk(yk−Bkk)(yk−Bksk)T
