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

2019-09-25 本文已影响0人 Azur_wxj

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算法的应用

猜你喜欢

热点阅读