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