準Newton法
概要
準Newton法（quasi-Newton method）とは、方程式 $F(x)=0$（$F\colon\mathbb R^d\to\mathbb R^d$）を Newton 法と同じ形の反復 $x_{k+1}=x_k-B_k^{-1}F(x_k)$ で解くとき、Jacobi 行列の代わりに、割線方程式 $B_{k+1}(x_{k+1}-x_k)=F(x_{k+1})-F(x_k)$ を満たすよう低階数の修正で更新する行列 $B_k$ を使う方法の総称である。方程式には Broyden の方法、最小化には BFGS 法が代表的である。$x_k\to x^*$ のとき、超 1 次収束は $B_k$ が進む方向について $F'(x^*)$ を近似することと同値で（Dennis–Moré の定理）、Broyden の方法は $x_0$ と $B_0$ がともに十分よければ超 1 次収束する。
準Newton法（quasi-Newton method）は、多変数の方程式 $F(x)=0$ を Newton法 と同じ形の反復 $x_{k+1}=x_k-B_k^{-1}F(x_k)$ で解くとき、Jacobi行列 $F'(x_k)$ の代わりに、反復の途中で得た関数値だけから作る行列 $B_k$ を使う方法の総称である。$F\colon\mathbb R^d\to\mathbb R^d$ の Newton 法は毎回 $d^2$ 個の偏導関数を計算し、新しい行列の連立 1 次方程式を解く。準Newton法では $B_k$ を前の $B_{k-1}$ に階数の低い行列を足して作るので、偏導関数が要らず、逆行列も前のものから安く更新できる。
$B_{k+1}$ に課す条件は 割線方程式 $B_{k+1}(x_{k+1}-x_k)=F(x_{k+1})-F(x_k)$ である。1 変数ではこれで $B_{k+1}$ が差分商に決まり、割線法 になる。$d\ge2$ では 1 つに決まらないので、どう選ぶかで方法が分かれる。この記事では、方程式に使う Broyden の方法と、最小化に使う BFGS 法を定義し、次を証明する。
- Broyden の更新は、割線方程式を満たす行列のうち前の行列からの変化が最も小さいものである。
- $x^*$ に収束する列について、超 1 次収束は「$B_k$ が進む方向 $s_k$ について $F'(x^*)$ を近似すること」と同値である（Dennis–Moré の定理）。$B_k\to F'(x^*)$ は要らない。
- Broyden の方法は、$x_0$ が零点に近く $B_0$ が $F'(x^*)$ に近ければ、局所的に超 1 次収束する。
定義と使える条件
この記事では、ベクトルのノルムは Euclid ノルム $\|v\|=\sqrt{v^{\mathsf T}v}$、行列 $M$ のノルムはそれから決まる作用素ノルム $\|M\|=\max_{\|v\|=1}\|Mv\|$ とし、Frobenius ノルムを $\|M\|_F:=\bigl(\sum_{i,j}M_{ij}^2\bigr)^{1/2}$ とする。$\|M\|\le\|M\|_F$、$\|uv^{\mathsf T}\|_F=\|u\|\|v\|$ である。
$D\subset\mathbb R^d$ を開集合、$F\colon D\to\mathbb R^d$ とする。$x_0\in D$ と正則行列 $B_0$ から出発し、
$$
x_{k+1}:=x_k-B_k^{-1}F(x_k),\qquad s_k:=x_{k+1}-x_k,\qquad y_k:=F(x_{k+1})-F(x_k)
$$
とし、次の行列 $B_{k+1}$ を、$B_k$ に階数 $2$ 以下の行列を足して 割線方程式
$$
B_{k+1}s_k=y_k
$$
を満たすように選ぶ反復を 準Newton法 という。$F(x_k)=0$ となったら止める。
- Broyden の方法：$s_k\ne0$ のとき
$$ B_{k+1}:=B_k+\frac{(y_k-B_ks_k)\,s_k^{\mathsf T}}{s_k^{\mathsf T}s_k}. $$ - BFGS 法：$f\colon D\to\mathbb R$ を $C^1$ 級として $F=\nabla f$ に準Newton法を当てる（$\nabla f(x)=0$ を解いて $f$ の停留点を探す）。$B_k$ を対称行列とし、$s_k^{\mathsf T}B_ks_k\ne0$、$y_k^{\mathsf T}s_k\ne0$ のとき
$$ B_{k+1}:=B_k-\frac{B_ks_ks_k^{\mathsf T}B_k}{s_k^{\mathsf T}B_ks_k}+\frac{y_ky_k^{\mathsf T}}{y_k^{\mathsf T}s_k}. $$
どちらも割線方程式を満たす：Broyden では $B_{k+1}s_k=B_ks_k+(y_k-B_ks_k)=y_k$、BFGS では $B_{k+1}s_k=B_ks_k-B_ks_k+y_k=y_k$ である。BFGS の名は Broyden、Fletcher、Goldfarb、Shanno による。
使える条件をまとめる。$x^*$ を $F(x^*)=0$ を満たす点とし、$A:=F'(x^*)$ と書く。
- (i) $F$ は $D$ で微分可能で、$F'$ は $x^*$ で連続、$A$ は正則。
- (ii) Broyden の方法の収束には、$x^*$ での Lipschitz 型の条件 $\|F'(x)-A\|\le\gamma\|x-x^*\|$（$x\in D$）を使う。
- (iii) $x_0$ が $x^*$ に近く、しかも $B_0$ が $A$ に近い。$x_0$ が近いだけでは足りない（反例の表）。
- (iv) BFGS 法で $B_{k+1}$ を正定値に保つには 曲率条件 $y_k^{\mathsf T}s_k>0$ が要る。
公式の表
| 公式 | 使える条件 | 根拠 |
|---|---|---|
| Broyden：$B_{k+1}=B_k+\dfrac{(y_k-B_ks_k)s_k^{\mathsf T}}{s_k^{\mathsf T}s_k}$ | $s_k\ne0$ | def-qn-updates |
| Broyden の逆行列 $H_k=B_k^{-1}$：$H_{k+1}=H_k+\dfrac{(s_k-H_ky_k)s_k^{\mathsf T}H_k}{s_k^{\mathsf T}H_ky_k}$ | $s_k^{\mathsf T}H_ky_k\ne0$ | prop-qn-inverse |
| BFGS：$B_{k+1}=B_k-\dfrac{B_ks_ks_k^{\mathsf T}B_k}{s_k^{\mathsf T}B_ks_k}+\dfrac{y_ky_k^{\mathsf T}}{y_k^{\mathsf T}s_k}$ | $B_k$ 正定値、$y_k^{\mathsf T}s_k>0$ | prop-qn-bfgs |
| $d=1$ では $B_{k+1}=\dfrac{F(x_{k+1})-F(x_k)}{x_{k+1}-x_k}$（割線法） | $x_{k+1}\ne x_k$ | 割線方程式 |
| 超 1 次収束 $\iff\dfrac{\Vert (B_k-A)s_k\Vert }{\Vert s_k\Vert }\to0$ | $x_k\to x^*$、$A$ 正則 | thm-qn-dennis-more |
| $\Vert B_{k+1}-A\Vert _F\le\Vert B_k-A\Vert _F+\gamma\max(\Vert e_k\Vert ,\Vert e_{k+1}\Vert )$ | Broyden、(ii) | lem-qn-deterioration |
| $B_k=B$ に固定すると、超 1 次収束しない | $x_k\to x^*$、$B-A$ が正則 | thm-qn-dennis-more の後の説明、ex-qn-chord |
主定理と証明
道具：平均値の不等式
$D\subset\mathbb R^d$ を凸な開集合、$F\colon D\to\mathbb R^d$ を微分可能、$A$ を $d$ 次正方行列とする。$u,v\in D$ について
$$
\|F(u)-F(v)-A(u-v)\|\le\sup_{0\le t\le1}\|F'(v+t(u-v))-A\|\cdot\|u-v\|.
$$
とくに $\|F'(x)-A\|\le\gamma\|x-x^*\|$（$x\in D$）なら、左辺は $\gamma\max(\|u-x^*\|,\|v-x^*\|)\|u-v\|$ 以下である。
証明を開く
左辺のベクトル $r$ が $0$ なら明らか。そうでなければ $w:=r/\|r\|$ とし、$\varphi(t):=w^{\mathsf T}\bigl(F(v+t(u-v))-tA(u-v)\bigr)$ とおく。$\varphi$ は $[0,1]$ で微分可能で $\varphi'(t)=w^{\mathsf T}\bigl(F'(v+t(u-v))-A\bigr)(u-v)$ である。平均値の定理 により、ある $\tau\in(0,1)$ で $\|r\|=w^{\mathsf T}r=\varphi(1)-\varphi(0)=\varphi'(\tau)\le\|F'(v+\tau(u-v))-A\|\,\|u-v\|$ である（Cauchy–Schwarzの不等式）。後半は $\|v+t(u-v)-x^*\|=\|t(u-x^*)+(1-t)(v-x^*)\|\le\max(\|u-x^*\|,\|v-x^*\|)$ による。$\square$
Broyden の更新は最小の変化
$s\ne0$、$y\in\mathbb R^d$、行列 $B$ に対し $B_+:=B+\dfrac{(y-Bs)s^{\mathsf T}}{s^{\mathsf T}s}$ とおく。
- $B_+s=y$ であり、$s$ に直交するすべての $q$ について $B_+q=Bq$ である。この 2 条件を満たす行列は $B_+$ だけである。
- $Ms=y$ を満たすすべての行列 $M$ について $\|B_+-B\|_F\le\|M-B\|_F$ であり、等号は $M=B_+$ のときに限る。
証明を開く
1：$s^{\mathsf T}q=0$ なら $(y-Bs)s^{\mathsf T}q=0$ なので $B_+q=Bq$ である。$\mathbb R^d$ は $s$ と $s$ の直交補空間の直和だから、2 条件は $B_+$ の値をすべてのベクトルで決める。2：$P:=ss^{\mathsf T}/(s^{\mathsf T}s)$ は $s$ の方向への直交射影である。$Ms=y$ なら $(M-B)s=y-Bs$ なので $B_+-B=\dfrac{(y-Bs)s^{\mathsf T}}{s^{\mathsf T}s}=(M-B)P$ である。行列 $N$ の各行 $n^{\mathsf T}$ について $\|n^{\mathsf T}\|^2=\|n^{\mathsf T}P\|^2+\|n^{\mathsf T}(I-P)\|^2$（直交分解）だから、行ごとに足して $\|N\|_F^2=\|NP\|_F^2+\|N(I-P)\|_F^2$ である。$N=M-B$ とすると $\|B_+-B\|_F^2=\|M-B\|_F^2-\|(M-B)(I-P)\|_F^2\le\|M-B\|_F^2$ で、等号は $(M-B)(I-P)=0$、すなわち $M-B=(M-B)P=B_+-B$ のときに限る。$\square$
1 は「$s$ と直交する方向については新しい情報がないので、そこでの予測は変えない」という Broyden の考え方そのものである（Bro65 §4 の Method 1）。
Dennis–Moré の定理
$D\subset\mathbb R^d$ を凸な開集合、$F\colon D\to\mathbb R^d$ を微分可能とし、$x^*\in D$ で $F'$ が連続、$A:=F'(x^*)$ が正則とする。正則行列の列 $(B_k)$ と $x_0\in D$ について、$x_{k+1}=x_k-B_k^{-1}F(x_k)$ で定まる列が $D$ にとどまり $x^*$ に収束し、すべての $k$ で $x_k\ne x^*$ とする。$e_k:=x_k-x^*$、$s_k:=x_{k+1}-x_k$ とおく。このとき次は同値である。
- $F(x^*)=0$ で、$(x_k)$ は $x^*$ に超 1 次収束する（$\|e_{k+1}\|/\|e_k\|\to0$）。
- $\displaystyle\lim_{k\to\infty}\frac{\|(B_k-A)s_k\|}{\|s_k\|}=0$。
まず $s_k\ne0$ である：ある $k$ で $s_k=0$ なら $F(x_k)=0$ で、以後 $x_j=x_k$ が続き、極限 $x^*$ が $x_k$ に等しくなって仮定に反する。$\beta:=\|A^{-1}\|$ とおき、
$$
\rho_k:=\sup\{\|F'(z)-A\|:z\text{ は }x_k,x_{k+1},x^*\text{ のどれか 2 点を結ぶ線分上}\}
$$
とおくと、線分は $x^*$ に縮むので $F'$ の $x^*$ での連続性から $\rho_k\to0$ である。$B_ks_k=-F(x_k)$ から
$$
(B_k-A)s_k=\bigl[F(x_{k+1})-F(x_k)-As_k\bigr]-F(x_{k+1})\qquad(\ast)
$$
であり、lem-qn-mvi により右辺第 1 項のノルムは $\rho_k\|s_k\|$ 以下である。
2 ⇒ 1：$(\ast)$ から $\|F(x_{k+1})\|/\|s_k\|\le\|(B_k-A)s_k\|/\|s_k\|+\rho_k\to0$ である。$\|s_k\|\to0$ なので $F(x_{k+1})\to0$ で、$F$ の連続性から $F(x^*)=0$ である。すると lem-qn-mvi により $\|F(x_{k+1})-Ae_{k+1}\|\le\rho_k\|e_{k+1}\|$、また $\|Ae_{k+1}\|\ge\|e_{k+1}\|/\beta$ なので、$\rho_k\le1/(2\beta)$ となる $k$ で $\|F(x_{k+1})\|\ge\|e_{k+1}\|/(2\beta)$ である。$\|s_k\|\le\|e_{k+1}\|+\|e_k\|$ と合わせ、$p_k:=\|e_{k+1}\|/\|e_k\|$ とおくと
$$
\frac{1}{2\beta}\cdot\frac{p_k}{1+p_k}\le\frac{\|F(x_{k+1})\|}{\|s_k\|}\to0
$$
となる。$p_k/(1+p_k)\to0$ から $p_k\to0$ である。
1 ⇒ 2：$F(x^*)=0$ と lem-qn-mvi から $\|F(x_{k+1})\|\le(\|A\|+\rho_k)\|e_{k+1}\|$、また $\|s_k\|\ge\|e_k\|-\|e_{k+1}\|=(1-p_k)\|e_k\|$ である。$p_k\to0$ なので $\|F(x_{k+1})\|/\|s_k\|\le(\|A\|+\rho_k)p_k/(1-p_k)\to0$ であり、$(\ast)$ から 2 が従う。$\square$
2 は $B_k$ が 進む方向 $s_k$ について $A$ を近似することだけを求めている。$B_k$ が行列として $A$ に収束しなくても超 1 次収束は起こりうるし、実際に多くの準Newton法で $B_k\not\to A$ となる例がある（DM74 §4）。逆に $B_k$ を固定行列 $B$ に保つ方法は、$B-A$ が正則なら超 1 次収束しない：超 1 次収束すれば 2 から単位ベクトル $s_k/\|s_k\|$ の集積点 $u$ で $(B-A)u=0$ となるからである（ex-qn-chord）。
Broyden の方法の局所超 1 次収束
lem-qn-mvi の仮定の下で、$x^*\in D$ と $A$ について $\|F'(x)-A\|\le\gamma\|x-x^*\|$（$x\in D$）とする。$x_k,x_{k+1}\in D$、$s_k=x_{k+1}-x_k\ne0$、$y_k=F(x_{k+1})-F(x_k)$ とし、$B_{k+1}$ を Broyden の更新、$E_k:=B_k-A$、$E_{k+1}:=B_{k+1}-A$、$\theta_k:=\|E_ks_k\|/\|s_k\|$、$\sigma_k:=\max(\|x_k-x^*\|,\|x_{k+1}-x^*\|)$ とおく。このとき
$$
\|E_{k+1}\|_F\le\sqrt{\|E_k\|_F^2-\theta_k^2}+\gamma\sigma_k\le\|E_k\|_F+\gamma\sigma_k
$$
である。
証明を開く
$P:=s_ks_k^{\mathsf T}/(s_k^{\mathsf T}s_k)$ とおく。$y_k-B_ks_k=(y_k-As_k)-E_ks_k$ と $E_ks_ks_k^{\mathsf T}/(s_k^{\mathsf T}s_k)=E_kP$ から $E_{k+1}=E_k(I-P)+\dfrac{(y_k-As_k)s_k^{\mathsf T}}{s_k^{\mathsf T}s_k}$ である。prop-qn-least-change の証明と同じ直交分解で $\|E_k(I-P)\|_F^2=\|E_k\|_F^2-\|E_kP\|_F^2$、また $\|E_kP\|_F=\|E_ks_k\|\|s_k\|/\|s_k\|^2=\theta_k$ である。第 2 項の Frobenius ノルムは $\|y_k-As_k\|/\|s_k\|$ で、lem-qn-mvi により $\gamma\sigma_k$ 以下である。$\square$
$D\subset\mathbb R^d$ を凸な開集合、$F\colon D\to\mathbb R^d$ を微分可能とし、$x^*\in D$ で $F(x^*)=0$、$A:=F'(x^*)$ は正則で、ある $\gamma>0$ について $\|F'(x)-A\|\le\gamma\|x-x^*\|$（$x\in D$）とする。$\beta:=\|A^{-1}\|$、
$$
\delta:=\frac1{12\beta},\qquad\varepsilon:=\frac{\delta}{2\gamma}=\frac1{24\beta\gamma}
$$
とおき、閉球 $\{x:\|x-x^*\|\le\varepsilon\}$ が $D$ に含まれるとする。$\|x_0-x^*\|\le\varepsilon$、$\|B_0-A\|_F\le\delta$ なら、Broyden の方法について次が成り立つ。
- 反復は $x_k=x^*$ となるまで定義され、すべての $k$ で $B_k$ は正則、$\|B_k-A\|_F\le2\delta$、$\|x_{k+1}-x^*\|\le\frac14\|x_k-x^*\|$ である。
- 反復が止まらなければ $(x_k)$ は $x^*$ に超 1 次収束する。
$e_k:=x_k-x^*$、$E_k:=B_k-A$ とおく。
段 1（1 歩の評価） $\|e_k\|\le\varepsilon$、$\|E_k\|_F\le2\delta$ とする。$\|A^{-1}E_k\|\le\beta\cdot2\delta=\frac16$ である。$M:=A^{-1}E_k$ について、任意の $v$ で $\|(I+M)v\|\ge(1-\|M\|)\|v\|\ge\frac56\|v\|$ なので $I+M$ は正則で $\|(I+M)^{-1}\|\le\frac65$ である。よって $B_k=A(I+M)$ は正則で $\|B_k^{-1}\|\le\frac65\beta$ である。$F(x^*)=0$ から
$$
e_{k+1}=e_k-B_k^{-1}F(x_k)=B_k^{-1}\Bigl(E_ke_k-\bigl[F(x_k)-F(x^*)-Ae_k\bigr]\Bigr)
$$
であり、lem-qn-mvi で角括弧のノルムは $\gamma\|e_k\|^2\le\gamma\varepsilon\|e_k\|$ 以下である。したがって
$$
\|e_{k+1}\|\le\frac65\beta\,(2\delta+\gamma\varepsilon)\|e_k\|=\frac65\beta\cdot\frac{5}{24\beta}\|e_k\|=\frac14\|e_k\|.
$$
また $x_k\ne x^*$ なら $\|F(x_k)\|\ge\|Ae_k\|-\gamma\|e_k\|^2\ge(\beta^{-1}-\gamma\varepsilon)\|e_k\|>0$ なので $s_k=-B_k^{-1}F(x_k)\ne0$ で、Broyden の更新が定まる。
段 2（帰納法） $k$ についての主張「$j\le k$ で $\|e_j\|\le4^{-j}\varepsilon$、$\|E_j\|_F\le2\delta$」を示す。$k=0$ は仮定である。$k$ で成り立てば段 1 から $\|e_{k+1}\|\le4^{-(k+1)}\varepsilon$ で、$x_{k+1}$ は閉球に入る。$\sigma_j=\|e_j\|$（$\|e_{j+1}\|\le\|e_j\|$）だから lem-qn-deterioration を $j=0,\ldots,k$ で足して
$$
\|E_{k+1}\|_F\le\|E_0\|_F+\gamma\sum_{j=0}^{k}\|e_j\|\le\delta+\gamma\varepsilon\cdot\frac43=\delta+\frac23\delta<2\delta
$$
である。これで 1 が示された。
段 3（超 1 次収束） $0\le\theta\le a$、$a>0$ なら $\sqrt{a^2-\theta^2}\le a-\frac{\theta^2}{2a}$ である（右辺は $0$ 以上で、2 乗すると $a^2-\theta^2+\frac{\theta^4}{4a^2}$）。$\theta_k:=\|E_ks_k\|/\|s_k\|\le\|E_k\|\le\|E_k\|_F$ なので、lem-qn-deterioration から、$E_k\ne0$ のとき
$$
\theta_k^2\le2\|E_k\|_F\bigl(\|E_k\|_F-\|E_{k+1}\|_F+\gamma\|e_k\|\bigr)\le4\delta\bigl(\|E_k\|_F-\|E_{k+1}\|_F+\gamma\|e_k\|\bigr)
$$
である（$E_k=0$ なら $\theta_k=0$ で、右辺は lem-qn-deterioration により $0$ 以上なので同じ不等式が成り立つ）。$k=0,\ldots,N$ で足すと
$$
\sum_{k=0}^N\theta_k^2\le4\delta\Bigl(\|E_0\|_F+\gamma\sum_{k\ge0}\|e_k\|\Bigr)\le4\delta\Bigl(\delta+\frac43\gamma\varepsilon\Bigr)
$$
で、$N$ によらない。よって $\theta_k\to0$ である。$F'$ は $x^*$ で連続で（仮定の Lipschitz 型の条件から）、$x_k\to x^*$、$x_k\ne x^*$ なので、thm-qn-dennis-more の 2 が成り立ち、超 1 次収束する。$\square$
定数 $\delta,\varepsilon$ は証明が通るように選んだもので、最良ではない。この定理は「$B_0$ を $A$ の近くにとれば、その後の $B_k$ は $A$ から大きく離れない」ことを、劣化の評価の和で保証している。
$B$ が正則、$H:=B^{-1}$、$s\ne0$ とし、$B_+$ を Broyden の更新とする。$B_+$ が正則であることと $s^{\mathsf T}Hy\ne0$ は同値で、そのとき $B_+^{-1}=H+\dfrac{(s-Hy)s^{\mathsf T}H}{s^{\mathsf T}Hy}$ である。
証明を開く
$u:=(y-Bs)/(s^{\mathsf T}s)$ とおくと $B_+=B+us^{\mathsf T}=B(I+Hus^{\mathsf T})$ で、$c:=1+s^{\mathsf T}Hu=s^{\mathsf T}Hy/(s^{\mathsf T}s)$ である。$c\ne0$ なら $(I+Hus^{\mathsf T})(I-Hus^{\mathsf T}/c)=I+Hus^{\mathsf T}(1-1/c-(c-1)/c)=I$ なので $B_+$ は正則で $B_+^{-1}=(I-Hus^{\mathsf T}/c)H=H-\frac{Hus^{\mathsf T}H}{c}$、$Hu=(Hy-s)/(s^{\mathsf T}s)$ を代入すると主張の式になる（Sherman–Morrison の公式）。$c=0$ なら $(I+Hus^{\mathsf T})Hu=Hu(1+s^{\mathsf T}Hu)=0$ で、$Hu\ne0$（$c=0$ なら $s^{\mathsf T}Hu=-1$）だから $B_+$ は正則でない。$\square$
BFGS 法は正定値性を保つ
証明を開く
対称性と $B_+s=y$ は式から明らか。$z\ne0$ について、内積 $\langle a,b\rangle_B:=a^{\mathsf T}Bb$ での Cauchy–Schwarzの不等式 により $z^{\mathsf T}B_+z=\Bigl(z^{\mathsf T}Bz-\frac{(z^{\mathsf T}Bs)^2}{s^{\mathsf T}Bs}\Bigr)+\frac{(y^{\mathsf T}z)^2}{y^{\mathsf T}s}\ge0$ で、第 1 項が $0$ になるのは $z=cs$（$c\ne0$）のときに限る。そのとき第 2 項は $c^2y^{\mathsf T}s>0$ である。よって $z^{\mathsf T}B_+z>0$ である。後半：$\psi(t):=f(x_k+ts_k)$ は $[0,1]$ で狭義凸かつ微分可能なので $\psi'$ は狭義単調増加であり、$y_k^{\mathsf T}s_k=\psi'(1)-\psi'(0)>0$ である。$\square$
$B_k$ が正定値なら、$d_k:=-B_k^{-1}\nabla f(x_k)$ は $\nabla f(x_k)^{\mathsf T}d_k=-\nabla f(x_k)^{\mathsf T}B_k^{-1}\nabla f(x_k)<0$（$\nabla f(x_k)\ne0$ のとき）を満たし、$f$ が減る方向になる。最小化では、この方向に沿って刻み幅を選ぶ（直線探索）のが普通である。BFGS の式は、DM74 が式 (4.1) で complementary Davidon–Fletcher–Powell 法として扱っている更新と同じである。
計算の手順
Broyden の方法で $F(x)=0$（$F\colon\mathbb R^d\to\mathbb R^d$）を解く手順：
- 初期値 $x_0$ を選び、$B_0$ を作る。$F'(x_0)$ を 1 回だけ計算するか、差分商で近似するのが普通である（thm-qn-broyden は $B_0$ が $F'(x^*)$ に近いことを求める）。$F_0:=F(x_0)$ を計算する。
- $k=0,1,2,\ldots$ について、連立 1 次方程式 $B_ks_k=-F_k$ を解く。逆行列 $H_k=B_k^{-1}$ を持つなら $s_k=-H_kF_k$ である。
- $x_{k+1}:=x_k+s_k$、$F_{k+1}:=F(x_{k+1})$、$y_k:=F_{k+1}-F_k$ を計算する。1 回の反復で新しく計算するのは $F$ の値 1 つ（$d$ 個の成分）だけである。
- $\|s_k\|\le\mathrm{tol}\cdot\max(1,\|x_{k+1}\|)$ か $\|F_{k+1}\|\le\mathrm{tol}_F$ なら止める。超 1 次収束する列では $\|s_k\|/\|e_k\|\to1$ なので（割線法 の注意「止める判定の根拠」と同じ計算）、$\|s_k\|$ は誤差のよい見積もりになる。
- Broyden の更新で $B_{k+1}$（または prop-qn-inverse で $H_{k+1}$）を作る。$s_k^{\mathsf T}H_ky_k$ が $0$ に近いときは $B_{k+1}$ がほぼ特異になるので、$F'(x_{k+1})$ を計算して $B_{k+1}$ を作り直す。
- 反復の上限に達したら収束していないとみなし、初期値や $B_0$ を見直す。
BFGS 法で $f$ を最小化するときは、$F=\nabla f$、$B_0$ を正定値（単位行列の定数倍など）にとり、手順 2 の $s_k$ を方向 $d_k=-B_k^{-1}\nabla f(x_k)$ と刻み幅 $\lambda_k>0$ で $s_k=\lambda_kd_k$ とし、$y_k^{\mathsf T}s_k>0$ を確かめてから prop-qn-bfgs の更新をする。
例題
問い：$d=1$ の Broyden の方法を書き下す。
答え：$B_{k+1}=B_k+\dfrac{(y_k-B_ks_k)s_k}{s_k^2}=\dfrac{y_k}{s_k}=\dfrac{F(x_{k+1})-F(x_k)}{x_{k+1}-x_k}$ なので、$x_2$ 以降は 割線法 と同じ点列になる。$B_0$ は $x_1$ を決めるだけである。たとえば $F(x)=x^2-2$、$x_0=1$、$B_0=F'(1)=2$ なら $x_1=\frac32$ で、以後 $x_0=1$、$x_1=\frac32$ からの割線法である。BFGS 法も $d=1$ では $B_{k+1}=B_k-B_k+y_k^2/(y_ks_k)=y_k/s_k$ で、$f'$ に対する割線法になる。
問い：$F(x,y)=(x^2+y^2-1,\ y-x^2)$ の第 1 象限の零点 $x^*=(0.78615137\ldots,\ 0.61803398\ldots)$ を、$x_0=(1,1)$、$B_0=F'(x_0)=\begin{pmatrix}2&2\\-2&1\end{pmatrix}$ から求める。Broyden の方法、$B_k=B_0$ に固定する方法（簡易 Newton 法）、Newton 法を比べる。
使う公式：def-qn-updates、thm-qn-dennis-more。
答え：誤差 $\|x_k-x^*\|$ は次のとおり（3 つとも $x_1=(5/6,\,2/3)$ は同じ）。
| $k$ | Broyden | $B_k=B_0$ に固定 | Newton |
|---|---|---|---|
| 2 | $1.18\times10^{-2}$ | $1.88\times10^{-2}$ | $2.19\times10^{-3}$ |
| 3 | $6.85\times10^{-4}$ | $5.36\times10^{-3}$ | $2.73\times10^{-6}$ |
| 4 | $1.08\times10^{-4}$ | $1.51\times10^{-3}$ | $4.66\times10^{-12}$ |
| 5 | $6.82\times10^{-6}$ | $4.20\times10^{-4}$ | $1.38\times10^{-23}$ |
| 6 | $3.79\times10^{-8}$ | $1.15\times10^{-4}$ | |
| 7 | $3.89\times10^{-12}$ | $3.08\times10^{-5}$ |
$B_0$ を固定すると誤差は毎回 $0.27$〜$0.29$ 倍で 1 次収束である。Broyden では誤差の比 $\|e_{k+1}\|/\|e_k\|$ が $k=1,\ldots,6$ で $0.17,\,0.058,\,0.16,\,0.063,\,0.0056,\,0.00010$ と、揺れながら $0$ に近づく。Newton 法は反復の回数では速いが、毎回 Jacobi 行列を計算して新しい行列の方程式を解く。thm-qn-broyden は十分条件である。この $F$ では $\gamma=2\sqrt2$ ととれて $\beta=\|A^{-1}\|=0.636\ldots$、$\varepsilon=0.0231\ldots$、$\delta=0.131\ldots$ だが、$\|x_0-x^*\|=0.437\ldots$、$\|B_0-A\|_F=0.97\ldots$ はその範囲の外であり、それでも収束している。
問い：$F(x)=x^2-2$ を $x_{k+1}=x_k-F(x_k)/4$（$B_k=4$ に固定）で、$x_0=2$ から解く。
答え：$x_1=1.5$、$x_2=1.4375$、$x_3=1.42090\ldots$ で、誤差の比は $1-\frac{2\sqrt2}4=0.29289\ldots$ に近づく。1 次収束で超 1 次収束しない。
途中の計算を開く
$e_k:=x_k-\sqrt2$ とおくと $F(x_k)=(x_k+\sqrt2)e_k$ なので $e_{k+1}=e_k\bigl(1-\frac{x_k+\sqrt2}4\bigr)$ である。$x_k\in[\sqrt2,2]$ なら比 $1-\frac{x_k+\sqrt2}4$ は $\bigl[1-\frac{2+\sqrt2}4,\,1-\frac{2\sqrt2}4\bigr]=[0.146\ldots,\,0.292\ldots]$ に入るので、$0\le e_{k+1}\le0.293\,e_k$ で $x_{k+1}\in[\sqrt2,x_k]$ である。よって $x_k$ は $\sqrt2$ に単調に近づき、比は $1-\frac{2\sqrt2}4$ に近づく。thm-qn-dennis-more の量は $\lvert(4-2\sqrt2)s_k\rvert/\lvert s_k\rvert=4-2\sqrt2\ne0$ である。
問い：$f(x)=\frac12x^{\mathsf T}Qx$、$Q=\begin{pmatrix}2&0\\0&1\end{pmatrix}$、$B=I$、$s=(1,1)^{\mathsf T}$ で BFGS の更新をする。
答え：$y=Qs=(2,1)^{\mathsf T}$、$y^{\mathsf T}s=3>0$ で
$$
B_+=I-\frac12\begin{pmatrix}1&1\\1&1\end{pmatrix}+\frac13\begin{pmatrix}4&2\\2&1\end{pmatrix}=\begin{pmatrix}11/6&1/6\\1/6&5/6\end{pmatrix}.
$$
$B_+s=(2,1)^{\mathsf T}=y$（割線方程式）、$\operatorname{tr}B_+=\frac83>0$、$\det B_+=\frac32>0$ なので $B_+$ は正定値である。$B_+\ne Q$ だが、$s$ の方向については $B_+s=Qs$ である。
使える条件と反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 割線方程式を課して $B_k$ を更新すること | $F(x)=x^2-2$、$B_k=4$ に固定（ex-qn-chord） | 誤差の比が $0.29289\ldots$ に近づき、超 1 次収束しない |
| $B_0$ が $F'(x^*)$ に近いこと（thm-qn-broyden） | $F(x)=x^2-2$、$x_0=\sqrt2+t$（$t>0$ は任意に小さくてよい）、$B_0=\dfrac{F(x_0)}{2x_0}$ | $x_1=-x_0$、$y_0=0$ となり $B_1=0$ で、$x_2$ が定まらない |
| $F'(x^*)$ が正則であること | $F(x)=x^2$、$x_0=t$、$B_0=F'(t)=2t$（$t>0$ は任意に小さくてよい） | $x_1=t/2$ で、以後は割線法なので $x_n=t/u_{n+2}$（$u_1=u_2=1$、$u_{n+1}=u_n+u_{n-1}$ は Fibonacci 数）。誤差の比は黄金比 $\varphi=\frac{1+\sqrt5}2$ の逆数 $0.618\ldots$ に近づき 1 次収束（割線法 の例「重根では 1 次収束になる」を $t$ 倍したもの） |
| BFGS の曲率条件 $y_k^{\mathsf T}s_k>0$ | $d=1$、$f(x)=\frac{x^4}4-x^2$、$x_k=\frac12$、$B_k=1$、方向 $d_k=\frac78$、刻み幅 $\lambda_k=\frac47$（$x_{k+1}=1$） | $s_k=\frac12$、$y_k=f'(1)-f'(\frac12)=-\frac18$ で $B_{k+1}=y_k/s_k=-\frac14$ は正定値でない（prop-qn-bfgs の結論が崩れる） |
2 行目：$x_1=x_0-F(x_0)/B_0=x_0-2x_0=-x_0$ で、$F$ は偶関数なので $y_0=F(x_1)-F(x_0)=0$、$B_1=B_0+(0-B_0s_0)s_0/s_0^2=0$ である。$t\to0$ で $x_0\to\sqrt2$ だが $B_0\to0$ で、$F'(\sqrt2)=2\sqrt2$ から離れたままである。$x_0$ が零点に近いだけでは足りない。
よくある誤り
| 誤り | 正しくは | なぜ |
|---|---|---|
| 割線方程式で $B_{k+1}$ が決まるとする | $d\ge2$ では $d^2$ 個の未知数に $d$ 個の式で、決まらない。最小の変化などの追加の条件で選ぶ | prop-qn-least-change |
| 超 1 次収束には $B_k\to F'(x^*)$ が必要だとする | 必要なのは進む方向での近似 $\Vert (B_k-A)s_k\Vert /\Vert s_k\Vert \to0$ だけ | thm-qn-dennis-more |
| BFGS をどんな $s_k$ でも更新する | $y_k^{\mathsf T}s_k\le0$ だと正定値性が崩れる。直線探索で曲率条件を満たす刻み幅を選ぶか、更新を飛ばす | prop-qn-bfgs、反例の表 |
| 初期値さえ近ければ $B_0$ は何でもよい | $B_0$ も $F'(x^*)$ に近くないと破綻しうる | 反例の表 2 行目 |
補足
- Newton 法と準Newton法のどちらが速いかは、1 回の反復の費用（Jacobi 行列の計算と新しい行列の分解）と反復の回数のかね合いで決まる（ex-qn-2d）。
- 刻み幅 $\lambda_k$ をかけた $x_{k+1}=x_k-\lambda_kB_k^{-1}F(x_k)$ の形でも、thm-qn-dennis-more の 2 が成り立つなら、$F(x^*)=0$ への超 1 次収束は $\lambda_k\to1$ と同値である（DM74 Corollary 2.3。この記事では証明しない）。
- DM74 §3 は、Davidon–Fletcher–Powell 法（$H_k=B_k^{-1}$ の側の更新）の超 1 次収束を、この定理から導いている。
- 1 変数の準Newton法は 割線法 で、単根の近くでの収束の次数は黄金比である（割線法 の定理「割線法の収束の次数」）。初期値での情報から零点の存在まで保証する定理は、Newton 法については Newton–Kantorovichの定理 がある。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
