対称ランク1

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

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(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}}}}$。

正定値が保持されないのはなぜかと疑問に思うかもしれない。結局のところ、次の形式のランク 1 更新では${\displaystyle B_{k+1}=B_{k}+vv^{T}}$正定値であるのは、${\displaystyle B_{k}}$そうです。説明としては、アップデートは次の形式になる可能性があるということです。${\displaystyle B_{k+1}=B_{k}-vv^{T}}$なぜなら、分母が負になる可能性があり、その場合は正定値性について保証がないからです。

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)}$は小さな数です。$10⁻⁸$[ ^{4 ]​}

SR1 更新では密行列が維持されるため、大規模な問題では処理が困難になる場合があります。L -BFGS法と同様に、メモリ制限付き SR1 (L-SR1) アルゴリズムも存在します。^{[ 5 ]} L-SR1 法では、完全なヘッセ行列近似を保存する代わりに、${\displaystyle m}$最新のペア${\displaystyle \{(s_{i},y_{i})\}_{i=km}^{k-1}}$、 どこ$\displaystyle \Delta x_{i}:=s_{i}}$そして${\displaystyle m}$は問題のサイズよりもはるかに小さい整数です（${\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_{km}&s_{k-m+1}&\ldots &s_{k-1}\end{bmatrix}},}$$$${\displaystyle Y_{k}={\begin{bmatrix}y_{km}&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})_{ii}=s_{i-1}^{T}y_{i-1},\quad km\leq i\leq k-1}$$

更新回数が無制限であるため、L-SR1アルゴリズムは信頼領域戦略に適しています。メモリ行列が限られているため、信頼領域L-SR1アルゴリズムは、L-BFGSと同様に、問題サイズに対して線形にスケーリングします。

• 準ニュートン法
• ブロイデンの方法
• 最適化におけるニュートン法
• ブロイデン・フレッチャー・ゴールドファーブ・シャノ（BFGS）法
• L-BFGS法
• コンパクトな準ニュートン表現