逆行列補題とBFGSへの応用

#逆行列補題について
まずブロック行列とその逆行列から話を始めよう。
$I_{n},I_{m},P,Q,R,S$をそれぞれ以下の条件を満たす行列とする。

$・I_{n}:n×n単位行列$ , $I_{m}:m×m単位行列$
$・P:n×n行列$ , $Q:n×m行列$ , $R:m×m行列$ , $S:m×n行列$
$・P,Rはそれぞれ逆行列を持つ$
$・P+QRS$  $及び$ $R^{-1}+SP^{-1}Q$ はそれぞれ逆行列を持つ

その上で以下のブロック行列を考えよう。

```math
\begin{pmatrix}
P & -Q \\
S & R^{-1}
\end{pmatrix}
```
この行列は次のように分解できる。

```math
\begin{align}
\begin{pmatrix}
P & -Q \\
S & R^{-1}
\end{pmatrix}
&=\begin{pmatrix}
I_{n} & -QR \\
0 & I_{m}
\end{pmatrix}
\begin{pmatrix}
P+QRS & 0 \\
0 &R^{-1}
\end{pmatrix}
\begin{pmatrix}
I_{n} & 0 \\
RS & I_{m}
\end{pmatrix}\\
\begin{pmatrix}
P & -Q \\
S & R^{-1}
\end{pmatrix}
&=\begin{pmatrix}
I_{n} & 0 \\
SP^{-1} & I_{m}
\end{pmatrix}
\begin{pmatrix}
P & 0 \\
0 &R^{-1}+SP^{-1}Q
\end{pmatrix}
\begin{pmatrix}
I_{n} & -P^{-1}Q \\
0 & I_{m}
\end{pmatrix}
\end{align}
```

ところで$X,Y,Z$がそれぞれ逆行列を持つ場合、行列$XYZ$の逆行列について、
$(XYZ)^{-1}=Z^{-1}Y^{-1}X^{-1}$が成り立つ。
また上三角行列,下三角行列の逆行列について、

```math
\begin{align}
\begin{pmatrix}
I_{n} & -QR \\
0 & I_{m}
\end{pmatrix}^{-1}
&=
\begin{pmatrix}
I_{n} & QR \\
0 & I_{m}
\end{pmatrix}\\

\begin{pmatrix}
I_{n} & 0 \\
RS & I_{m}
\end{pmatrix}^{-1}
&=
\begin{pmatrix}
I_{n} & 0 \\
-RS & I_{m}
\end{pmatrix}\\

\begin{pmatrix}
I_{n} & 0 \\
SP^{-1} & I_{m}
\end{pmatrix}^{-1}
&=
\begin{pmatrix}
I_{n} & 0 \\
-SP^{-1} & I_{m}
\end{pmatrix}\\

\begin{pmatrix}
I_{n} & -P^{-1}Q \\
0 & I_{m}
\end{pmatrix}^{-1}
&=
\begin{pmatrix}
I_{n} & P^{-1}Q \\
0 & I_{m}
\end{pmatrix}\\

\end{align}
```
がそれぞれ成り立つ。
これらを踏まえて先のブロック行列の逆行列を考えよう。
すると

```math
\begin{align}
\begin{pmatrix}
P & -Q \\
S & R^{-1}
\end{pmatrix}^{-1}
&=
\begin{pmatrix}
I_{n} & 0 \\
RS & I_{m}
\end{pmatrix}^{-1}
\begin{pmatrix}
P+QRS & 0 \\
0 &R^{-1}
\end{pmatrix}^{-1}
\begin{pmatrix}
I_{n} & -QR \\
0 & I_{m}
\end{pmatrix}^{-1}\\
&=
\begin{pmatrix}
I_{n} & 0 \\
-RS & I_{m}
\end{pmatrix}
\begin{pmatrix}
(P+QRS)^{-1} & 0 \\
0 &R
\end{pmatrix}
\begin{pmatrix}
I_{n} & QR \\
0 & I_{m}
\end{pmatrix}\\
&=
\begin{pmatrix}
(P+QRS)^{-1} & (P+QRS)^{-1}QR \\
-RS(P+QRS)^{-1} & R-RS(P+QRS)^{-1}QR
\end{pmatrix}...①
\end{align}
```

```math
\begin{align}
\begin{pmatrix}
P & -Q \\
S & R^{-1}
\end{pmatrix}^{-1}
&=
\begin{pmatrix}
I_{n} & -P^{-1}Q \\
0 & I_{m}
\end{pmatrix}^{-1}
\begin{pmatrix}
P & 0 \\
0 &R^{-1}+SP^{-1}Q
\end{pmatrix}^{-1}
\begin{pmatrix}
I_{n} & 0 \\
SP^{-1} & I_{m}
\end{pmatrix}^{-1}\\
&=
\begin{pmatrix}
I_{n} & P^{-1}Q \\
0 & I_{m}
\end{pmatrix}
\begin{pmatrix}
P^{-1} & 0 \\
0 & (R^{-1}+SP^{-1}Q )^{-1}
\end{pmatrix}
\begin{pmatrix}
I_{n} & 0 \\
-SP^{-1} & I_{m}
\end{pmatrix}\\
&=
\begin{pmatrix}
P^{-1}-P^{-1}Q(R^{-1}+SP^{-1}Q)^{-1}SP^{-1} & P^{-1}Q(R^{-1}+SP^{-1}Q)^{-1} \\
-(R^{-1}+SP^{-1}Q)^{-1}SP^{-1} & (R^{-1}+SP^{-1}Q)^{-1}
\end{pmatrix}...②
\end{align}
```

式①,②を比較すれば、

```math
(P+QRS)^{-1}=P^{-1}-P^{-1}Q(R^{-1}+SP^{-1}Q)^{-1}SP^{-1}
```
が得られる。これを$逆行列補題(Sherman–Morrison-Woodburyの公式)$という。

さらに逆行列補題の特別な場合を考えよう。
$u,vをn次元列ベクトル,wをスカラー,Pを逆行列を持つn×n行列$とする。
このとき$v^{T}P^{-1}u$がスカラーになることを踏まえれば、

```math
(P+\frac{uv^{T}}{w})^{-1}=P^{-1}-\frac{P^{-1}uv^{T}P^{-1}}{w+v^{T}P^{-1}u}...③
```

が得られる。
これが後述の$BFGS(H公式)$の導出に深く関わってくる。


#準ニュートン法について
$B_{k}$を正定値対称行列として、関数$f(x_{k}+d)$を次のように近似する。

```math
f(x_{k}+d) \approx f(x_{k})+▽f(x_{k})^{T}d+\frac{1}{2}d^{T}B_{k}d\\
d=x-x_{k}
```
ここで、関数$f(x_{k}+d)$をdの関数としてdで微分しその解を$d_{k}$した、

```math
d_{k}=-B^{-1}_{k}▽f(x_{k})
```
を利用して、関数$f(x)=0$の数値解を求めるアルゴリズムを準ニュートン法という。
※$B_{k}$が正定値対称行列であるために、以下の条件を満たさなくてはいけない。また(3)をセカント条件という。

```math
\begin{align}
(1)s_{k}&=x_{k+1}-x_{k}\\
(2)y_{k}&=▽f(x_{k+1})-▽f(x_{k})\\
(3)y_{k}&=B_{k+1}s_{k}\\
\end{align}
```
さてセカント条件を満たす$B_{k}$のなかで代表的なものが以下の$BFGS(B公式)$だろう。

```math
B_{k+1}=
(B_{k}+\frac{y_{k}y^{T}_{k}}{s^{T}_{k}y_{k} } )
-(\frac{B_{k}s_{k}s^{T}_{k}B_{k} }{s^{T}_{k}B_{k}s_{k}})
```

この逆行列を用いて$d_{k}$を求めるというのが準ニュートン法の流れになるが、しかしわざわざ$B_{k}$の逆行列を求めるのは間怠こしい。そこで先述の逆行列補題の出番となる。
つまり逆行列補題を利用して$B_{k}$の逆行列を$H_{k}$とした上で、$d_{k}=-H_{k}▽f(x_{k})$を直接求めようというわけだ。


#逆行列補題によるBFGS(H公式)の導出
式③を思い出してほしい。

```math
(P+\frac{uv^{T}}{w})^{-1}=P^{-1}-\frac{P^{-1}uv^{T}P^{-1}}{w+v^{T}P^{-1}u}
```
これを利用して、行列$B_{k}$の逆行列を求めよう。
すると、

```math
B^{-1}_{k+1}=
(B_{k}+\frac{y_{k}y^{T}_{k}}{s^{T}_{k}y_{k} } )^{-1}
+
\frac{(B_{k}+\frac{y_{k}y^{T}_{k}}{s^{T}_{k}y_{k}})^{-1}B_{k}s_{k}s^{T}_{k}B_{k}(B_{k}+\frac{y_{k}y^{T}_{k}}{s^{T}_{k}y_{k}})^{-1}}{s^{T}_{k}B_{k}s_{k}-s^{T}_{k}B_{k}(B_{k}+\frac{y_{k}y^{T}_{k}}{s^{T}_{k}y_{k}})^{-1}B_{k}s_{k}}・・・④
```
が得られる。ここで式④右辺第1項について、

```math
(B_{k}+\frac{y_{k}y^{T}_{k}}{s^{T}_{k}y_{k} } )^{-1}
=B^{-1}_{k}-\frac{B^{-1}_{k}y_{k}y^{T}_{k}B^{-1}_{k}}{s^{T}_{k}y_{k}+y^{T}_{k}B^{-1}_{k}y_{k}}・・・⑤
```
となる。式⑤を踏まえて式④右辺第2項を鑑みると分子・分母はそれぞれ次の通りとなる。

```math
\begin{align}
(B_{k}+\frac{y_{k}y^{T}_{k}}{s^{T}_{k}y_{k}})^{-1}B_{k}s_{k}s^{T}_{k}B_{k}(B_{k}+\frac{y_{k}y^{T}_{k}}{s^{T}_{k}y_{k}})^{-1}
&=(I-\frac{B^{-1}y_{k}y^{T}_{k}}{s^{T}_{k}y_{k}+y^{T}_{k}B^{-1}_{k}y_{k}})s_{k}s^{T}_{k}(I-\frac{y_{k}y^{T}_{k}B^{-1}}{s^{T}_{k}y_{k}+y^{T}_{k}B^{-1}_{k}y_{k}})\\
&=s_{k}s^{T}_{k}-\frac{s^{T}_{k}y_{k}}{s^{T}_{k}y_{k}+y^{T}_{k}B^{-1}_{k}y_{k}}(B^{-1}_{k}y_{k}s^{T}_{k}+s_{k}y^{T}_{k}B^{-1}_{k})+(\frac{s^{T}_{k}y_{k}}{s^{T}_{k}y_{k}+y^{T}_{k}B^{-1}_{k}y_{k}})
^2B^{-1}_{k}y_{k}y^{T}_{k}B^{-1}_{k}・・・⑥
\end{align}
```
※$I$は単位行列

```math
{s^{T}_{k}B_{k}s_{k}-s^{T}_{k}B_{k}(B_{k}+\frac{y_{k}y^{T}_{k}}{s^{T}_{k}y_{k}})^{-1}B_{k}s_{k}}
=\frac{(s^{T}_{k}y_{k})^{2}}{s^{T}_{k}y_{k}+y^{T}_{k}B^{-1}_{k}y_{k}}・・・⑦
```

従って式⑤,⑥,⑦を整理することにより、式④について行列$B_{k}$の逆行列を$H_{k}$と置き換えれば、

```math
\begin{align}
H_{k+1}&=H_{k}-\frac{H_{k}y_{k}s^{T}_{k}+s_{k}y^{T}_{k}H_{k}}{s^{T}_{k}y_{k}}+(1+\frac{y^{T}_{k}H_{k}y_{k}}{s^{T}_{k}y_{k}})\frac{s_{k}s^{T}_{k}}{s^{T}_{k}y_{k}}\\
&= (I-\frac{y_{k}s^{T}_{k}}{s^{T}_{k}y_{k}})^{T}H_{k}(I-\frac{y_{k}s^{T}_{k}}{s^{T}_{k}y_{k}})+\frac{s_{k}s^{T}_{k}}{s^{T}_{k}y_{k}}
\end{align}
```
が得られる。こうして$BFGS(H公式)$が導かれる。
#準ニュートン法の流れ
さて$BFGS(B公式,H公式)$による流れは以下の通り。
・$BFGS(B公式)$
$(step:1)$初期値$x_{0}、B_{0}$(通常は単位行列)を選び、k:=0とする
$(step:2)$$▽f(x_{k})=0$ならば計算終了。$▽f(x\_{k})\neq 0$ならば$d\_{k}=-B^{-1}\_{k}▽f(x_{k})$を求める。
$(step:3)α\_{k}$をステップ幅として、$x\_{k+1}=x\_{k}+α\_{k}d\_{k}$とする$^{※}$
$(step:4)s\_{k}$及び$y\_{k}$を算出
$(step:5)BFGS(B公式)$により行列$B_{k}$を更新

```math
B_{k+1}=
(B_{k}+\frac{y_{k}y^{T}_{k}}{s^{T}_{k}y_{k} } )
-(\frac{B_{k}s_{k}s^{T}_{k}B_{k} }{s^{T}_{k}B_{k}s_{k}})
```
$(step:6)k:\=k+1$として$(step:1)$に戻る

・$BFGS(H公式)$
$(step:1)$初期値$x_{0}、H_{0}$(通常は単位行列)を選び、k:=0とする
$(step:2)$$▽f(x_{k})=0$ならば計算終了。$▽f(x\_{k})\neq 0$ならば$d\_{k}=-H\_{k}▽f(x_{k})$を求める。
$(step:3)α\_{k}$をステップ幅として、$x\_{k+1}=x\_{k}+α\_{k}d\_{k}$とする$^{※}$
$(step:4)s\_{k}$及び$y\_{k}$を算出
$(step:5)BFGS(H公式)$により行列$H_{k}$を更新

```math
\begin{align}
H_{k+1}&= (I-\frac{y_{k}s^{T}_{k}}{s^{T}_{k}y_{k}})^{T}H_{k}(I-\frac{y_{k}s^{T}_{k}}{s^{T}_{k}y_{k}})+\frac{s_{k}s^{T}_{k}}{s^{T}_{k}y_{k}}
\end{align}
```
$(step:6)k:\=k+1$として$(step:1)$に戻る

こうして関数$f(x_{k})=0$の数値解が求められるわけだ。

※ステップ幅計算については$Appendix$参照
#Appendix
上述の$(step:3)$ステップ幅$α\_{k}$は以下の$Armijo条件,Wolfe条件$に基づいて算出することが一般的。

・$Armijo条件$
$0<ξ<1$となる定数$ξ$について

```math
f(x_{k}+α_{k}d_{k}) \leq f(x_{k}) + ξα_{k}▽f(x_{k})^{T}d_{k} 
```
を満たす$α_{k}>0$をステップ幅とする。

・$Wolfe条件$
$0<ξ\_{1}<ξ\_{2}<1$となる定数$ξ\_{1},ξ\_{2}$について

```math
f(x_{k}+α_{k}d_{k}) \leq f(x_{k}) + ξ_{1}α_{k}▽f(x_{k})^{T}d_{k} \\
ξ_{2}▽f(x_{k})^{T}d_{k} \leq ▽f(x_{k}+α_{k}d_{k})^{T}d_{k}
```
を満たす$α_{k}>0$をステップ幅とする。

#参考文献
・D.A.ハーヴィル「統計のための行列代数」(丸善出版)
・矢部博「工学基礎 最適化とその応用」(数理工学社)
・福島雅夫「数理計画入門 新版」(朝倉書店)