SR1法のソースを表示

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

SR1法で近似したヘッセ行列の列は緩い条件下の下で収束することが知られている。実用上でSR1法は他の解法（[[BFGS法]]や[[DFP法]]）よりも早く真のヘッセ行列に収束することが数値実験により知られている。<ref name="CGT">{{cite journal|last1=Conn|first1=A. R.|last2=Gould|first2=N. I. M.|last3=Toint|first3=Ph. L.|title=Convergence of quasi-Newton matrices generated by the symmetric rank one update|journal=Mathematical Programming|date=March 1991|publisher=Springer Berlin/ Heidelberg |issn=0025-5610|pages=177–195|volume=50|number=1|doi=10.1007/BF01594934|s2cid=28028770 }}</ref><ref>{{cite journal |last1=Khalfan |first1=H. Fayez |first2=R. H. |last2=Byrd |first3=R. B. |last3=Schnabel |display-authors=1 |year=1993 |title=A Theoretical and Experimental Study of the Symmetric Rank-One Update |journal=SIAM Journal on Optimization |volume=3 |issue=1 |pages=1–24 |doi=10.1137/0803001 }}</ref>。SR1法は疎な行列や部分分割できる問題に対して計算上の利点を有する<ref>{{cite journal |last1=Byrd |first1=Richard H. |first2=Humaid Fayez |last2=Khalfan |first3=Robert B. |last3=Schnabel |display-authors=1 |year=1996 |title=Analysis of a Symmetric Rank-One Trust Region Method |journal=SIAM Journal on Optimization |volume=6 |issue=4 |pages=1025–1039 |doi=10.1137/S1052623493252985 }}</ref>。

2階微分可能な連続関数を <math>x \mapsto f(x)</math> とし、[[勾配]]を <math>\nabla f</math>、[[ヘッセ行列]]を <math>B</math> とする。関数 <math>f</math> の点 <math>x_0</math> における[[テイラー展開]]は以下のように近似される:
::<math>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 </math>;
また、勾配 <math>\nabla f</math> に対するテイラー展開は以下のように近似される:
::<math>\nabla f(x_0+\Delta x) \approx \nabla f(x_0)+B \Delta x</math>,
これら二つの近似式から <math>B</math> を更新していく。ただし上記のセカント法による方程式は一意の解 <math>B</math> をもつとは限らない。SR1法では以下の[[行列の階数|ランク]]1更新式と呼ばれると呼ばれる式を用いて、十分に近似された対称行列 <math>B_k</math> を計算する{{要説明|date=2022-07}}:
::<math>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}</math>
ただし、
::<math>y_k=\nabla f(x_k+\Delta x_k)-\nabla f(x_k)</math>
である。近似した行列の逆行列に対応したヘッセ行列 <math>H_k=B_k^{-1}</math> の更新は以下のようになる:
::<math>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}</math>.

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

これまでSR1法の更新式は幾度と再発見されてきた。SR1法において更新式の分母の項がゼロとなることを回避するために、以下の条件を満たす場合にのみ近似ヘッセ行列の更新を行う手法も提案されている:
::<math>|\Delta x_k^T (y_k-B_k \Delta x_k)|\geq r \|\Delta x_k\|\cdot \|y_k-B_k \Delta x_k\| </math>,
このとき、<math>r\in(0,1)</math> は <math>10^{-8}</math> のような十分に小さい数とする<ref>{{cite book |last1=Nocedal |first1=Jorge |last2=Wright |first2=Stephen J. |year=1999 |title=Numerical Optimization |publisher=Springer |isbn=0-387-98793-2 }}</ref>。

== 記憶制限 ==
SR1更新は密な行列を使用することから、大規模問題においては計算量が高くなることがある。計算効率を高めるために[[L-BFGS法]]と同様に記憶制限SR1法が存在する<ref name="bem17">{{cite journal |last1=Brust |first1=J. |last2=Erway |first2=J.B. |last3=Marcia |first3=R.F. |display-authors=1 |year=2017 |title=On solving L-SR1 trust-region subproblems |journal=Computational Optimization and Applications |volume=66|pages=245–266 |doi=10.1007/s10589-016-9868-3 |arxiv=1506.07222 }}</ref>。L-SR1法では近似したヘッセ行列のすべての情報を持たずに、<math>m</math> 個の組 <math> \{(s_i, y_i) \}_{i=k-m}^{k-1} </math> のみを利用して近似の行列を更新する。ただし、<math>\Delta x_i := s_i </math> とし、<math>m</math> は問題のサイズ <math>n</math> より十分に小さい整数（<math>m \ll n </math>）とする。記憶制限による行列は以下のように表される:

<math display="block>
B_k = B_0 + J_k N^{-1}_k J^T_k, \quad J_k = Y_k-B_0 S_k, \quad  N_k =
D_k+L_k+L^T_k-S^T_k B_0 S_k 
</math>

<math display="block"> S_k = \begin{bmatrix} s_{k-m} & s_{k-m+1} & \ldots & s_{k-1} \end{bmatrix}, </math>
<math display="block"> Y_k = \begin{bmatrix} y_{k-m} & y_{k-m+1} & \ldots & y_{k-1} \end{bmatrix}, </math>

<math display="block" > \big(L_k\big)_{ij} = s^T_{i-1}y_{j-1}, \quad D_k = s^T_{i-1}y_{i-1}, \quad k-m \le i \le k-1 </math>

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

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 関連項目 ==
* [[準ニュートン法]]
* [[ブロイデン法]]
* [[最適化におけるニュートン法]]
* [[BFGS法]]
* [[L-BFGS法]]

{{最適化アルゴリズム}}

[[Category:最適化アルゴリズムとメソッド]]
[[Category:数学に関する記事]]