SR1法 （SR1ほう、別称：対称ランクワン法 、たいしょうランクワンほう、英 : Symmetric Rank 1 ）とは、2点の導関数（勾配）の情報に基づいてヘッセ行列を更新する準ニュートン法 の一種である。SR1法は多次元の問題に対するセカント法 を一般化させたものである。更新される行列は対称行列 であることは保証されるが、正定値性 については保証されない。
SR1法で近似したヘッセ行列の列は緩い条件下の下で収束することが知られている。実用上でSR1法は他の解法（BFGS法 やDFP法 ）よりも早く真のヘッセ行列に収束することが数値実験により知られている[ 1] [ 2] [ 3]
2階微分可能な連続関数を
x
↦
f
(
x
)
{\displaystyle x\mapsto f(x)}
勾配 を
∇
f
{\displaystyle \nabla f}
ヘッセ行列 を
B
{\displaystyle B}
f
{\displaystyle f}
x
0
{\displaystyle x_{0}}
テイラー展開 は以下のように近似される:
f
(
x
0
+
Δ
x
)
≈
f
(
x
0
)
+
∇
f
(
x
0
)
T
Δ
x
+
1
2
Δ
x
T
B
Δ
x
{\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
{\displaystyle \nabla f}
∇
f
(
x
0
+
Δ
x
)
≈
∇
f
(
x
0
)
+
B
Δ
x
{\displaystyle \nabla f(x_{0}+\Delta x)\approx \nabla f(x_{0})+B\Delta x}
これら二つの近似式から
B
{\displaystyle B}
B
{\displaystyle B}
ランク 1更新式と呼ばれると呼ばれる式を用いて、十分に近似された対称行列
B
k
{\displaystyle B_{k}}
[要説明 :
B
k
+
1
=
B
k
+
(
y
k
−
B
k
Δ
x
k
)
(
y
k
−
B
k
Δ
x
k
)
T
(
y
k
−
B
k
Δ
x
k
)
T
Δ
x
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}}}}
ただし、
y
k
=
∇
f
(
x
k
+
Δ
x
k
)
−
∇
f
(
x
k
)
{\displaystyle y_{k}=\nabla f(x_{k}+\Delta x_{k})-\nabla f(x_{k})}
である。近似した行列の逆行列に対応したヘッセ行列
H
k
=
B
k
−
1
{\displaystyle H_{k}=B_{k}^{-1}}
H
k
+
1
=
H
k
+
(
Δ
x
k
−
H
k
y
k
)
(
Δ
x
k
−
H
k
y
k
)
T
(
Δ
x
k
−
H
k
y
k
)
T
y
k
{\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}}}}
B
k
{\displaystyle B_{k}}
B
k
+
1
=
B
k
+
v
v
T
{\displaystyle B_{k+1}=B_{k}+vv^{T}}
B
k
{\displaystyle B_{k}}
B
k
+
1
{\displaystyle B_{k+1}}
B
k
+
1
=
B
k
−
v
v
T
{\displaystyle B_{k+1}=B_{k}-vv^{T}}
B
k
+
1
{\displaystyle B_{k+1}}
これまでSR1法の更新式は幾度と再発見されてきた。SR1法において更新式の分母の項がゼロとなることを回避するために、以下の条件を満たす場合にのみ近似ヘッセ行列の更新を行う手法も提案されている:
|
Δ
x
k
T
(
y
k
−
B
k
Δ
x
k
)
|
≥
r
‖
Δ
x
k
‖
⋅
‖
y
k
−
B
k
Δ
x
k
‖
{\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}\|}
このとき、
r
∈
(
0
,
1
)
{\displaystyle r\in (0,1)}
10
−
8
{\displaystyle 10^{-8}}
[ 4]
SR1更新は密な行列を使用することから、大規模問題においては計算量が高くなることがある。計算効率を高めるためにL-BFGS法 と同様に記憶制限SR1法が存在する[ 5]
m
{\displaystyle m}
{
(
s
i
,
y
i
)
}
i
=
k
−
m
k
−
1
{\displaystyle \{(s_{i},y_{i})\}_{i=k-m}^{k-1}}
Δ
x
i
:=
s
i
{\displaystyle \Delta x_{i}:=s_{i}}
m
{\displaystyle m}
n
{\displaystyle n}
m
≪
n
{\displaystyle 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
{\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
k
=
[
s
k
−
m
s
k
−
m
+
1
…
s
k
−
1
]
,
{\displaystyle S_{k}={\begin{bmatrix}s_{k-m}&s_{k-m+1}&\ldots &s_{k-1}\end{bmatrix}},}
Y
k
=
[
y
k
−
m
y
k
−
m
+
1
…
y
k
−
1
]
,
{\displaystyle Y_{k}={\begin{bmatrix}y_{k-m}&y_{k-m+1}&\ldots &y_{k-1}\end{bmatrix}},}
(
L
k
)
i
j
=
s
i
−
1
T
y
j
−
1
,
D
k
=
s
i
−
1
T
y
i
−
1
,
k
−
m
≤
i
≤
k
−
1
{\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法と同様に扱うことができる。
^ 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 . ^ 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 . ^ 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 . ^ Nocedal, Jorge; Wright, Stephen J. (1999). Numerical Optimization . Springer. ISBN 0-387-98793-2 ^ 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 .
