最急降下法 宮澤 彬 総合研究大学院大学 博士前期 [email protected] July 13, 2015 (modified: 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
© Copyright 2024 ExpyDoc