最急降下法 - pecorarista.com

最急降下法
宮澤　彬
総合研究大学院大学博士前期
[email protected]
July 13, 2015
(modiﬁed: December 2, 2015)
1/11
最急降下法
関数の停留点（特に極小点）を，反復的な計算で求めるにはどうすれば
よいか．接線の傾きが負である点から，0 に近づく方向に移動していけ
ばよさそうである．
y
y = f (x)
∇f (x∞ ) = 0
O
x0
xk
x∞
x
2/11
Armijo 条件
0 < ξ1 < 1 であるような定数 ξ1 に対して，
f (xk + αdk ) ≤ f (xk ) + ξ1 α∇f (xk ) · dk
を満たす α > 0 を選ぶ．この条件を Armijo 条件 1 という．
y
y = f (x)
O
xk
y = f (xk ) + ξ1 α∇f (xk ) · dk
x
xk + αdk
y = f (xk ) + α∇f (xk ) · dk
1 スペイン語読みをするならばおそらく/arˈmixo/．
3/11
Wolfe 条件
0 < ξ1 < ξ2 < 1 であるような ξ1 , ξ2 に対して
ξ2 ∇f (xk ) · dk ≤ ∇f (xk + αdk ) · dk
を満たす α > 0 を選ぶ．この条件を曲率条件 (curvature condition)
と呼ぶ．この条件と Armijo 条件を合わせて Wolfe 条件と呼ぶ．
y
y = f (x)
ξ2 ∇f (xk )
∇f (xk )
O
xk
xk + αdk
x
4/11
Zoutendijk 条件
定理目的関数 f (x) は下に有界で，かつ，初期点 x0 における準位集合
{x ; f (x) ≤ f (x0 )} におけるを含む開集合 U において連続的微分可能
であるとする．また勾配 ∇f (x) は U で Lipschitz 連続であるとする．
すなわち，ある正定数 L が存在して，任意の x, y ∈ U に対して
k∇f (x) − ∇f (y)k ≤ L kx − yk
が成り立つとする．
このとき xk+1 = xk + αk dk を以下の条件を満たすようにとる．
I
各 αk が Wolfe 条件を満たす．
I
各 dk が降下方向である．すなわち ∇f (xk ) · dk < 0 を満たす．
すると点列 (xk )k について
2
∞ X
∇f (xk ) · dk
k=0
kdk k
<∞
が成り立つ．
5/11
Zoutendijk 条件
証明曲率条件と xk+1 = xk + αk dk から
ξ2 ∇f (xk ) · dk ≤ ∇f (xk+1 ) · dk
(ξ2 − 1) ∇f (xk ) · dk ≤ (∇f (xk+1 ) − ∇f (xk )) · dk
が成り立つ．Lipschitz 条件より
(∇f (xk+1 ) − ∇f (xk )) · dk ≤ k∇f (xk+1 ) − ∇f (xk )k kdk k
≤ L kxk+1 − xk k kdk k
≤ αk L kdk k
2
が成り立つ．これらから
αk ≥
(∇f (xk+1 ) − ∇f (xk )) · dk
2
L kdk k
ξ2 − 1 ∇f (xk ) · dk
≥
2
L
kdk k
を得る．
6/11
Zoutendijk 条件
得られた αk を Armijo 条件に代入して
f (xk+1 ) ≤ f (xk ) + ξ1 αk ∇f (xk ) · dk
≤ f (xk ) −
ξ1 (1 − ξ2 ) (∇f (xk ) · dk )
2
L
kdk k
2
となる．ここで k = 0 から m までの和をとると
m
X
k=0
(f (xk+1 ) − f (xk )) ≤ −
m
2
X
ξ1 (1 − ξ2 ) (∇f (xk ) · dk )
k=0
L
m
2
kdk k
2
ξ1 (1 − ξ2 ) X (∇f (xk ) · dk )
f (xm+1 ) − f (x0 ) ≤ −
2
L
kdk k
k=0
を得る．
7/11
Zoutendijk 条件
上式の右辺は m が増加するにつれて単調に減少する．また f は下に有
界であると仮定していたので
∞
2
X
(∇f (xk ) · dk )
2
k=0
kdk k
<∞
(Zoutendijk)
を得る．
上の (Zoutendijk) を Zoutendijk 条件 2 と呼ぶ．
2 オランダ語読みをするならばおそらく/ˈzɑutəndɛ̞ɪk/．
8/11
Zoutendijk 条件
Zoutendijk
P∞ 条件が成り立つとする．このとき
2
2
S := k=0 (∇f (xk ) · dk ) / kdk k はある有限の値である．
Cauchy-Schwarz の不等式から，任意の自然数 m について
m
X
|∇f (xk ) · dk |
k=0
kdk k
!2
≤
m
2
X
(∇f (xk ) · dk )
kdk k
k=0
2
≤S
が成り立つ．ゆえに
∞
X
|∇f (xk ) · dk |
k=0
kdk k
≤
√
S
となり，この級数は収束することが分かる．したがって
|∇f (xk ) · dk |
→ 0 (k → ∞)
kdk k
となる．
9/11
最急降下法の大域収束性
2
特に dk = −∇f (xk ) をとる．この dk は ∇f (xk ) · dk = − kf (xk )k < 0
を満たすので，降下方向である．さらに先に示した結果から，
|∇f (xk ) · dk |
= k∇f (xk )k → 0 (k → ∞)
kdk k
を満たす．
Cauchy-Schwarz の不等式における等号成立条件から，kdk k を固定し
て考えたとき，この dk は ∇f (xk ) · dk を最小にするものである．つま
り最も急に減少させるものである．そのため dk = −∇f (xk ) とする方
法を最急降下法 (steepest descent method) と呼ぶ．
10/11
参考文献・おわりに
主に以下を参考にした．
I
矢部博, 新・工科系の数学「工学基礎　最適化とその応用」, 数理工
学社, 2006.
また，このスライドのソースコードは
https://github.com/pecorarista/documents にある．
11/11

Download Report