対称ランク1

対称ランク1法（SR1法）は、2点で計算された導関数（勾配）に基づいて2階微分（ヘッセ行列）を更新する準ニュートン法です。これは、多次元問題に対する正割法の一般化です。この更新は行列の対称性を維持しますが、更新結果が正定値であることを保証するものではありません。

SR1法によって生成されたヘッセ行列近似値の列は、理論的には、穏やかな条件下では真のヘッセ行列に収束します。実際には、予備的な数値実験では、SR1法によって生成された近似ヘッセ行列は、一般的な代替法（BFGSまたはDFP）よりも真のヘッセ行列への収束速度が速いことが示されています。[1] [2] SR1法は、疎な問題や部分的に分離可能な問題に対して計算上の利点があります。[3]

2回連続微分可能な関数は勾配（）とヘッセ行列を持つ。この関数はでテイラー級数として展開され、切り捨てられる。 × ↦ f （ × ） {\displaystyle x\mapsto f(x)} ∇ f {\displaystyle \nabla f} B {\displaystyle B} f {\displaystyle f} × 0 {\displaystyle x_{0}}

f （ × 0 + Δ × ） ≈ f （ × 0 ） + ∇ f （ × 0 ） T Δ × + 1 2 Δ × T B Δ × {\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} ;

その勾配はテイラー級数近似も持つ

∇ f （ × 0 + Δ × ） ≈ ∇ f （ × 0 ） + B Δ × {\displaystyle \nabla f(x_{0}+\Delta x)\approx \nabla f(x_{0})+B\Delta x} 、

これは を更新するために使用されます。上記の割線方程式は、一意の解 を持つ必要はありません 。SR1式は（階数1の更新を介して）現在の近似値 に 最も近い（詳細な説明が必要）対称解を計算します。 B {\displaystyle B} B {\displaystyle B} B け {\displaystyle B_{k}}

B け + 1 ＝ B け + （ y け − B け Δ × け ） （ y け − B け Δ × け ） T （ y け − B け Δ × け ） T Δ × け {\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}}}} 、

どこ

y け ＝ ∇ f （ × け + Δ × け ） − ∇ f （ × け ） {\displaystyle y_{k}=\nabla f(x_{k}+\Delta x_{k})-\nabla f(x_{k})} 。

対応する近似逆ヘッセ行列の更新は H け ＝ B け − 1 {\displaystyle H_{k}=B_{k}^{-1}}

H け + 1 ＝ H け + （ Δ × け − H け y け ） （ Δ × け − H け y け ） T （ Δ × け − H け y け ） T y け {\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}}}} 。

なぜ正定値が保存されないのかと疑問に思う人もいるかもしれない。結局のところ、 のランク1更新はであれば正定値である。その説明は、分母が負になる可能性があり、その場合正定値が保証されないため、更新は の形式になる可能性がある、というものである。 B け + 1 ＝ B け + v v T {\displaystyle B_{k+1}=B_{k}+vv^{T}} B け {\displaystyle B_{k}} B け + 1 ＝ B け − v v T {\displaystyle B_{k+1}=B_{k}-vv^{T}}

SR1の公式は何度も再発見されている。分母が消える可能性があるため、一部の著者は、以下の場合にのみ更新を適用することを提案している。

| Δ × け T （ y け − B け Δ × け ） | ≥ r ‖ Δ × け ‖ ⋅ ‖ y け − B け Δ × け ‖ {\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}\|} 、

ここでは小さな数、例えば である。[4] r ∈ （ 0 、 1 ） {\displaystyle r\in (0,1)} 10 − 8 {\displaystyle 10^{-8}}

限られたメモリ

SR1更新は密行列を維持するため、大規模な問題では適用が困難となる可能性がある。L -BFGS法と同様に、メモリ制限SR1（L-SR1）アルゴリズムも存在する。[5] L-SR1法は、完全なヘッセ近似値を保存する代わりに、最新のペアのみを保存する。ここで、およびは問題サイズ（）よりもはるかに小さい整数である。メモリ制限行列は、コンパクトな行列表現に基づいている。 メートル {\displaystyle m} { （ s 私 、 y 私 ） } 私 ＝ け − メートル け − 1 {\displaystyle \{(s_{i},y_{i})\}_{i=km}^{k-1}} Δ × 私 := s 私 {\displaystyle \Delta x_{i}:=s_{i}} メートル {\displaystyle m} メートル ≪ n {\displaystyle m\ll n}

B け ＝ B 0 + J け 北 け − 1 J け T 、 J け ＝ はい け − B 0 S け 、 北 け ＝ D け + L け + L け T − S け T B 0 S け {\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}}

S け ＝ [ s け − メートル s け − メートル + 1 … s け − 1 ] 、 {\displaystyle S_{k}={\begin{bmatrix}s_{km}&s_{k-m+1}&\ldots &s_{k-1}\end{bmatrix}},} はい け ＝ [ y け − メートル y け − メートル + 1 … y け − 1 ] 、 {\displaystyle Y_{k}={\begin{bmatrix}y_{km}&y_{k-m+1}&\ldots &y_{k-1}\end{bmatrix}},}

（ L け ） 私 j ＝ s 私 − 1 T y j − 1 、 （ D け ） 私 私 ＝ s 私 − 1 T y 私 − 1 、 け − メートル ≤ 私 ≤ け − 1 {\displaystyle {\big (}L_{k}{\big )}_{ij}=s_{i-1}^{T}y_{j-1},\quad (D_{k})_{ii}=s_{i-1}^{T}y_{i-1},\quad km\leq i\leq k-1}

L-SR1アルゴリズムは更新が不定となる可能性があるため、信頼領域戦略に適しています。メモリが限られた行列のため、信頼領域L-SR1アルゴリズムはL-BFGSと同様に問題のサイズに比例してスケールします。

参照

参考文献

  1. ^ Conn, AR; Gould, NIM; Toint, Ph. L. (1991年3月). 「対称ランク1更新によって生成された準ニュートン行列の収束」.数理計画. 50 (1). Springer Berlin/ Heidelberg: 177– 195. doi :10.1007/BF01594934. ISSN  0025-5610. S2CID  28028770.
  2. ^ Khalfan, H. Fayez; et al. (1993). 「対称ランク1更新の理論的および実験的研究」. SIAM Journal on Optimization . 3 (1): 1– 24. doi :10.1137/0803001.
  3. ^ Byrd, Richard H.; et al. (1996). 「対称ランク1信頼領域法の解析」. SIAM Journal on Optimization . 6 (4): 1025– 1039. doi :10.1137/S1052623493252985.
  4. ^ Nocedal, Jorge; Wright, Stephen J. (1999).数値最適化. Springer. ISBN 0-387-98793-2。
  5. ^ Brust, J.; et al. (2017). 「L-SR1信頼領域部分問題の解決について」.計算最適化とその応用. 66 : 245–266 . arXiv : 1506.07222 . doi :10.1007/s10589-016-9868-3.
「https://en.wikipedia.org/w/index.php?title=Symmetric_rank-one&oldid=1287339866」より取得