SR1法

SR1法（SR1ほう、別称：対称ランクワン法、たいしょうランクワンほう、テンプレート:Lang-en-short）とは、2点の導関数（勾配）の情報に基づいてヘッセ行列を更新する準ニュートン法の一種である。SR1法は多次元の問題に対するセカント法を一般化させたものである。更新される行列は対称行列であることは保証されるが、正定値性については保証されない。

SR1法で近似したヘッセ行列の列は緩い条件下の下で収束することが知られている。実用上でSR1法は他の解法（BFGS法やDFP法）よりも早く真のヘッセ行列に収束することが数値実験により知られている。。SR1法は疎な行列や部分分割できる問題に対して計算上の利点を有する。

2階微分可能な連続関数を $x\mapsto f(x)$ とし、勾配を $\mathrm{\nabla }f$、ヘッセ行列を $B$ とする。関数 $f$ の点 $x_0$ におけるテイラー展開は以下のように近似される:

$f(x_0+\mathrm{\Delta }x)\approx f(x_0)+\mathrm{\nabla }f(x_0{)}^T\mathrm{\Delta }x+\frac{1}{2}\mathrm{\Delta }{x}^{T}B\mathrm{\Delta }x$;

また、勾配 $\mathrm{\nabla }f$ に対するテイラー展開は以下のように近似される:

$\mathrm{\nabla }f(x_0+\mathrm{\Delta }x)\approx \mathrm{\nabla }f(x_0)+B\mathrm{\Delta }x$,

これら二つの近似式から $B$ を更新していく。ただし上記のセカント法による方程式は一意の解 $B$ をもつとは限らない。SR1法では以下のランク1更新式と呼ばれると呼ばれる式を用いて、十分に近似された対称行列 $B_k$ を計算するテンプレート:要説明:

$B_{k+1}=B_k+\frac{(y_k-B_k\mathrm{\Delta }{x}_k)(y_k-B_k\mathrm{\Delta }{x}_k{)}^T}{(y_k-B_k\mathrm{\Delta }{x}_k{)}^T\mathrm{\Delta }{x}_k}$

ただし、

$y_k=\mathrm{\nabla }f(x_k+\mathrm{\Delta }{x}_k)-\mathrm{\nabla }f(x_k)$

である。近似した行列の逆行列に対応したヘッセ行列 $H_k=B_k^{-1}$ の更新は以下のようになる:

$H_{k+1}=H_k+\frac{(\mathrm{\Delta }{x}_k-H_k{y}_k)(\mathrm{\Delta }{x}_k-H_k{y}_k{)}^T}{(\mathrm{\Delta }{x}_k-H_k{y}_k{)}^T{y}_k}$.

$B_k$ は行列の更新において $B_{k+1}=B_k+v{v}^T$ の形となれば、$B_k$ が正定値行列であれば $B_{k+1}$ も正定値行列となるが、$B_{k+1}=B_k-v{v}^T$ の形となれば、$B_{k+1}$ は正定値性が保証されない。

これまでSR1法の更新式は幾度と再発見されてきた。SR1法において更新式の分母の項がゼロとなることを回避するために、以下の条件を満たす場合にのみ近似ヘッセ行列の更新を行う手法も提案されている:

$|\mathrm{\Delta }{x}_k^T(y_k-B_k\mathrm{\Delta }{x}_k)|\ge r\Vert \mathrm{\Delta }{x}_k\Vert \cdot \Vert y_k-B_k\mathrm{\Delta }{x}_k\Vert$,

このとき、$r\in (0,1)$ は $10^{-8}$ のような十分に小さい数とする。

記憶制限

SR1更新は密な行列を使用することから、大規模問題においては計算量が高くなることがある。計算効率を高めるためにL-BFGS法と同様に記憶制限SR1法が存在する。L-SR1法では近似したヘッセ行列のすべての情報を持たずに、$m$ 個の組 $\{(s_i,y_i){\}}_{i=k-m}^{k-1}$ のみを利用して近似の行列を更新する。ただし、$\mathrm{\Delta }{x}_i:=s_i$ とし、$m$ は問題のサイズ $n$ より十分に小さい整数（$m\ll n$）とする。記憶制限による行列は以下のように表される:

$$B_k=B_0+J_k{N}_k^{-1}{J}_k^T,J_k=Y_k-B_0{S}_k,N_k=D_k+L_k+L_k^T-S_k^T{B}_0{S}_k$$

$$S_k=\left[\begin{array}{cccc}{s}_{k-m}& s_{k-m+1}& \dots & s_{k-1}\end{array}\right],$$ $$Y_k=\left[\begin{array}{cccc}{y}_{k-m}& y_{k-m+1}& \dots & y_{k-1}\end{array}\right],$$

$$(L_k{)}_{ij}=s_{i-1}^T{y}_{j-1},D_k=s_{i-1}^T{y}_{i-1},k-m\le i\le k-1$$

SR1法では更新の際に行列が正定値となるとは限らない。L-SR1法では信頼領域法と組み合わせて用いることが望ましい。記憶制限による行列を使用することで、信頼領域・L-SR1法は問題のサイズに対して線形のオーダーで計算することができ、L-BFGS法と同様に扱うことができる。

関連項目

• 準ニュートン法
• ブロイデン法
• 最適化におけるニュートン法
• BFGS法
• L-BFGS法