SR1法

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

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

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

${\displaystyle f(x_{0}+\Delta x)\approx f(x_{0})+\nabla f(x_{0})^{T}\Delta x+{\frac {1}{2}}\Delta x^{T}{B}\Delta x}$;

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

${\displaystyle \nabla f(x_{0}+\Delta x)\approx \nabla f(x_{0})+B\Delta x}$,

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

${\displaystyle B_{k+1}=B_{k}+{\frac {(y_{k}-B_{k}\Delta x_{k})(y_{k}-B_{k}\Delta x_{k})^{T}}{(y_{k}-B_{k}\Delta x_{k})^{T}\Delta x_{k}}}}$

ただし、

${\displaystyle y_{k}=\nabla f(x_{k}+\Delta x_{k})-\nabla f(x_{k})}$

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

${\displaystyle H_{k+1}=H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})(\Delta x_{k}-H_{k}y_{k})^{T}}{(\Delta x_{k}-H_{k}y_{k})^{T}y_{k}}}}$.

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

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

${\displaystyle |\Delta x_{k}^{T}(y_{k}-B_{k}\Delta x_{k})|\geq r\|\Delta x_{k}\|\cdot \|y_{k}-B_{k}\Delta x_{k}\|}$,

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

記憶制限

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

$${\displaystyle B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T},\quad J_{k}=Y_{k}-B_{0}S_{k},\quad N_{k}=D_{k}+L_{k}+L_{k}^{T}-S_{k}^{T}B_{0}S_{k}}$$

$${\displaystyle S_{k}={\begin{bmatrix}s_{k-m}&s_{k-m+1}&\ldots &s_{k-1}\end{bmatrix}},}$$ $${\displaystyle Y_{k}={\begin{bmatrix}y_{k-m}&y_{k-m+1}&\ldots &y_{k-1}\end{bmatrix}},}$$

$${\displaystyle {\big (}L_{k}{\big )}_{ij}=s_{i-1}^{T}y_{j-1},\quad D_{k}=s_{i-1}^{T}y_{i-1},\quad k-m\leq i\leq k-1}$$

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

脚注

1. Conn, A. R.; Gould, N. I. M.; Toint, Ph. L. (March 1991). “Convergence of quasi-Newton matrices generated by the symmetric rank one update”. Mathematical Programming (Springer Berlin/ Heidelberg) 50 (1): 177–195. doi:10.1007/BF01594934. ISSN 0025-5610. 
2. Khalfan, H. Fayez et al. (1993). “A Theoretical and Experimental Study of the Symmetric Rank-One Update”. SIAM Journal on Optimization 3 (1): 1–24. doi:10.1137/0803001. 
3. Byrd, Richard H. et al. (1996). “Analysis of a Symmetric Rank-One Trust Region Method”. SIAM Journal on Optimization 6 (4): 1025–1039. doi:10.1137/S1052623493252985. 
4. Nocedal, Jorge; Wright, Stephen J. (1999). Numerical Optimization. Springer. ISBN 0-387-98793-2 
5. Brust, J. et al. (2017). “On solving L-SR1 trust-region subproblems”. Computational Optimization and Applications 66: 245–266. arXiv:1506.07222. doi:10.1007/s10589-016-9868-3. 

関連項目

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