第6回の授業資料

計画数理
第６回：制約なし最適化アルゴリズム
林俊介
無制約（制約なし）最適化問題
この問題を解くためには，計算機上でアルゴリズム
を実装するのが一般的．
無制約最適化問題を解くアルゴリズム（の多く）は
直線探索法（というクラス）の一種である．
直線探索法
（注意）テキストではステップサイズの
記号として t を使っているが，スライド
ではαを用いる．
以下のように探索方法とステップサイズ（ステップ幅）を使って，
最適解へ収束するような点列を生成する手法の総称．
初期点
…
…
直線探索法
（注意）テキストではステップサイズの
記号として t を使っているが，スライド
ではαを用いる．
以下のように探索方法とステップサイズ（ステップ幅）を使って，
最適解へ収束するような点列を生成する手法の総称．
初期点
• 多くの最適化アルゴリズムが直線探索法．
• 通常，以下を満たすように点列を生成．
• 一般的に，生成点列の極限
に対しては，局所最適性
…
… しか保証できない．
直線探索法
（注意）テキストではステップサイズの
記号として t を使っているが，スライド
ではαを用いる．
以下のように探索方法とステップサイズ（ステップ幅）を使って，
最適解へ収束するような点列を生成する手法の総称．
初期点
更新式は，まとめて以下のように書く．
降下方向
では，探索方向
はどんな条件を満たせば良いか？
が以下の条件を満たすことが望ましい．
このような探索方向を，降下方向という．
ステップサイズとして十分小さな
を選べば，必ず
となる !!
ステップサイズ
の決め方
では，ステップサイズ
はどのように決めればよいか？
アルゴリズムがとても遅くなる．
アルゴリズムが正しく動かない．
ステップサイズは適切に決定しなければならない！
※ ３つのステップサイズルールがよく知られている．
ステップサイズルール
1. 正確な直線探索 (Exact line search)
利点：自然で分かりやすい
欠点：最適化問題を解かなければならず，効率が悪い．
ステップサイズルール
2. アルミホ(Armijo)のルール
アルミホの不等式を満たす
非負実数 ℓ は必ず存在！
とする．
利点：計算機への実装が容易．欠点：ちょっと分かりにくい．
ステップサイズルール
3. ウルフ(Wolfe)のルール
１つめの不等式はアルミホのルールと等価．
２つめの不等式はステップサイズが0に近づきすぎないことを要請．
（詳細略）
計算手順
以下に直線探索法の一般的な計算手順を記述する．
※ パラメータ ε は十分小さな正数（
など）を選ぶのが一般的．
※ 場合によっては，(3)で「正確な直線探索」を用いてもよい．
次に，探索方向
の決め方を紹介する．
11
最急降下法 (steepest descent method)
最急降下法では，探索方向を以下の式で決定する．
言うまでもなく，
は降下方向である．なぜなら，
最急降下法の利点と欠点
利点：最急降下法は大域的収束性をもつ．
どんな初期点
を選んだとしても，
生成点列の極限
は局所最適解になる．
(厳密には，いくつかの仮定が必要だが，ここでは割愛．）
欠点：最適解への収束が極端に遅くなることがある．
目的関数の等高線が丸い場合（収束が早い）
目的関数の等高線が潰れてる場合（収束が遅い）
13
テキスト43ページの例
14
一次収束性
実際，最急降下法で生成される点列は以下のような性質をもつ．
このような性質を一次収束性という．
(等高線が丸っこい場合)
(等高線が潰れた場合)
15
ニュートン法
ニュートン法では，探索方向を以下の式で決定する．
(Taylor展開)
16
Notice: 最適化におけるニュートン法は，方程式に対するニュートン法とは別．
ニュートン法の利点
利点: ニュートン法は収束がとても速い．
を最適解の十分近くに取ることができれば，以下が成立．
このような性質二次収束性という．
17
ニュートン法の利点
利点: ニュートン法は収束がとても速い．
を最適解の十分近くに取ることができれば，以下が成立．
このような性質二次収束性という．
テキスト44ページの例
18
収束の速さ（収束率）
一次収束 (Linear convergence)
二次収束 (Quadratic convergence)
超一次収束 (Superlinear convergence)
最急降下法
ニュートン法
準ニュートン法
実際の収束の速さ
19
ニュートン法の欠点
欠点：ニュートン法は大域的収束性をもたない．
の選択によっては，ニュートン法は収束しない．
何故か？
が降下方向にならないことがあるから．
20
降下方向（以前のスライド）
では，探索方向
はどんな条件を満たせば良いか？
が以下の条件を満たすことが望ましい．
このような探索方向を，降下方向という．
ステップサイズとして十分小さな
を選べば，必ず
となる !!
ニュートン法の欠点
１次元の例
22
最急降下法とニュートン法の利点と欠点
最急降下法
利点：大域的収束性をもつ．
欠点：収束率が遅い．（一次収束）
ニュートン法
利点：最適解の周りで収束が速い．（二次収束）
欠点：大域的最適性をもたない．
※ 目的関数が凸なら，（多くの場合）ニュートン法も大域的収束性をもつ．
23
準ニュートン法
準ニュートン法では，探索方向を以下で決定する．
（憶える必要なし）
: 最急降下方向
: ニュートン方向
24
準ニュートン法の収束性
準ニュートン法は最急降下法と
ニュートン法の利点を併せ持つ！
収束率は超一次収束
実際の収束の速さ
準ニュートン法の利点と欠点
利点 1:
大域的収束性をもつ．
利点 2:
最適解の周りで速い収束性（超一次収束）をもつ．
利点 3:
ヘッセ行列を計算しなくてもよい．
欠点:
収束率がニュートン法にくらべて少し遅い．
テキストの修正（宿題について）
３限に横井先生から指示があるので，それに従うこと．
27

Download Report