Microsoft PowerPoint - 数理計画08_s_distri.ppt [互換モード]

Transcription

1 数理計画 鈴木聡 ~7 回目 石川潤 8~ 回目 講義内容 シラバスと同じなので書写さなくても OK. 導入. 曲線と曲面の方程式 p~6. 次形式の標準形と最小値 最大値最大値 p6~. 関数の勾配 p~59. プレ中間試験 5. 関数の極値 p59~77 6. 勾配法による関数の最適化 p78~85 7. ニュートン法による関数の最適化 p85~97 8. 中間試験 9. 最小二乗法. 確率 統計の復習. 最尤推定. 線形計画法の考え方. 非線形計画法の考え方. 動的計画法 最適経路問題の考え方 ~ 最終試験? レポート? ~ 8, Satosh Suzuk 数理計画とは? 書写し不要 人生の目標 書写し不要 一般的な日常問題を数式で表現し 数学的手法で最適な もっともらしい 答えを探す作業 最適化問題 ともいう では 最適optmzato とはなんでしょう? - 国語辞典 : 名 形動 最も適している こと さま - 英英辞典 : to make as perect, eectve, or uctoal as possble 8, Satosh Suzuk 汎用化柔軟性 大域性局所性 計算時間探査可否 生物は進化の過程である種の最適化問題を解いている ダーウィン的進化 人生目標 - お金持ち? 長生き? 有名人? 本講義の目的 -" 数理計画 " を理解する - 評価方法は?... 点数をとる単位をとる ということで - 目標関数 : 中間テスト > 6 8, Satosh Suzuk Charles Robert Darw [Wkpeda より引用 ] 数理計画 第 回 ~ 曲線と曲面の方程式 ~ p~5 5 鈴木聡 最適化とは 数学的意味で ある状況において最善の決定を行うこと いくつかの選択肢の中から最善のものを選ぶこと 究極の一番を見つけることではない optmzato の定式化 与えられた制約条件 costrat のもとで 目的関数 obectve ucto が最小 or 最大となるような 決定変数 decso varable を見つけること 目的関数 = 望ましさの尺度をあらわす関数 8, Satosh Suzuk 8, Satosh Suzuk

2 最適化問題 決定変数 : 通常複数個存在 ベクトルで表現 [,,, ] 目的関数 : 最小制約条件 : S 目的関数 : S を含む適当な集合上で定義された実数値関数 実行可能領域 S - 変数 がとることを許された値の集合 - S は通常 に関する 不 等式や組合せ式 で表される 実行可能領域 可能領域の特徴を使って最適解を探索する 適切に S を設定しないと.. - 探索終了しない, - 計算機爆発 仕事 卒論 が終わらない!! o S 最大解は? 8, Satosh Suzuk 8, Satosh Suzuk 最適化問題を解くための心得 条件は何か? - 制約条件の洗出し - 実行可能領域 S の明確化 如何に数式で表現するか 本当に解ける問題か? - の最小値の存在性, 極小値の唯一性 - 局所最適 大域的最適 解くための労力は? - 適切な探索アルゴリズムか 解がキチンと見つけられる? - 計算時間 複雑度は? 数理計画 に必要なツール 知識 線形代数 ベクトル 行列 幾何 直線 曲線 超平面 微分 積分 勾配 偏微分 数と集合の概念 凸 閉 開集合 きちんと覚えていますか? 必要なときに適宜説明しますが 復習しておくことが好ましい 書写し不要 8, Satosh Suzuk 8, Satosh Suzuk 幾何学 線と直線 曲線の方程式 線 曲線 : 次元空間で境界を表す基本要素, 平面 曲面 : 次元空間で 境界を表す,, z 次元では?... 超平面 超曲面 正則 特異点を持たない,, - 探索領域に不連続点がないということ 一般表現 :, 以下 説明簡略の為 次元に限定 本講義では正則 なものに限る 正則 = 特異点 となる点 を持たない 領域.. 線 直線でも曲線でも で区切られた空間 - 片側が, なら 反対側は, - 閉曲線ならば内部と外部では符号が反対,, o, o, 8, Satosh Suzuk 8, Satosh Suzuk

3 曲線の方程式.. 例 次方程式, :,? 7 楕円方程式 , : 9,? 5 o,, -, o, 計算機ではこのように 数式で内側 外側を判定する 内側って何? 外側って? 外側, 内側 とは人間が作った抽象的概念 計算機は 規約なしに判別できない 外側, と決めたなら 内側, に対応させる コンピュータの気持ちになって考える 書写し不要 M.C.Escher s web-ste 代数解と数値解 代数解... 数値を代入すると解が求まる - 例 - 式構造から最適問題の答えが分かる場合がある 最小値発見 最小値を与える位置を発見 * 勾配と法線 勾配 - ある位置における, 関数の変化の程度を表す - 探索方向を決める手段のひとつ 数値解... 繰り返し計算 = 探索 で数値的に解を求める 8, Satosh Suzuk 勾配を使うと効率的になる * 法線 = 曲線における垂直方向の勾配 8, Satosh Suzuk 法線ベクトルの定義 曲線上の微小変位ベクトルを : としたとき 内積の極限 lm, を満たすベクトル を法線ベクトルという に直交するベクトルが :, o, 法線ベクトルの定義 テイラー展開の 次の係数,! 座標点 : における法線ベクトルであることを明示する場合には : と書く 定理 曲線,= の点, における法線ベクトルは である 8, Satosh Suzuk 8, Satosh Suzuk

4 例 の位置, : での法線は? 解 :, とおくと, なので : 7, 5 よって : 7, 8, Satosh Suzuk - 曲線の接線 直線, A a B b の法線ベクトルは 接線 = 法線ベクトルが 8, Satosh Suzuk A B A B で 点 a, b を通る直線 定理 点 における曲線,=の接線は 例題 例題 : 楕円 上の点 の接線は? 9 解 :, : 9 とおくと, なので よって接線は 9 6 8, Satosh Suzuk 曲面の方程式 一般表現 :,, z 本講義では基本的に正則なものに限る 片側が,, z なら 反対側は,, z 閉曲面ならば内部と外部では符号が反対 ,, z 5 8, Satosh Suzuk,, z 5,, z,, z 例 : 楕円体 楕円体,, z 9 z 6 に関して A 点,, は内部か外部か? 解 :,, より内部の点は負であり,, 8 であるので A 点は内部 曲面での法線ベクトル 定理 曲面,, z=の点,, z における法線ベクトルは z である,, z 8, Satosh Suzuk 8, Satosh Suzuk

5 例 : 楕円体上の法線ベクトル 楕円体,, z 9 z 6 に関して,, 9 における法線ベクトルは? 解,, z 9 z 8 なので 9 z 曲面の接平面 平面,, z A a B b C z c の 法線ベクトル z A B C 法線ベクトルが A B C で点 a, b, c を通る平面 定理 点 z における曲面,, z= の接平面は z z z 8, Satosh Suzuk 8, Satosh Suzuk 例 : 楕円体上の接平面 楕円体,, z 9 z 6 に関して,, 9 における接平面は? 解 : 前述の例題から 9 9 なので z 数理計画 第 回 ~ 次形式の標準形と最小値 最大値 ~ p6~ 鈴木聡 8, Satosh Suzuk 直線 曲面の一般化 直線や曲面は or 次元の幾何学要素... このままでは説明変数がつまでの問題しか解けない 数理計画では 次元へ拡張する必要アリ 数学的に 名称を 一般化 - 直線 >>[ 一般化 ] >> 次形式 - 放物線 >> [ 一般化 ] >> 次形式 次形式 a a a. a ベクトル表現 a : : とおくと a a a a a,... 内積で表現可 8, Satosh Suzuk 8, Satosh Suzuk

6 復習 ; 行列論 内積 - つのベクトルに対する演算操作 a, a - < ベクトル > < ベクトル > < スカラ > a R R a, R - 教科書に準じ 内積は a, 行列は a と書く - 間違えやすいので注意 行列は a の方が好ましいが... 行列 - 一般に非可換 : AB BA - 対称行列 : A A - 転置の分配 : AB B 8, Satosh Suzuk A 次形式の微分 次形式 : a a を各変数で偏微分すると a よって : と定義すると a と書ける さらに a,, とも書けるから 次の定理が成立 定理 次形式 a, の微分は a, a 微分すると, 内積 スカラ を ベクトルになる, 8, Satosh Suzuk 次形式 a a a a a a, a a a a : A, A... 内積で表現可.7 A は対称行列 :a a 次形式の係数行列 8, Satosh Suzuk 例題 次形式 問 : 次の 次形式をベクトルと対称行列とで表せ a b c 解. 変数の横ベクトル 係数行列 縦ベクトルの枠を準備. 次の係数を対角要素に並べる a c. 次の係数のを非対角要素に並べる a b b c 次形式の微分 a 次形式.7 をで微分 を含む項を取出すと a a a これを微分すると a a a a a 他の変数 = についても同様なので a,, が成立する注目! 次形式の微分 続き 改めて =~ まで並べると a ベクトルA の 行め要素 a ベクトルA の 行め要素 A 定理 次形式,A の微分は, A A 8, Satosh Suzuk 8, Satosh Suzuk

7 例 次形式の微分 次形式 5 6 の内積表現は 5, なので の微分は定理より, A A から 5 6 A 6 8 微分計算が極めて容易 計算機で数値解を求める数理計画にとって好都合 次形式の標準形 次形式の利点 - 最適化の評価関数としてよく利用 - 最適探索に必要な微分計算が簡単 - 最大 最小値の計算も容易 次形式標準形 標準形とは. 変数の座標変換で. 評価関数を簡単化 干渉項を消去 すること 例 : 6 ' 7 ' 8, Satosh Suzuk 8, Satosh Suzuk まずは例題 目的関数 : 最小 問 制約条件 : S - 目的関数 : 6 の最大 最小値は? - 制約条件 : 8, Satosh Suzuk 例題の解法 概略. 制約条件を満たしたまま 座標変換 {, } { ', '} なぜこの係数か? 後で説明 ' 5 5 ' 5 5 ' '. 目的関数を標準形へ 上の変換式を変形して代入 ' 5 ' 5 ' 5 ' 5 6 ' 7 '. 従属変数を消去. 変数範囲考慮して最大小値判明 ' 7' 5' ma 7, m 標準形と固有値 固有ベクトル 変数が多くなると式変形が煩雑 面倒 行列の性質を使うともっと簡単! 実は先の座標変換は 係数行列 A の固有ベクトル さらに の最大 最小値は Aの最大 最小固有値 次形式 I A 6 8, Satosh Suzuk 9 7 7, 固有ベクトル u 固有値 固有ベクトルの定義式代入して求める A u u に固有値 λ を : の固有ベクトル u に関し u,u を未知数として 6 u u u u, 行目とも u u 解の一つは u, u 5 だが 単位ベクトルにとり u 5 : 7の固有ベクトル u に関しても同様に 8, Satosh Suzuk u 5 5

8 固有ベクトル u を並べると 先の座標変換 U' となる 確認 5 U u u ' ' ' ' ' 5 ' 5 先の変換式と同じ 座標変換は 係数行列 A の固有ベクトル の最大 最小値は Aの最大 最小固有値 8, Satosh Suzuk 次形式と正定行列 次形式 quadratc orm: - 変数,, についての 次のべき関数 - 対称行列 A を用いて A と書ける 例 : 6 変数についての 次のべき関数 a A 一見行列のようだが スカラーであることに注意 正定 [ 正値 ] postve dete: A 半正定 [ 半正値 ] pos. sem-de.: A 負定 [ 負値 ] egatve dete: t A 8, Satosh Suzuk 正定行列 postve dete matr: - 次形式 A が正定のとき 行列 A を正定行列といい A と書く -つの対称行列について A B のときは A B と書く 正定行列の性質 a A である為の必要十分条件は A の固有値が全て正 l b 任意の行列 C R に対して C C c C C とC は等価 行列の対角化 行列の対角化 と 次形式の標準化 は等価 6 6 = 7 ' 7 ' 係数行列 A 対称行列 の対角化は直交行列で. 直交行列 - 正規直交に選んだ固有ベクトルを並べたもの U u u u R - U U I U U 重要! 8, Satosh Suzuk 8, Satosh Suzuk スペクトル分解 固有値分解 定義から Au なので u,, Au u Au, u,, u Au, Au,, Au U u, u,, u u, u,, u dag dag U dag 上式の両辺に左から U をかけると U AU U U dag dag スペクトル分解 : A U dag U 8, Satosh Suzuk 標準形と座標変換 座標変換 : 直交行列 U を用いる ' U U は直交なので逆行列 = 転置行列 U ' U U, A U ', AU' U ' 次形式, A は以下のように変形できる U' AU' ' U AU' ' U AU' ', U AU ' ', dag ' 8, Satosh Suzuk ' ' ' 二乗和形式 = 標準形 係数は A の固有値

9 正値 次形式 定理.- A が半正値対称行列, の時 A - 次形式, A を最大 最小 にする単位ベクトル は A の最大 最小 固有値に対する固有ベクトル - 次形式, A の最大 最小 値は行列 Aの最大 最小 固有値 数理計画 第 回 ~ 関数の勾配 ~ p~59 鈴木聡 8, Satosh Suzuk 勾配と最適化問題 探索 = 評価関数が減少 増加 する方向をさがす 勾配 = 関数の偏微分係数 テイラー展開 = 勾配を利用した関数近似法 a a a a a! a a a a!! ただし a : a d a : d a 8, Satosh Suzuk 復習 : テイラー展開 例題 : s の 近傍でのテイラー展開は? 解 : 微分係数を計算すると : s s なので 公式に代入して s s s! s! 5! 5!! 8, Satosh Suzuk 例題 続き.5.5 s とそのテイラー展開の,,5,7 次近似! ! 5!, s ! 5! 7! 高次になるほど 良い近似 方向を決めるだけ = 値の精度を気にしない なら 次項で十分 8, Satosh Suzuk 関数のテイラー展開 次変数関数, ある固定点, 近傍の座標, でのテイラー展開 ta,, ただし :, :,,, 8, Satosh Suzuk ta,, テイラー展開 ta, は, の近くでのみ,, ta

10 接平面 テイラー展開の 次以上の項を無視 次近似 した関数 I,. 接平面.5 勾配 グラディエント.5 式の接平面の勾配は, 関数, の勾配を 接平面の勾配を利用して : と定義 はAの近傍で関数値 が最も急激に増大する方向 A 点 接平面 :,,,, I 接平面の等高線 A 点 接平面上の最急上昇方向 曲面の等高線 曲面 :, R 8, Satosh Suzuk 8, Satosh Suzuk 次への拡張 次変数関数,, 次近似 = テイラー展開の 次以上の項を無視した関数 I,, 関数,, の勾配 : R は の近傍で関数値 が最も急激に増大する方向 ノルム はその方向の増加率 ノルム =ベクトルの大きさを表す尺度 a a a R のとき a a a R 8, Satosh Suzuk 最適化問題を解くには 小まとめ テイラー展開の 次項 勾配 で探索方向を決める 勾配の具体的な探索方法は後日 8, Satosh Suzuk 次関数の一般系 平行移動で 次の項と定数のみに変形できる 例 :, 6 6, 6 関数値が極値をとる位置を求めるには定数項は無関係 定数項を無視した式を 次形式の一般式として扱う, a b c a, b, c は慣例 微分するとすっきりするから 平行移動量の求め方 教科書 例題. 参照 8, Satosh Suzuk 係数 a,b,c の正負で形状が違う I. b= の場合 楕円型 放物型 双曲型 II. b= でない場合主軸変換を行うと, b=の場合と同じになる 8, Satosh Suzuk

11 次関数の極値 その : b の場合 a, b, c 例 :, 原点で最小値 a, b, c なら最大値 楕円型, 軸がその対称軸 主軸と呼ぶ 続き a b 例 :, 軸 軸 に沿って関数値が一定 放物型 軸 軸 がその対称軸 主軸と呼ぶ - - 主軸 8, Satosh Suzuk 主軸 8, Satosh Suzuk 続き ac, b 例 :, 軸 軸 方向に凹 軸 軸 方向に凸 双曲型, 鞍点 あんてん をもつ, 軸がその対称軸 主軸 評価関数構造の見極め なぜ一般化が必要か - 最適解の存在可否を事前に知る - 最大 最小値の存在が保証されているか? 8, Satosh Suzuk 主軸 楕円型 放物型 双曲型 最適値の存在性 最適値を与える条件 唯一 無数 8, Satosh Suzuk 次関数の極値 その : b の場合 先は b の 干渉項がゼロの場合 b では? 主軸変換をすると b の場合と同じ, a b c a, b, c a b,. b c : H... 次関数のヘッセ行列 ヘシアン 8, Satosh Suzuk 回転の座標変換 c s ' ' : R s : s, c : cos s c ' ' を一般形. に代入すると 最終的に次式になる ', R ' 回転行列 a b b ' R c ' O 復習 スヘ クトル 固有値 分解 A U dag U は直交行列なので ここは対角化できる R 角度 を選ぶと 8, Satosh Suzuk a b の形になるハズ b c では λの値は? R R

12 主軸変換, はヘッセ行列 H の固有値, を主軸と呼ぶ 次曲面を主軸, の座標系で表現 = 主軸変換 主軸変換, a b c, ' ' のとき,, を主軸とする楕円型曲面 b= の場合の, a>,c>, or a<,c< に相当 のとき, または を軸とする放物型曲面 のとき,,, を主軸とする双曲型曲面 8, Satosh Suzuk b= の場合の,a=,orc= に相当 b= の場合の, a>,c<, or a<,c> に相当 変数への拡張 変数の 次関数,, h, h h その内積表現,.8 h h 座標変換 : H... ヘッセ行列 ヘシアン u u ' ' : U 直交行列 U u u ' ' =Hの固有ベクトル を列とする行列 8, Satosh Suzuk 主軸変換 : 式.8 ' h, U ' h 変数 次関数の標準形 h ' U h ' はヘッセ行列の固有値 ヘッセ行列と解の存在性 ヘッセ行列の固有値を調べれば 解を探索せずとも 最適問題の解の有無が分かる 次関数が唯一の最小 最大 値をとるのは ヘッセ行列の固有値が全て正 負 のとき すなわち ヘッセ行列が正定 不定 対称行列のとき ' ' 8, Satosh Suzuk 8, Satosh Suzuk 回分講義終了 エビングハウスの忘却曲線 分後には% を忘却 時間後には56% を忘却 日後には 7% を忘却 週間後 7 日間後 には77% を忘却 ヶ月後 日間後 には 79% を忘却. 人間とは忘れる動物である. 書写し不要 数理計画 第 回 ~ プレ中間試験 ~ 鈴木聡 本試験の注意事項 ノート, 教科書は参照して構いません 私語 不正行為は禁止します 時間 6 分 8, Satosh Suzuk

13 数理計画 第 5 回 ~ 関数の極値 ~ p59~77 鈴木聡 極値 極小 大 値 = 局地的な最小 最大 値ある点,, を含む ある小さい領域内で,, が最大 最小 である時 極大 極小 値という 極値 = 極大値と極小値をあわせた呼び名 8, Satosh Suzuk 極値と停留点 定理 7.7 点,, で関数,, が極値をとれば その点で各変数に関する偏微分係数は.65 式.65 を満たす点は 停留点. その関数値を 停留値 定理 7.7 の逆は必ずしも常に成立しない 反例 : 双曲型 次曲面の鞍点 極値とヘッセ行列 テイラー展開の 次までの項 = 次近似 II,,, 関数,, が点,, で極値をとるとき その点での 次近似は次式で表現できる II,, H, 8, Satosh Suzuk 8, Satosh Suzuk ここで の点 H H はヘッセ行列 での値の 行 列成分,, 定理.8 停留点におけるヘッセ行列が 正 負 定対称行列であれば その点で極小 大 値をとる 8, Satosh Suzuk 定理 8.8 の逆は必ずしも成立しない 例題 : 関数,, z z z の極値を求めよ 解 : まず停留点を求める. 定義式.65 より z z z z z を満たすものが停留点 上式を解くと z z z z,, z,, or 一方 ヘッセ行列は,, z 6 H z z z zz 6z Hの固有値の正負を調べれば極値が求まる 簡単な方法は? 8, Satosh Suzuk

14 固有値の正負判定 シルベスタの定理 対称行列が正定か負定かを, 固有値を計算せずに調べる方法 主小行列式の正負を調べる 小行列式って?... 行列の k 行と l 列を除いてできた 次元の行列 M の行列式 行列式 determat って? A a M a は行列 A の, 成分 例 : a a a a 8, Satosh Suzuk a M a M a [ a] a [ a] aa a a kl 例題の続き点,, ではヘッセ行列は,, 次の主小行列式は 6 6 H 6, 6 6 H シルベスタの定理から, 全ての小行列 > H は正定行列 この点で極小値をもつ 極小値は,,=-5 8, Satosh Suzuk 一方 点,, ではヘッセ行列は,, 次の主小行列式は H H 8, 全ての小行列が正でも負でもない ので 定理よりこの点は極値ではない - 実際 点,, を通り, 軸に -.5 平行な直線上の関数値 -,, -.5 は = で極値をとらない -5-8, Satosh Suzuk まとめ 極値とヘッセ行列 前シートと同じなので書写さなくても OK 定理.8 停留点におけるヘッセ行列が 正 負 定対称行列であれば その点で極小 大 値をとる ヘッセ行列 H 8, Satosh Suzuk 定理.8 の逆は必ずしも成立しない ラグランジュの未定係数法 最大 小 値は 前述したように極値条件から求まる しかし一般の問題にはさらに制約条件がつき, 複雑 目的関数 : 最小 制約条件 : S 極値条件だけでは解くのが困難 ラグランジュの未定係数法制約条件を表す関数の法線と 目的関数の法線は互いに平行であることを利用して 最適問題の解を得る方法 8, Satosh Suzuk 例題 回目講義と同じ 前シートと同じなので書写さなくても OK 問 - 目的関数 : 6 の最大 最小値は? - 制約条件 : 8, Satosh Suzuk

15 解法 未定ラグランジュ法による. 未定係数 λ ラグランジュ乗数という を用い, L = 目的関数 -λ 制約条件 なる関数を作る L 6. 次の条件を満たすとき, 目的関数は最大 最小値をとる L L L,, 8, Satosh Suzuk L L 6 L.~ を連立して解く λ=のとき に代入... を へ代入 この座標値を に代入して は自明. なぜなら= とすると, 式より=となり 制約条件を満たさないから, 5 5, 最小値 λ=7のとき 同様の手順で, と求まり 5 5, 7 最大値 5 5 8, Satosh Suzuk ラグランジュの未定係数法の原理 法線平行 条件 制約条件の法線と 目的関数の法線は互いに平行 具体例: 条件 : 関数 :, の最小 L L L 6.5 L.5 条件 の 法線 6 関数 の法線 -.5, cost. とが平行 - 色は深さを表す ,, 5, 5, 5 m, 6 5 8, Satosh Suzuk ラグランジュの未定乗数法 定理.9 制約条件 g,, のもとで 関数,, が極値をとる点は F,,,,, g,, とおくと 次式を満たす F F,,,,.8 つの法線が平行制約条件 式.8 + 個の方程式 連立して解が求まる 定理 9.9 は必要条件であって 十分条件ではない 極値をとるかどうかの判定が必要 8, Satosh Suzuk 数理計画 第 6 回 ~ 勾配法による関数の最適化 ~ p79~85 最適化問題を解くには テイラー展開の 次項で探索方向を決める その一次項を勾配 グラディエント と呼ぶ 回目講義と同じなので書写さなくても OK 鈴木聡 今回は具体的に最適化問題を解く方法を説明 8, Satosh Suzuk

16 最適化問題の解法の基本 解析的に計算できる場合: をみたす点 を求めればよい 極値定理 導関数 が複雑な場合には解析的に求まらない 数値的に計算せざるを得ない 反復解法 代表的手法 - 勾配法 基本 - ニュートン法 収束速度が速い - 共役勾配法 ニュートン法の簡略版 数値的にとは? 反復法. 定義域内の初期値を選ぶ. 関数が増大 or 減少 する方向を探索. その方向に移動. 関数がある程度収束したら終了 * ポイント - ステップ幅のとり方 - 収束判定 * 8, Satosh Suzuk 8, Satosh Suzuk 勾配法のアルゴリズム 最大値探索の場合. 最大をとる値に近いと思われる点を初期値に選定. ならそこで最大値をとる 終了右上がり -a なら 軸を右へ. h, での 値調査まだ右上がり a-, ならば,, となるまで ステップ幅を逐次 倍にし, 増加が停止した点の一つ前の点を にする 8, Satosh Suzuk, h h h 8h,,,,, 5, =, 5 右へ 移動した先が低いなら a-, ならば,, となるまで ステップ幅を逐次.5 倍にして縮め 増加が停止した点の一つ前の点を にする, 8, Satosh Suzuk h h, h,,,, = を基点にステップ幅を短くしていることに注意, 左上がり h, まだ左上がり, ならば,, -b なら 軸を左へ. での 値調査 b- となるまで ステップ幅を逐次 倍にし, 増加が停止した点の一つ前の点 を にする, 5,,,,5, 8h h h h, 左へ 移動した先が低いなら b-, ならば,, となるまで ステップ幅を逐次.5 倍に縮めて, 減少が停止した点の一つ前の点を にする,. step の方法で次の位置 が求まったら その直前のステップ幅をh として改めて同じ事を実行し, 数列,, を求める 5. ' となるまで繰り返し 最大を与える位置 が求まる * =, 8, Satosh Suzuk 8, Satosh Suzuk *,,

17 反復解法アルゴリズム : search,. の初期値を与え, h h o とする. h sg ' h, X, X ' h とおく. もし X X ' であれば, a X X ' となるまで h h, X X ', X ' X h を繰り返し, b X, h h と置く.. そうでなければ a X X' となるまで, h h, X' X' h 繰返す b X ', h h と置く. 5. Step に戻り, これを ' となるまで繰返す 6. 得られた を返す 7, Satosh Suzuk 変数の場合の勾配法. 初期位置 を選定,. その位置での勾配 を計算. その位置から勾配 方向の直線上で 関数値 を最大にする点を探索 直線探索. その点で再び勾配を計算 5. step-へ 移動量が十分小さくなるまで繰り返し k, k 8, Satosh Suzuk k k k, k 多変数の勾配法 :,, の最大化 hll-clmbg. : R の初期値を与える,,. 関数 F t t に対して手続き search F, F' を呼んで 直線探索を実行 t はスカラ. 返り値 t を用い, t, と更新. step- へ戻り これを となるまで繰返す 5. を返す R k k 勾配法の限界 勾配法はシンプルながらも非常に強力. ただし欠点もある a 微分できない関数では都合が悪い 勾配を使うので 勾配を式で書くのが困難な場合は, 実装不可 b 初期値によっては別の極値に到達する 最大値, 最小値でない極値を局所解という c 関数の形によっては, なかなか最終点に到達しない R 超空間 8, Satosh Suzuk k k t : k k k k 8, Satosh Suzuk b 極値が複数あると 必ずしも最小最大値は見つからない c 細長い尾根の上や 細長い谷細長い谷底にあるときには なかなか極値に到達しない 反復解法の限界 欠点 a,b は, 勾配法のみならず, 微分を用いる全ての反復解法に共通の欠点 局所解を回避する方法 - SA Smulated Aealg : 焼きなまし法 - GA Geetc Algorthm : 遺伝的アルゴリズム 数理計画 第 7 回 ~ニュートン法による関数の最適化 ~ p85~97 鈴木聡 SA: 最初の頃は移動量を大きく 徐々に小さくすることで最適化意を見つけやすくする GA: 解の候補を 遺伝的な個体として表現し 適応度の高い個体を 遺伝的な行為で探索 8, Satosh Suzuk

18 ニュートン法 勾配法は, 関数の 階導関数 ' を利用 階導関数 '' も利用 ニュートン ラフソン法 勾配法とニュートン法の違い - 勾配法 : ステップ幅を 繰返し計算で試行錯誤的に決定 - ニュートン法 : 回の計算でステップ幅を決定 h h h 8h 8, Satosh Suzuk 6h 勾配法 II ニュートン法 ニュートン法を平たくいうと... ある点 で関数 の 次近似を求める II ' ''. 次近似の放物線が極値をとる位置を求める et ' ''. その位置 et まで移動し et としてstep-へ. 十分収束するまで繰り返す 8, Satosh Suzuk II et ニュートン法の原理 次近似した放物線の極値へ移動 これをステップ幅とする テイラー展開の 次近似式 ' '' 軸上の点 の近くの点 でのテイラー展開 上式を の 次式 他は定数 と考えて 最大位置を求める 放物線なので微分 =のところが極値 ' '' ' '' この をステップ幅として採用し 次式で更新する ' '' procedure Newto ', ''. の初期値を与える. とおき 次式で を更新 ' ''. step-に戻り, これを となるまで繰り返す. を返す 8, Satosh Suzuk 8, Satosh Suzuk 6 例題 5 = から探索せよ 解 : 階及び 階微分は ', '' 6 なので 5, ' 5, '' 8 となるよって における の 次近似は II ' '' 5 5 8, Satosh Suzuk 問 : の極値を 次近似 の導関数は II II ' であるので, これをとおいて解くと 6 5 8, Satosh Suzuk 8 を得る 5 5 II

19 8 と更新し 新しい新しい での各導関数値を求めると ' '' よって新しい 次近似関数は II 新しい 次近似 の導関数は II ' II であるので, これをとおいて解くと を得る と更新し. を繰り返していくと解は. と収束し, 極値を与える値が求まる , Satosh Suzuk 8, Satosh Suzuk 多変数の場合 ニュートン法 変数の場合と同様に, 次近似関数の微分 =から H H よって解 のより良い近似値は H 繰返し計算で解が得られる ニュートン法の収束 次収束という 収束が極めて早い K K 回目の近似値と真値との差を とすると, K K K+ 回目での差 はほぼ の定数倍 通常の反復法は 次収束 遅い ニュートン法の欠点 ヘッセ行列が複雑な場合には適用困難 代替手法有 ヘッセ行列の逆行列計算が厄介 次数が大きいときには計算時間必要 また精度心配 8, Satosh Suzuk 8, Satosh Suzuk