BFGS算法中的SWM公式应用

BFGS算法矩阵$ B_k $的迭代公式为：

$$B_{k+1}=B_k+\frac{y_ky_k^T}{y_k^T\delta_k}-\frac{B_k\delta_k\delta_k^TB_k}{\delta_k^TB_k\delta_k}$$

Sherman-Morrison公式为：

假设 A 是 n 阶可逆矩阵， t 为常量，u,v 是 n 维向量，且 $A+uv^T $也是可逆矩阵，则

$$(A+\frac{uv^T}{t})^{-1}=A^{-1}-\frac{A^{-1}uv^TA^{-1}}{t+v^TA^{-1}u}$$

下面我们需要根据上述两个式子，得到$B_{k+1}$的逆矩阵$H_{k+1}$的迭代格式。注意下面推导过程中第二个等号和第三个等号分别利用了一次Sherman-Morrison公式。\begin{align*} & B_{k+1}^{-1} =(B_k+\frac{y_ky_k^T}{y_k^Ts_k}-\frac{B_ks_ks_k^TB_k}{s_k^TB_ks_k})^{-1}\\ &=(B_k+\frac{y_ky_k^T}{y_k^Ts_k})^{-1}+(B_k+\frac{y_ky_k^T}{y_k^Ts_k})^{-1}\frac{B_ks_ks_k^TB_k}{s_k^TB_ks_k-s_k^TB_k(B_k+\frac{y_ky_k^T}{y_k^Ts_k})^{-1}B_ks_k}(B_k+\frac{y_ky_k^T}{y_k^Ts_k})^{-1}\\ &=(B_k^{-1}-\frac{B_k^{-1}y_ky_k^TB_k^{-1}}{y_k^Ts_k+y_k^TB_k^{-1}y_k})+(B_k^{-1}-\frac{B_k^{-1}y_ky_k^TB_k^{-1}}{y_k^T\delta_k+y_k^TB_k^{-1}y_k})\frac{B_ks_ks_k^TB_k}{s_k^TB_ks_k-s_k^TB_k(B_k^{-1}-\frac{B_k^{-1}y_ky_k^TB_k^{-1}}{y_k^Ts_k+y_k^TB_k^{-1}y_k})B_ks_k}(B_k^{-1}-\frac{B_k^{-1}y_ky_k^TB_k^{-1}}{y_k^Ts_k+y_k^TB_k^{-1}y_k})\\ &=(B_k^{-1}-\frac{B_k^{-1}y_ky_k^TB_k^{-1}}{y_k^Ts_k+y_k^TB_k^{-1}y_k})+(B_k^{-1}-\frac{B_k^{-1}y_ky_k^TB_k^{-1}}{y_k^Ts_k+y_k^TB_k^{-1}y_k})\frac{B_ks_ks_k^TB_k}{\frac{s_k^Ty_ky_k^Ts_k}{y_k^Ts_k+y_k^TB_k^{-1}y_k}}(B_k^{-1}-\frac{B_k^{-1}y_ky_k^TB_k^{-1}}{y_k^Ts_k+y_k^TB_k^{-1}y_k})\\ &=(B_k^{-1}-\frac{B_k^{-1}y_ky_k^TB_k^{-1}}{y_k^Ts_k+y_k^TB_k^{-1}y_k})+\frac{B_k^{-1}B_ks_ks_k^TB_kB_k^{-1}}{\frac{s_k^Ty_ky_k^Ts_k}{y_k^Ts_k+y_k^TB_k^{-1}y_k}}-\frac{B_k^{-1}B_ks_ks_k^TB_k}{\frac{s_k^Ty_ky_k^Ts_k}{y_k^Ts_k+y_k^TB_k^{-1}y_k}}\frac{B_k^{-1}y_ky_k^TB_k^{-1}}{y_k^Ts_k+y_k^TB_k^{-1}y_k}-\frac{B_k^{-1}y_ky_k^TB_k^{-1}}{y_k^Ts_k+y_k^TB_k^{-1}y_k}\frac{B_ks_ks_k^TB_k}{\frac{s_k^Ty_ky_k^Ts_k}{y_k^Ts_k+y_k^TB_k^{-1}y_k}}B_k^{-1}+\frac{B_k^{-1}y_ky_k^TB_k^{-1}}{y_k^Ts_k+y_k^TB_k^{-1}y_k}\frac{B_ksa_ks_k^TB_k}{\frac{s_k^Ty_ky_k^Ts_k}{y_k^Ts_k+y_k^TB_k^{-1}y_k}}\frac{B_k^{-1}y_ky_k^TB_k^{-1}}{y_k^Ts_k+y_k^TB_k^{-1}y_k}\\ &=(B_k^{-1}-\frac{B_k^{-1}y_ky_k^TB_k^{-1}}{y_k^Ts_k+y_k^TB_k^{-1}y_k})+\frac{s_ks_k^T(y_k^Ts_k+y_k^TB_k^{-1}y_k)}{s_k^Ty_ky_k^Ts_k}-\frac{s_ks_k^Ty_ky_k^TB_k^{-1}}{s_k^Ty_ky_k^Ts_k}- \frac{B_k^{-1}y_ky_k^Ts_ks_k^T}{s_k^Ty_ky_k^Ts_k}+\frac{B_k^{-1}y_k(y_k^Ts_ks_k^Ty_k)y_k^TB_k^{-1}}{(y_k^Ts_k+y_k^TB_k^{-1}y_k)(s_k^Ty_ky_k^Ts_k)}\\ &=(B_k^{-1}-\frac{B_k^{-1}y_ky_k^TB_k^{-1}}{y_k^Ts_k+y_k^TB_k^{-1}y_k}) +\frac{s_ks_k^T(y_k^Ts_k+y_k^TB_k^{-1}y_k)}{(s_k^Ty_k)^2} -\frac{s_k(s_k^Ty_k)y_k^TB_k^{-1}}{(s_k^Ty_k)^2} -\frac{B_k^{-1}y_k(y_k^Ts_k)s_k^T}{(s_k^Ty_k)^2}+\frac{B_k^{-1}y_ky_k^TB_k^{-1}}{(y_k^Ts_k+y_k^TB_k^{-1}y_k)}\\ &=B_k^{-1} +\frac{s_ks_k^T(y_k^Ts_k)}{(s_k^Ty_k)^2} +\frac{s_ks_k^T(y_k^TB_k^{-1}y_k)}{(s_k^Ty_k)^2} -\frac{s_ky_k^TB_k^{-1}}{s_k^Ty_k} -\frac{B_k^{-1}y_ks_k^T}{s_k^Ty_k}\\ &=B_k^{-1} -\frac{B_k^{-1}y_ks_k^T}{s_k^Ty_k} -\frac{s_ky_k^TB_k^{-1}}{s_k^Ty_k} +\frac{s_k(y_k^TB_k^{-1}y_k)s_k^T}{(s_k^Ty_k)^2} +\frac{s_ks_k^T}{s_k^Ty_k}\\ &=B_k^{-1}(I-\frac{y_ks_k^T}{s_k^Ty_k}) -\frac{s_ky_k^TB_k^{-1}}{s_k^Ty_k}(I-\frac{y_ks_k^T}{s_k^Ty_k}) +\frac{s_ks_k^T}{s_k^Ty_k}\\ &=(I-\frac{s_ky_k^T}{s_k^Ty_k})B_k^{-1}(I-\frac{y_ks_k^T}{s_k^Ty_k})+\frac{s_ks_k^T}{s_k^Ty_k}\\ &=(I-\frac{s_ky_k^T}{s_k^Ty_k})B_k^{-1}(I-\frac{s_ky_k^T}{s_k^Ty_k})^T+\frac{s_ks_k^T}{s_k^Ty_k} \end{align*}

记：$H_k=B_k^{-1},H_{k+1}=H_{k+1}^{-1}$，则有
$$H_{k+1}=(I-\frac{s_ky_k^T}{s_k^Ty_k})H_k(I-\frac{s_ky_k^T}{s_k^Ty_k})^T+\frac{s_ks_k^T}{s_k^Ty_k}$$

本文参考这篇知乎文章：

Broyden类算法：BFGS算法的迭代公式推导（应用两次Sherman-Morrison公式） - 知乎 (zhihu.com)