Sherman-Morrison公式在BFGS算法的应用

作者: Azur_wxj | 来源:发表于2019-09-25 10:56 被阅读0次

Sherman-Morrison公式在BFGS算法的应用
BFGS算法
BFGS, L-BFGS算法
L-BFGS算法
L-BFGS算法介绍
L-BFGS算法介绍
GD 以外的优化方案
2018-12-15逻辑回归高级优化
啊哈!算法
2018-10-15

Sherman-Morrison公式：设 $A\in\mathbb{R}^{n\times n}$ 为可逆矩阵， $u,v\in\mathbb{R}^n$ ，则 $(A+uv^T)$ 可逆当且仅当 $1+v^TAu\neq 0$ ，并且其逆矩阵是 $(A+uv^T)^{-1}=A^{-1}-\frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}$

在BFGS算法中，已经得到递推公式 $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^TB_k\delta_k}$ ，设 $B_k=B_k^T$ 为 $n\times n$ 的实对可逆对称矩阵， $y_k,\delta_k\in\mathbb{R}^n$ ，我们希望得到 $B^{-1}_{k+1}$ 。

为了方便叙述，省略下标 $k$ 。首先令 $H=B+\frac{yy^T}{y^T\delta}$ ，我们注意到， $-\frac{B\delta\delta^TB}{\delta^TB\delta}=-\frac{1}{\delta^TB\delta}(B\delta)(B\delta)^T$ ，其中 $\delta^TB\delta$ 为标量（二次型形式），且 $B\delta\in\mathbb{R}^n$ ，因此利用sherman-morrison公式，我们就有
$\begin{split} B_{k+1}^{-1}=& \left(H-\frac{1}{\delta^TB\delta}(B\delta)(B\delta)^T\right)^{-1}\\ =&H^{-1}-\frac{H^{-1}\left(-\frac{1}{\delta^TB\delta}(B\delta)(B\delta)^T\right)H^{-1}}{1+(-\frac{1}{\delta^TB\delta})(B\delta)^TH^{-1}(B\delta)}\\ =&H^{-1}+H^{-1}\frac{B\delta\delta^TB}{\delta^TB\delta-\delta^TBH^{-1}B\delta}H^{-1} \end{split}$
另一方面，对于 $H^{-1}$ ，再次利用sherman-morrison公式，就有
$\begin{split} H^{-1}&= \left(B+\frac{yy^T}{y^T\delta}\right)^{-1}\\ &=B^{-1}-\frac{B^{-1}\frac{yy^T}{y^T\delta }B^{-1}}{1+\frac{1}{y^T\delta}y^T B^{-1}y}\quad\text{Note that $y^T\delta$ is scalar, inner product}\\ &=B^{-1}-\frac{B^{-1}yy^TB^{-1}}{y^T\delta+y^TB^{-1}y} \end{split}$
注意到 $y^T\delta$ 和 $y^TB^{-1}y$ 都是常数（即内积形式和二次型形式），令 $Q=y^T\delta+y^TB^{-1}y$

现将 $H^{-1}$ 的表达式代回 $B^{-1}_{k+1}$ 中，我们首先计算第二项：
$\begin{split} &H^{-1}\frac{B\delta\delta^TB}{\delta^TB\delta-\delta^TBH^{-1}B\delta}H^{-1} \\=&\left(B^{-1}-\frac{B^{-1}yy^TB^{-1}}{Q}\right) \frac{B\delta\delta^TB}{\delta^TB\delta-\delta^TB\left(B^{-1}-\frac{B^{-1}yy^TB^{-1}}{Q}\right)B\delta}\left(B^{-1}-\frac{B^{-1}yy^TB^{-1}}{Q}\right)\\ =& \left(B^{-1}-\frac{B^{-1}yy^TB^{-1}}{Q}\right) \frac{B\delta\delta^TB}{ \delta^TB\delta-\delta^TB\delta +\frac{\delta^Tyy^T\delta}{Q}} \left(B^{-1}-\frac{B^{-1}yy^TB^{-1}}{Q}\right)\\ =&\frac{Q}{\delta^Tyy^T\delta}\left(B^{-1}-\frac{B^{-1}yy^TB^{-1}}{Q}\right) B\delta\delta^TB\left(B^{-1}-\frac{B^{-1}yy^TB^{-1}}{Q}\right) \\ =&\frac{Q}{\delta^Tyy^T\delta}\left(\delta\delta^TB-\frac{B^{-1}yy^T\delta\delta^TB}{Q}\right)\left(B^{-1}-\frac{B^{-1}yy^TB^{-1}}{Q}\right)\\ =&\frac{Q}{\delta^Tyy^T\delta}\left(\delta\delta^T-\frac{\delta\delta^Tyy^TB^{-1}}{Q}-\frac{B^{-1}yy^T\delta\delta^T}{Q}+\frac{B^{-1}yy^T\delta\delta^Tyy^TB^{-1}}{Q^2}\right)\;\;\text{(let $k=\delta^Ty=y^T\delta$)}\\ =&\frac{Q}{k^2}\left(\delta\delta^T-\frac{k\delta y^TB^{-1}}{Q}-\frac{B^{-1}ky\delta^T}{Q}+\frac{B^{-1}k^2yy^TB^{-1}}{Q^2}\right)\\ =&\frac{Q\delta\delta^T}{k^2}-\frac{\delta y^TB^{-1}}{k}-\frac{B^{-1}y\delta^T}{k}+\frac{B^{-1}yy^TB^{-1}}{Q} \end{split}$
现在，我们有
$\begin{split} B_{k+1}^{-1} &=H^{-1}+\frac{Q\delta\delta^T}{k^2}-\frac{\delta y^TB^{-1}}{k}-\frac{B^{-1}y\delta^T}{k}+\frac{B^{-1}yy^TB^{-1}}{Q}\\ &=B^{-1}+\frac{Q\delta\delta^T}{k^2}-\frac{\delta y^TB^{-1}}{k}-\frac{B^{-1}y\delta^T}{k}\\ &=\left(I-\frac{\delta y^T}{k}\right)B^{-1}-\frac{B^{-1}y\delta^T}{k}+\frac{(y^T\delta+y^TB^{-1}y)\delta\delta^T}{k^2}\\ &=\left(I-\frac{\delta y^T}{k}\right)B^{-1}-\frac{B^{-1}y\delta^T}{k}+\frac{\delta\delta^T}{k}+\frac{y^TB^{-1}y\delta\delta^T}{k^2}\\ &\quad\quad\text{(Note that $y^TB^{-1}y$ is scalar, so $y^TB^{-1}y\delta\delta^T=\delta y^TB^{-1}y\delta^T$)}\\ &=\left(I-\frac{\delta y^T}{k}\right)B^{-1}-\frac{B^{-1}y\delta^T}{k}+\frac{\delta\delta^T}{k}+\frac{\delta y^T }{k}\frac{B^{-1}y\delta^T}{k}\\ &=\left(I-\frac{\delta y^T}{k}\right)B^{-1}-\left(I-\frac{\delta y^T}{k}\right)\frac{B^{-1}y\delta^T}{k}+\frac{\delta\delta^T}{k}\\ &=\left(I-\frac{\delta y^T}{k}\right)B^{-1}\left(I-\frac{\delta y^T}{k}\right)+\frac{\delta\delta^T}{k} \end{split}$
于是，可以求得 $B^{-1}_{k+1}$ 为 $B^{-1}_{k+1}=\left(I-\frac{\delta_k y_k^T}{\delta_k^T y_k}\right)B_k^{-1}\left(I-\frac{\delta_k y_k^T}{\delta_k^T y_k}\right)+\frac{\delta_k\delta_k^T}{\delta_k^T y_k}$

Sherman-Morrison公式在BFGS算法的应用
Sherman-Morrison公式：设为可逆矩阵，，则可逆当且仅当，并且其逆矩阵是在BFGS算法中，已经得到递...
BFGS算法
BFGS算法详细介绍
BFGS, L-BFGS算法
BFGS拟牛顿法的基础上，进一步绕过海塞逆矩阵的存储；L-BFGS，在BFGS的基础上，采取一些进一步的近似措施，...
L-BFGS算法
BFGS算法是用来求解最优化问题的，在这个算法中，相对于普通的牛顿迭代法有很大的改进。链接：http://blog...
L-BFGS算法介绍
本文由作者林洋港授权网易云社区发布。一、L-BFGS是什么 L-BFGS是解无约束非线性规划问题最常用的方法，具...
L-BFGS算法介绍
本文由作者林洋港授权网易云社区发布。一、L-BFGS是什么 L-BFGS是解无约束非线性规划问题最常用的方法，具...
GD 以外的优化方案
L-BFGS or Conjugate Gradients win. Large-batch L-BFGS ext...
2018-12-15逻辑回归高级优化
高级优化 “共轭梯度”，“BFGS”和“L-BFGS”是更复杂，更快速的优化θ的方法，可用于代替梯度下降。但是建议...
啊哈!算法
《啊哈!算法》是一本充满智慧和趣味的算法入门书。没有枯燥的描述，没有难懂的公式，一切以实际应用为出发点，通过幽默的...
2018-10-15
你的人生算法是什么？人生算法这个提法很好，是一个人方法论的公式总结。和思维模型有的一批，只是更偏向于应用。这本...