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

数理計画

数理計画

鈴 木 聡

(1

回目

)

鈴 木 聡

(1～７回目)

石川 潤（

8～14回目）

石川 潤（

8 14回目）

◆ 講義内容

シラバスと同じなので 書写さなくてもＯＫ 1. 導入. 曲線と曲面の方程式(p1～16) 2 2次形式の標準形と最小値 最大値( 16 40)

◆ 講義内容

2. 2次形式の標準形と最小値・最大値(p16～40) 3. 関数の勾配(p41～59) 4.プレ中間試験 4. プレ中間試験 5. 関数の極値(p59～77) 6. 勾配法による関数の最適化(p78～85) 7. ニュートン法による関数の最適化(p85～97) 8. 中間試験 9 最小二乗法 9. 最小二乗法 10. 確率・統計の復習 11. 最尤推定 12. 線形計画法の考え方 13. 非線形計画法の考え方 14 動的計画法 最適経路問題の考え方 14. 動的計画法、最適経路問題の考え方 ★ ～ 最終試験? レポート? ～ ©2008, Satoshi Suzuki

◆ 数理計画とは？

書写し不要

◆ 数理計画とは？

・一般的な日常問題を数式で表現し、数学的手法で般的な日常問題を数式で表現し、数学的手法で 最適な(もっともらしい)答えを探す作業 ・”最適化問題”ともいう ・ 最適化問題 ともいう ・では「最適(optimization)」とはなんでしょう？ 国語辞典 【名 形動】最も適している こと(さま) - 国語辞典: 【名・形動】最も適している・こと(さま) - 英英辞典: to make as perfect, effective, or

functional as possible 大域性 局所性 計算時間 探査可否 汎用化 柔軟性 ©2008, Satoshi Suzuki

◆ 人生の目標

書写し不要

◆ 人生の目標

・生物は進化の過程である種の最適化問題生物は進化の過程である種の最適化問題 を解いている…ダーウィン的進化 ・人生目標 ・人生目標 - お金持ち? 長生き? 有名人?

・本講義の目的 Charles Robert Darwin [Wikipediaより引用] - "数理計画"を理解する - 評価方法は?...点数をとる 単位をとる [Wikipediaより引用] …ということで… - 目標関数： 中間テスト > 60目標関数 中間テ ト ©2008, Satoshi Suzuki

数理計画・第1回

～曲線と曲面の方程式～

(p1 15)

(p1～15)

鈴 木 聡

鈴 木 聡

©2008, Satoshi Suzuki

◆ 最適化とは（数学的意味で）

・ある状況において最善の決定を行うこと

◆ 最適化とは（数学的意味で）

ある状況において最善の決定を行うこと ・いくつかの選択肢の中から最善のものを選ぶこと ・究極の一番を見つけることではない ・究極の一番を見つけることではない ・optimizationの定式化 与えられた制約条件(constraint)のもとで、 目的関数( bj ti f ti )が最小 最大となるような

目的関数(objective function)が最小or最大となるような、

決定変数(decision variable)を見つけること

※目的関数=望ましさの尺度をあらわす関数

◆ 最適化問題

・決定変数: 通常複数個存在 → ベクトルで表現

◆ 最適化問題

決定変数: 通常複数個存在 → ベクトルで表現 T n x x x x[ 1, 2,, ] ) ( f 目的関数： f(x)→最小 S x 目的関数： →最小 制約条件： ・目的関数 f ： S を含む適当な集合上で定義された実数値関数 実行可能領域S ・実行可能領域S - 変数 x がとることを許された値の集合 S は通常 に関する(不)等式や組合せ式 で表される - S は通常、 x に関する(不)等式や組合せ式、で表される。 ©2008, Satoshi Suzuki

◆ 実行可能領域

・可能領域の特徴を使って最適解を探索する

◆ 実行可能領域

可能領域の特徴を使って最適解を探索する ・適切に S を設定しないと.. 探索終了しない f ( ) - 探索終了しない - 計算機爆発 仕事（卒論）が f (x,y) S 最大解は？ →仕事（卒論）が 終わらない！！ _x o o ©2008, Satoshi Suzuki

◆ 最適化問題を解くための心得

◆ 最適化問題を解くための心得

・条件は何か？条件は何か？ - 制約条件の洗出し 実行可能領域Sの明確化(如何に数式で表現するか) - 実行可能領域Sの明確化(如何に数式で表現するか) ・本当に解ける問題か？ f ( ) の最小値の存在性 極小値の唯 性 - f (x) の最小値の存在性, 極小値の唯一性 - 局所最適、大域的最適 ・解くための労力は？ - 適切な探索アルゴリズムか(解がキチンと見つけられる?) - 計算時間、複雑度は？ ©2008, Satoshi Suzuki

◆ “数理計画”に必要なツール・知識

書写し不要 ・線形代数 ベクトル、行列

◆ 数理計画 に必要なツール・知識

線形代数…ベクトル、行列 ・幾何…直線、曲線、超平面 ・微分(積分) 勾配 偏微分 ・微分(積分)…勾配、偏微分 ・数と集合の概念…凸・閉・開集合 ★きちんと覚えていますか？ ★必要なときに適宜説明しますが、 復習しておくことが好ましい。 ©2008, Satoshi Suzuki

◆ 幾何学

線と直線

・線/曲線: 2次元空間で境界を表す基本要素

◆ 幾何学…線と直線

0 ) (x y  f 線/曲線: 2次元空間で境界を表す基本要素 ・平面/曲面: 3次元空間で、境界を表す 〃 ・n 次元では? 超平面/超曲面 0 ) , (x y  f 0 ) , , (x y z  f 0 ) ( f ・n 次元では?... 超平面/超曲面 ・正則(特異点を持たない) 探索領域に不連続点がないということ 0 ) , , (x₁ x_n  f  - 探索領域に不連続点がないということ ©2008, Satoshi Suzuki

◆ 曲線の方程式

・一般表現： (以下 説明簡略の為 2次元に限定)

◆ 曲線の方程式

0 ) (x y  f 般表現： (以下、説明簡略の為、2次元に限定) ・本講義では正則※_{なものに限る} ※正則=特異点（ となる点）を持たない 0 ) , (x y  f 0 / /   f f ※正則=特異点（ となる点）を持たない ・領域 線（直線でも曲線でも）で区切られた空間 0 / /    f x f y 0 ) , (x y  f f(x,y)0 領域..線（直線でも曲線でも）で区切られた空間 - 片側が なら、反対側は 閉曲線ならば内部と外部では符号が反対 y f(x,y)0 - 閉曲線ならば内部と外部では符号が反対 0 ) , (xy f x 0 ) , (xy f _y 0 ) , (xy f x o o x ©2008, Satoshi Suzuki

◆ 曲線の方程式 例

10 15 ・2次方程式

◆ 曲線の方程式..例

y _f(x,y)0 5 10 y 3 4 2 2_{ }  x x y 0 ) , (xy f y x x y x f( ):2 2 4 3 -2 0 2 4 0 x x o y x x y x f( , ):2 4 3 ? ) 10 , 0 (  f 70 ・楕円方程式 2 2 _y x 2 3 y f(x,y)0 1 4 9   y x -1 0 1 y x o 2 2 0 ) , (xy f -4 -2 0 2 4 -3 -2 x 1 4 / 9 / : ) , (_{x y x}2 _y2 _ f ? ) 2 , 3 (  f( , ) 10 x f 計算機ではこのように、数式で内側・外側を判定する

◆ 内側って何？ 外側って？

書写し不要 ・“外側” “内側”とは人間が

◆ 内側って何？ 外側って？

外側 , 内側 とは人間が 作った抽象的概念 （計算機は 規約なし （計算機は、規約なし に判別できない） 0 ) , (x y  f ・「外側→ 」 と決めたなら、 ©M.C.Escher’s web-site http://www.mcescher.com/ 0 ) , (x y  f 「内側→ 」 に対応させる ※コンピュータの気持ちになって考える ※ ン タ 気持ち な 考 る

◆ 代数解と数値解

・代数解 数値を代入すると解が求まる

◆ 代数解と数値解

代数解...数値を代入すると解が求まる - 例) 式構造から最適問題の 3 4 2 2   x x y y - 式構造から最適問題の 答えが分かる場合がある ②最小値 発 ①最小値を与える 1 ) 1 ( 2  2  x y _{0 x} * x 発見 位置を発見 ・数値解...繰り返し計算(=探索)で 数値的に解を求める y 勾配を使うと効率的になる 勾配を使うと効率的になる * x 0 x ©2008, Satoshi Suzuki

◆ 勾配と法線

・勾配

◆ 勾配と法線

勾配 - ある位置における,関数の変化の程度を表す 探索方向を決める手段のひとつ - 探索方向を決める手段のひとつ ・法線=曲線における垂直方向の勾配 ©2008, Satoshi Suzuki

◆ 法線ベクトルの定義1

・曲線上の微小変位ベクトルを

◆ 法線ベクトルの定義1





T y x     :x 曲線上の微小変位ベクトルを としたとき、内積の極限



x y



  :x 0 ) , ( lim 0 | |x f x  を満たすベクトル を法線ベクトルという 直交するベク が | | f  ・ _x に直交するベクトルが_f ) , ( : x y x x  f  0 ) , (xy  f x x y o ©2008, Satoshi Suzuki

◆ 法線ベクトルの定義2

・テイラー展開の1次の係数

◆ 法線ベクトルの定義2

  テイラ 展開の1次の係数                    y y f x x f f y y x x f( , ) 座標点





Tにおける法線ベクトルであることを   y                       2 2 2 2 2 2 2 2 ! 2 1 y y f y x y x f x x f ・座標点 における法線ベクトルであることを 明示する場合には と書く x x   f: f |





T y x  : x 【定理】 曲線 f ( ) 0の点( ) における法線ベクトルは 曲線 f (x,y)=0の点(x,y) における法線ベクトルは である。





T y f x f f       ©2008, Satoshi Suzuki

◆ 例

・ の位置 での法線は？

◆ 例

1 3 2 2   x x y (1,4):x 解： とおくと、 y 1 3 2 ) , (_{x y} _y _x2 _x f ) ( 解 おく 、 なので 1 3 2 ) , (x y y x x f 3 4   x f 1  f _なので、 x(1,410)         f x 4x 3 3 4    x x y1 _{f:(7,1)}T y 5 よ て                    1 3 4x y f x f f 0 よって、 T f :(7,1)  -2 0 2 x f : ( 7,1)  ©2008, Satoshi Suzuki

◆ 曲線の接線

・直線 の

◆ 曲線の接線

) ( ) ( ) (x y Ax a B y b f     直線 の 法線ベクトルは ) ( ) ( ) , (x y Ax a B y b f  



 

T



T B A y f x f f        ・接線=法線ベクトルが





Tで、点（ a, b )を通る直線 B A 【定理】 点 における曲線 f (x,y)=0の接線は 0 ) ( ) (  f f ) (xy 0 ) ( ) (       y y y f x x x f ©2008, Satoshi Suzuki

◆ 例題

例題：楕円 上の点 の接線は？

◆ 例題

1 2 2  y x





T 3 / 20 2  x 例題：楕円 上の点 の接線は？ 解： とおくと 1 4 9   1 4 / 9 / : ) ( 2  2 f



2 20/3



 x 解： とおくと、 なので f f 2  1  1 4 / 9 / : ) , (x y x2 y2  f 2 3 f  なので、 y y f x x f 2 , 9        2/9 4/9 1 0 1 y f   T 3 / 20 2  x                  6 / 20 9 / 4 2 / 1 9 / 2 y x f -4 -2 0 2 4 -3 -2 -1 よって接線は 4 2 0 2 4 x 0 20 20 ) 2 ( 4         y x よ て接線は ₀ 3 6 ) 2 ( 9 x  _y _ ©2008, Satoshi Suzuki

◆ 曲面の方程式

・一般表現：

◆ 曲面の方程式

0 ) (x y z  f 般表現： ・本講義では基本的に正則なものに限る 0 ) , , (x y z  f ・片側が なら、反対側は ・閉曲面ならば内部と外部では符号が反対 0 ) , , (x y z  f f(x,y,z)0 0 ) , , (xyz f 5 f(x,y,z)0 0 ) , , (xyz f 0 5 5 10 15 20 4 6 8 10 -5 f(x,y,z)0 5 2 4 6 ©2008, Satoshi Suzuki

◆ 例：楕円体

楕円体 に関して

◆ 例：楕円体

1 16 / 4 / 9 / ) , , (_{x y z} _x2 _y2 _z2  f 楕 体 関 ①A点(2,1,2)は内部か外部か？ 1 16 / 4 / 9 / ) , , (x y z x y z f 解： より 内部の点は負であり、 0 1 ) 0 , 0 , 0 (   f 内部の点は負であり、 0 18 / 1 ) 2 , 1 , 2 (   f であるので、A点は内部 ©2008, Satoshi Suzuki

◆ 曲面での法線ベクトル

◆ 曲面での法線ベクトル

【定理】 【定理】 曲面 f (x, y, z)=0の点(x, y, z) における法線ベクトルは である





T f f f f       





Tである。 z f y f x f f         0 ) ( f f  0 ) , , (xyz  f x  x ©2008, Satoshi Suzuki

◆ 例：楕円体上の法線ベクトル

楕円体 に関して

◆ 例：楕円体上の法線ベクトル

1 16 / 4 / 9 / ) , , (_{x y z} _x2 _y2 _z2  f ② における法線ベクトルは? ) ( y y f ) 3 / 92 , 1 , 1 (  x 解 z f y f x f 1 , 1 , 2  _  _   なので、 z y y x 9 ,  2 ,  8                   24 92 2 1 9 2 8 1 2 1 9 2 z y x f    9 2 8 9 2 24 ©2008, Satoshi Suzuki

◆ 曲面の接平面

・平面 の

◆ 曲面の接平面

) ( ) ( ) ( ) (x y z Ax a B y b C z c f       平面 の 法線ベクトル ) ( ) ( ) ( ) , , (x y z Ax a B y b C z c f   



 

T



T C B A z f y f x f f          ・法線ベクトルが





Tで点（ a, b , c )を通る平面 C B A 【定理】 点(x y z)における曲面 f (x y z)=0の接平面は 点 における曲面 f (x,y, z)=0の接平面は 0 ) ( ) ( ) (        z z f y y f x x f ) (x y z ) ( ) ( ) (   x y y y z ©2008, Satoshi Suzuki

◆ 例：楕円体上の接平面

楕円体 に関して

◆ 例：楕円体上の接平面

1 16 / 4 / 9 / ) , , (_{x y z x}2 _y2 _z2 _ f ③ における接平面は？ ) ( y y f ) 3 / 92 , 1 , 1 (  x 解： 前述の例題から         24 92 2 1 9 2 f なので、9 2 24  92 92 1 2   0 3 92 24 92 ) 1 ( 2 1 ) 1 ( 9 2 _            y z x   ©2008, Satoshi Suzuki

数理計画・第２回

～

2次形式の標準形と最小値・最大値～

(p16 40)

(p16～40)

鈴 木 聡

鈴 木 聡

◆ 直線・曲面の一般化

・直線や曲面は2 or 3次元の幾何学要素

◆ 直線・曲面の

般化

...このままでは説明変数が3つまでの問題しか解けない ・数理計画ではn次元へ拡張する必要アリ数理計画ではn次元 拡張する必要アリ 数学的に(名称を) 般化 ・数学的に(名称を)一般化 - 直線 >>[ 一般化] >>１次形式 - 放物線>> [一般化] >> 2次形式 ©2008, Satoshi Suzuki

◆ １次形式

◆ １次形式



   ax a_nx_n n a_ix_i f _{1 1  (1.40)}     a1 _ x1_



 i i i n n f 1 1 1 (1.40) ・ベクトル表現 とおくと          a  1 : a          x  1 : x    an xn     x1





          _n x a a f _{1  } aTx ...内積で表現可    xn

 

a,x  ©2008, Satoshi Suzuki

○ 復習；行列論

○ 復習；行列論

・内積 - ２つのベクトルに対する演算操作 - <ベクトル>・<ベクトル> → <スカラ>

 

a,x aTx <ベクトル> <ベクトル> → <スカラ> - 教科書に準じ 内積は 行列は と書く

 

_{a,x R}1 n R  a _Rn x

 

a x

 

a x 教科書に準じ、内積は 、行列は と書く - 間違えやすいので注意 （行列は

 

a,x の方が好ましいが

 

...） x a

 

a x BA AB  ・行列 - 一般に非可換：AB  BA T T T _{B A} AB ) (

A

A

T



般 非可換 - 対称行列： 転置の分配： _(AB)T  _BT_AT - 転置の分配： ©2008, Satoshi Suzuki

◆ １次形式の微分

・１次形式： を各変数で偏微分すると

◆ １次形式の微分

n nx a x a f  _{1 1}_ _{n n} f _{1 1} ) 1 (i n a x f  _i _i  _   f /x よって と定義すると、 と書ける            x f f / : 1  f a さらに とも書けるから、次の定理が成立    f /xn

 

a,x  f 【定理】

 

, f １次形式(a,x)の微分は、 ,

 

a x a ①内積(スカラ)を、 ②微分すると, _{③ベクトルになる,} ©2008, Satoshi Suzuki

◆ 2次形式

◆ 2次形式

2 2 1 11x annxn a f  ₁₁₁ _ _{nn n} f n n n n x x a x x a x x a_{12 1 2} 2 _{13 1 3} 2 _{( 1) 1} 2       _ n



i j (1.47) j i ijxx a



  1 ,





            n x a a x x _{   }   1 1 11 1





            n nn n n x a a x x _     1 1 x x AT :  (x,Ax) ...内積で表現可 ※Aは対称行列 「２次形式の係数行列」 ※Aは対称行列：aijaji ©2008, Satoshi Suzuki

◆ 例題（2次形式）

問：次の２次形式をベクトルと対称行列とで表せ

◆ 例題（2次形式）

2 2 2 1 2 1 2bxx cx ax f    解 1.変数の横ベクトル・係数行列・縦ベクトルの枠を準備  ○ ○x1 2 2次の係数を対角要素に並べる   _             2 1 2 1 x x x x f ○ ○ ○ ○ 2. 2次の係数を対角要素に並べる





_             1 2 1 x x c a x x f ○ ○ 3. 1次の係数の1/2を非対角要素に並べる    ○ c x2        a b x





_             2 1 2 1 x x c b b a x x f

◆ ２次形式の微分

2次形式(1.47)を で微分→ を含む項を取出すと

◆ ２次形式の微分

1 x 1 x ( ) これを微分すると n nxx a x x a x x a x a 2 _{12 1 2 13 1 3 1 1} 1 11 2 2 2 これを微分すると



     a x a x anxn n a jxj x a11 1 2 12 2 2 13 3 2 1 2 1 2 _ 他の変数 x_i ( i=1…n) についても同様なのでj 1 f n 

_

n i x a x f j j ij i , , 1 2 1     

_

 が成立する 注目！ ©2008, Satoshi Suzuki

◆ ２次形式の微分(続き)

改めて i=1～n まで並べると

◆ ２次形式の微分(続き)



    n j j jx a x f 1 1 1 2 / ベクトルAxの1行め要素  j 1 _{ }



   n j j nj n a x x f 1 2 / ベクトルAxのn行め要素  _{ }



f x f x



T f  / _ /  j 1 x A 2  【定理】



f x f x_n



f  / _{1 } / 2Ax 【定理】 2次形式(x,Ax)の微分は、



x,Ax



2Ax ©2008, Satoshi Suzuki

◆ 例（2次形式の微分）

２次形式 の内積表現は

◆ 例（2次形式の微分）

2 2 _{6 4} 5x xy y f   y y f ) 4 3 3 5 , ( _                   y x y x f なので、f の微分は定理より から 4 3 _{ }   y y



x,Ax



2Ax                        y x y x y x A 8 6 6 10 4 3 3 5 2 2 x ・微分計算が極めて容易       3 4 y 6x 8y → 計算機で数値解を求める数理計画にとって好都合 ©2008, Satoshi Suzuki

◆ 2次形式の標準形

・２次形式の利点

◆ 2次形式の標準形

- 最適化の評価関数としてよく利用 - 最適探索に必要な微分計算が簡単最適探索に必要な微分計算が簡単 -最大・最小値の計算も容易→2次形式標準形 ・標準形とは 1. 変数の座標変換で、 2 評価関数を簡単化(干渉項を消去)すること 2. 評価関数を簡単化(干渉項を消去)すること 例: _f _6x2_4xy_3y2 _f _2x'2_7y'2 ©2008, Satoshi Suzuki

◆ まずは例題

目的関数 _{f( )} 最小 ・問

◆ まずは例題

目的関数： →最小 制約条件： ) (x f S  x - 目的関数： の最大、最小値は？ - 制約条件： 2 2 3 4 6x xy y f    1 2 2_{ y } x 制約条件： x  y 1 ©2008, Satoshi Suzuki

◆ 例題の解法（概略）

1. 制約条件を満たしたまま、座標変換

◆ 例題の解法（概略）

} ' , ' { } , {x y  x y …なぜこの係数か？→後で説明  x'x/ 52y/ 5 } { } { y y    2 / 5 / 5 ' x y y x'2 y'21 2 目的関数を標準形へ（上の変換式を変形して代入） 2. 目的関数を標準形へ（上の変換式を変形して代入）  xx'/ 52y'/ 5 2 2 _{4 3} 6x xy y f    _{f 2x'}2_7y'2      2x'/ 5 y'/ 5 y 3 4 6x xy y f    f 2x 7y 3. 従属変数を消去. 変数範囲考慮して最大小値判明 2 2 2 ' 5 2 ' 7 ) ' 1 ( 2 y y y f      fmax7, fmin2

◆ 標準形と固有値・固有ベクトル

・ 変数が多くなると式変形が煩雑・面倒

◆ 標準形と固有値・固有ベクトル

→ 行列の性質を使うともっと簡単! ・ 実は先の実は先の座標変換座標変換は 係数行列は、係数行列AAのの固有ベクトル固有ベクトル ・ さらにf の最大・最小値は、Aの最大・最小固有値 2 2 3 4 6x xy y f    _             y x y x f 3 2 2 6 ) ( 2次形式    2 3 y 2 ) 2 ( ) 3 )( 6 ( 2 6 | |IA  ( )( )( ) 3 2 | |    ) 2 )( 7 ( 14 9 2_{    }   ( )( ) 7,,2 ©2008, Satoshi Suzuki ・固有ベクトルu ・固有ベクトルu 固有値・固有ベクトルの定義式 に固有値λを 代入して求める u u A ・ の固有ベクトル に関し、 u₁,u₂を未知数として 代入して求める 2 : 1   u1 、 1, 2 数              1 1 2 2 6 u u 2 : 1  1 1,2行目とも2u₁ u₂0 解の一つは             2 2 2 3 2 u u , 行目とも2u1 u2 0   2 1   u u 解の つは だが、単位ベクトルにとり、 _        5 / 2 5 / 1 1 u 2 , 1 ₂ 1 u  u     2/ 5 ・ _{: 7}の固有ベクトル に関しても同様に 2   u2        5 / 1 5 / 2 2 u  1/ 5 ©2008, Satoshi Suzuki

・固有ベクトルuを並べると 先の座標変換_{x Ux'}となる ・固有ベクトルuを並べると、先の座標変換 となる      (u u ) 1/ 5 2/ 5 U ' x xU       5 / 1 5 / 2 ) (u₂ u₂ U 確認 ・確認                 x 1/ 5 2/ 5 x' x'/ 5 2y'/ 5                         5 / ' 5 / ' 2 5 / 2 5 / ' 5 / 1 5 / 2 5 / 2 5 / 1 y x y x y y 先の変換式と同じ 先の変換式と同じ 座標変換は 係数行列Aの固有ベクトル ・座標変換は、係数行列Aの固有ベクトル ・ f の最大・最小値は、Aの最大・最小固有値 ©2008, Satoshi Suzuki

◆ 2次形式と正定行列

・ 2次形式(quadratic form)： 変数 についての2次のべき関数 a xx

◆ 2次形式と正定行列

- 変数 についての2次のべき関数 - 対称行列 を用いて と書ける 例: n x x x₁, ₂,   i j ij i j x x a A xTAx 2 2 2 _{2 4 6} 2    例: 2 3 2 2 3 1 2 1 2 1 2 4 6 2x  x x  x x x  x 1 3 2 3 1 2 2 2 3 1 2 1 2 1 2 6 2 2x x x  x x x x x  x  x x     





x x Ax x x x x _ T                ₂ 1 3 2 1 1 1 0 2 1 2 見行列のようだが x            2 0 6 3 定 値 T  一見行列のようだが、 スカラーであることに 注意 ・正定[正値] (positive definite): 半正定[半正値] (pos. semi-def.): 負定[負値] ( ti d fi it ) ) 0 ( 0    x Ax xT ) 0 ( 0   _x Ax xT ) 0 ( 0  A T 負定[負値] (negative definite): xTAx 0 (x0) ©2008, Satoshi Suzuki

・正定行列(positive definite matrix)：

- 2次形式_2次形式xTAxが正定のとき、行列 を正定行列といい、_{が正定のとき、行列 を正定行列といい、A} と書く - 2つの対称行列について、A B0のときは と書く A Ax x 0  A B A ・正定行列の性質 0  A n l R C  A 0  C CT (a) である為の必要十分条件は の固有値が全て正 (b) 任意の行列_CR に対して、_{C C 0} 0  Cx C xT T _Cx0 ( ) (c) と は等価 ©2008, Satoshi Suzuki

◆ 行列の対角化

・「行列の対角化」と「2次形式の標準化」は等価

◆ 行列の対角化

            7 0 0 2 3 2 2 6  2 2 3 4 6x xy y f    2 2 _{7 '} ' 2 f 

＝

       2 3 0 7 _{f 2x'}2_7y'2 係数行列Ａ(対称行列)の対角化は直交行列で ・係数行列Ａ(対称行列)の対角化は直交行列で. ・直交行列 - 正規直交に選んだ固有ベクトルを並べたもの n n R ) ( U u1 u2_u   - …重要! n) R ( U u1 u2 u  I U UT  _U1_UT ©2008, Satoshi Suzuki

◆ スペクトル分解（固有値分解）

定義から なので、

◆ スペクトル分解（固有値分解）

n n n A Au1111u11,,,, unnun



n

 

A A A n



Au₁,u₂,_,u  u₁, u₂,_, u





U





n nu u u   1 1, 2 2,, 



_



diag



  _



 u u u U



1, 2, , n



diag



1 2 n



 u u u ) ( diag _{1 2 n} U   _  上式の両辺に左から_UTをかけると ) ( diag ) ( diag T T U U AU U AUU U diag(₁ ₂ _n)diag(₁ ₂ _n) U     _    _ スペクトル分解： T U U A diag(  _ ) スペクトル分解： AUdiag(₁ _2_n)U ©2008, Satoshi Suzuki

◆ 標準形と座標変換

座標変換:直交行列U を用いる

◆ 標準形と座標変換

x x_'UT ・ U は直交なので逆行列=転置行列 ' U ) ( ) ' ( _{U U}T U(x')_U(_UTx)x xUx' U ・2次形式



A



は以下のように変形できる



x,Ax

 

 Ux',AUx'



・2次形式



x A, x



は以下のように変形できる



 



) ' ( ' ' ' ' ) ' (Ux TAUxxTUTAUxxTUTAUx  ) ' ) ( diag ' ( ) ' ' (x_',UT_AUx_{') (}x_',diag(  ₎x_') (x U AUx  x _1 _n x  2 2 2 2 2 1 1x'  x' nx'n   _  _{1 1 2 2 n n} …二乗和形式=標準形 係数はＡの固有値 ©2008, Satoshi Suzuki

◆ 正値2次形式

◆ 正値2次形式

【定理1.12-13】 A が半正値対称行列( )の時、 - 2次形式(x, A x)を最大(最小)にする単位ベクトルｘは 0 ) ( ,  _{i A} i  2次形式(x, A x)を最大(最小)にする単位 クトルｘは A の最大(最小)固有値に対する固有ベクトル 2次形式( A )の最大(最小)値は - 2次形式(x, A x)の最大(最小)値は 行列Aの最大(最小)固有値 ©2008, Satoshi Suzuki

数理計画・第３回

～関数の勾配～

(p41～59)

(p41～59)

鈴 木 聡

鈴 木 聡

◆ 勾配と最適化問題

・探索=評価関数が減少(増加)する方向をさがす

◆ 勾配と最適化問題

・勾配＝関数の偏微分係数 ・テイラー展開テイラ 展開=勾配を利用した関数近似法=勾配を利用した関数近似法 1 (2) 2 ) 1 ( ) ( ) ( ! 2 1 ) ( ) ( ) ( ) (x f a f a x a f a x a f        n n f f ( ) ( ) 1 ( ) ( ) 1 (3) 3 ()          _f n _{a x a} n n a x a f ( ) ( ) ! ) ( ) ( ! 3 ) ( 3 ) 3 ( x f a f( ): ( ) ただし n n _a d _{f x} f()( ): ( ) a x f f( ) ( ) _ a x n f x dx a f  ) ( : ) ( ©2008, Satoshi Suzuki

◆ 復習: テイラー展開

例題： の 近傍でのテイラー展開は？

◆ 復習: テイラ 展開

) sin( ) (x x f  x0 解: 微分係数を計算すると 解: 微分係数を計算すると なので 公式に代入して



/2



sin



/2



sin : ) 0 ( ) ( 0 ) ( ) (   n n x f x f x n n _{   }  なので、公式に代入して 2 ) 0 ( 2 sin 1 ) 0 ( sin ) 0 sin( ) (x     x    x f   ( 0) 2 sin ! 2 ) 0 ( 2 sin ) 0 sin( ) (               x x x f      1 _i 3 _{( 0)}3            _{( 0)}3 2 sin ! 3 x 1 2 5 3 _{x x} x n    _      )! 1 2 ( ) 1 ( ! 5 ! 3 n x x x x n ©2008, Satoshi Suzuki

◆ 例題（続き）

とそのテイラー展開の1,3,5,7次近似

◆ 例題（続き）

) sin( ) (x x f  1.5 1 1.02 ! 5 ! 3 5 3 _x x x y   x y 1 0.96 0.98 ) , ( yx f ysin(x) x y y 0.5 1.35 1.4 1.45 1.5 0.92 0.94 ! 3 3 x x y  y 0 0 5 1 1 5 0 3! 5! 7! 7 5 3 x x x x y    ! 3 0 0.5 _x 1 1.5 ・高次になるほど、良い近似 ・方向を決めるだけ（=値の精度を気にしない）なら1次項で十分 ©2008, Satoshi Suzuki

◆ 関数のテイラー展開

・2次変数関数

◆ 関数のテイラ 展開

) , (x y f ・ある固定点_(x,y)近傍の座標 でのテイラー展開  f f ) , (x y            ( ) ( ) ) , ( y y y f x x x f f y x f_ta y x f f   ( , ) y y x x y x f f: ( , )|_, x x x y f x f     ) , ( : ただし ) , (x y fta ) , (xy f f ) (x,y) (x y ) , (xy テイラー展開 は の近くでのみ ) , (x y fta (x,y) ) , ( ) , (x y f x y fta  ©2008, Satoshi Suzuki

◆ 接平面

・テイラー展開の2次以上の項を無視(1次近似)した関数

◆ 接平面

…. 接平面 (2.53) ) ( ) ( ) , ( y y y f x x x f f y x f_I          y x   A点 接平面：fI(x,y) )) , ( , , (x y f x y 曲面：f(x,y) ©2008, Satoshi Suzuki

◆ 勾配（グラディエント）

・(2.53)式の接平面の勾配は

◆ 勾配（グラディエント）



f/x, f /y



・関数 の勾配を、接平面の勾配を利用して と定義





) , (x y f





T y f x f f       : / / と定義 ・f はＡの近傍で関数値 f が最も急激に増大する方向



f x f y



f       : / / 接平面の等高線 接平面上の最急上昇方向 A点 曲面の等高線 2 R f  ©2008, Satoshi Suzuki

◆ n 次への拡張

・n 次変数関数

◆ n 次への拡張

) , , (x₁ x_n f _ ・1次近似=テイラー展開の2次以上の項を無視した関数 f f   1 n 関数 の勾配 ) ( ) ( ) , , ( _{1 1} 1 1 n n n n I x x x f x x x f f x x f           _  ・関数 の勾配





1 1 / / :       _{f f x f y}T _Rn  ) , , (x₁ x_n f _ は の近傍で関数値 f が最も急激に増大する方向 向 増 率



f 1 f y



f x f  ※ノルム＝ベクトルの大きさを表す尺度 ・ノルム_{|| f ||}はその方向の増加率 ※ ル クトルの大きさを表す尺度 のとき 1 1 ) (    n T n R a a  a ||a|| a12an2R1 ©2008, Satoshi Suzuki

◆ 最適化問題を解くには（小まとめ）

・テイラー展開の1次項(勾配)で探索方向を決める

◆ 最適化問題を解くには（小まとめ）

…勾配の具体的な探索方法は後日 ©2008, Satoshi Suzuki

◆ 2次関数の一般系

・平行移動で、2次の項と定数のみに変形できる

◆ 2次関数の 般系

例: f(x,y)3x26xy4y26x4y1 関数値が極値をとる位置を求めるには定数項は無関係 3 4 6 3 ) 1 , 2 (_{x y  x}2_{ xy y}2_ f ・関数値が極値をとる位置を求めるには定数項は無関係 →定数項を無視した式を2次形式の一般式として扱う 0 , , ) 2 ( 2 1 ) , (x y  ax2 bxycy2 abc f ※1/2は慣例 (微分するとすっきりするから) 平行移動量の求め方 教科書【例題2 2】参照 2 ・平行移動量の求め方→教科書【例題2.2】参照 ©2008, Satoshi Suzuki ・係数 a,b,c の正負で形状が違う I. b=0 の場合の場合 ① 楕円型 ② 放物型 ② 放物型 ③ 双曲型 II. b=0 でない場合 主軸変換軸変換を行うと, b=0の場合と同じになるを行う , 場合 同 なる ©2008, Satoshi Suzuki

◆ 2次関数の極値

（その１：b0の場合） ①

◆ 2次関数の極値

（その１： の場合） ) 3 2 ) , ( : ( 0 , 0 , 0_{b c f x y x}2 _y2 a   例   0  b ・原点で最小値（ なら最大値） ・楕円型 ) ) , ( ( , , f y y 0 , 0 , 0    b c a 楕円型 ・x, y 軸がその対称軸…主軸と呼ぶ 2 y 0 1 2 -1 x -2 -1 0 1 2 -2 ©2008, Satoshi Suzuki 主軸

◆ 続き

②

◆ 続き

) 2 ) , ( : ( 0 f x y y2 b a  例  ・x 軸(y 軸)に沿って関数値が一定 ・放物型 ) ) ( ( f y y 放物型 ・x 軸(y 軸)がその対称軸…主軸と呼ぶ 2 y 0 1 主軸 -2 -1 主軸 x -2 -1 0 1 2 -2 ©2008, Satoshi Suzuki

◆ 続き

③

◆ 続き

) 3 2 ) , ( : ( 0 , 0_{b f x y x}2 _y2 ac  例   ・x 軸(y 軸)方向に凹、 y 軸(x 軸)方向に凸 ・双曲型 鞍点(あんてん)をもつ ) ) , ( ( , f y y 双曲型, 鞍点(あんてん)をもつ ・x , y 軸がその対称軸…主軸 2 y 0 1 -1 x -2 -1 0 1 2 -2 ©2008, Satoshi Suzuki 主軸

◆ 評価関数構造の見極め

・なぜ一般化が必要か

◆ 評価関数構造の見極め

- 最適解の存在可否を事前に知る - 最大/最小値の存在が保証されているか?最大/最小値の存在が保証されているか? 楕 型 放物型 双曲型 楕円型 放物型 双曲型 最適値の存在性 ○ ○ × 最適値を与える条件 唯一 無数 × ©2008, Satoshi Suzuki

◆ 2次関数の極値

（その２：b0の場合）

◆ 2次関数の極値

（その２： の場合） ・先は_b0の、干渉項がゼロの場合 0  b ・ _b0では？→主軸変換をすると _b0の場合と同じ 1 0 , , ) 2 ( 2 1 ) , (_{x y}  _ax2 _bxy_cy2 _{ab c} f     b                           y x c b b a y x , 2 1 _(2.21)  y  y H :  ...2次関数のヘッセ行列 （ヘシアン） （ヘシアン） ©2008, Satoshi Suzuki y         回転の座標変換 x O    _       cos : , sin : ' ' : ' '                               c s y x R y x c s s c y x O         y y y を一般形(2.21)に代入すると、最終的に次式になる   '  b  '                          ' ' , ' ' 2 1 y x R c b b a R y x f T  【復習】ｽﾍﾟｸﾄﾙ（固有値）分解T n U U A diag(1 2)        回転行列_Rは直交行列なので、ここは対角化できる          1 0     R b b a RT 角度 を選ぶと の形になるハズ         0 2   c b ©2008, Satoshi Suzuki →では λの値は？

◆ 主軸変換

◆ 主軸変換

・ はヘッセ行列_Hの固有値 2 1,  ・ を主軸と呼ぶ ・2次曲面を主軸 の座標系で表現=主軸変換 2 1 y x,  y x  2次曲面を主軸x ,yの座標系で表現 主軸変換 ) 2 ( 1 ) , (xy ax2 bxy cy2 f    ( ' ' ) 2 1 ) , ( 2 2 2 1x y y x f      主軸変換 ) ( 2 ) , ( y y y f ( ) 2 ) , ( y _{1 2}y f ・1122 00 のとき,のとき, を主軸とする楕円型曲面x ,x yyを主軸とする楕円型曲面 ・ ₀のとき, または を軸とする放物型曲面 2 1   x y b=0の場合の, a>0,c>0, or a<0,c<0に相当 ・₁₂0 のとき, を主軸とする双曲型曲面x,y のとき, または を軸とする放物型曲面 0 2 1  x y b=0の場合の, a=0, or c=0に相当 のとき, を主軸とする双曲型曲面 0 2 1   x ,y b=0の場合の, a>0,c<0, or a<0,c>0に相当 ©2008, Satoshi Suzuki

◆n 変数への拡張

・n 変数の2次関数

◆n 変数への拡張



 n _{ij i j} n h xx x x f ₁ 2 1 ) , , ( _



 j i j j 1 , 2   x  h h x  ・その内積表現 (2.28)                                  n x h h x f       1 1 11 1 , 2 1     xn hn1  hnnxn 2 H :  ヘッセ行列 座標変換 :H ... ヘッセ行列 （ヘシアン）                x1 u11  u1 x'₁ x'₁ ・座標変換                                   n x U x u u x : 1 1 1 11 1       直交行列Ｕ =Hの固有ベクトル                xn u1n  unn x'n x'n =Hの固有ベクトル を列とする行列 ©2008, Satoshi Suzuki ・主軸変換：式（2.28）→                x' h _ h x'                                  n T x U h h U x f , 2 1 1 11 1 1          x'n hn hnn x'n 2 1               1 _は ヘッセ行列n  _1 ・

n

変数2次関数の標準形     n ッセ行列 の固有値 ) ' ' ( 2 1 2 2 1 1x nxn f   _ 2 ©2008, Satoshi Suzuki

◆ ヘッセ行列と解の存在性

◆ ヘッセ行列と解の存在性

・ヘッセ行列の固有値を調べれば（解を探索せずとも）、 最適問題の解の有無が分かる ・２次関数が唯一の最小(最大)値をとるのは、 ヘッセ行列の固有値が全て正（負）のとき。 すなわち ヘッセ行列が正定(不定)対称行列のとき すなわち、ヘッセ行列が正定(不定)対称行列のとき。 ©2008, Satoshi Suzuki 書写し不要

◆ ３回分講義終了

◆ ３回分講義終了

★エビングハウスの忘却曲線 20分後には42%を忘却 1時間後には56%を忘却 後 を忘却 1日後には74%を忘却 1週間後（7日間後）には77%を忘却 1ヶ月後（30日間後）には79%を忘却 1ヶ月後（30日間後）には79%を忘却 ….人間とは忘れる動物である. ©2008, Satoshi Suzuki

数理計画・第4回

～プレ中間試験～

鈴 木 聡

鈴 木 聡

■本試験の注意事項 ・ノート 教科書は参照して構いません ・ノート, 教科書は参照して構いません ・私語、不正行為は禁止します ・時間時間60分分

数理計画・第５回

～関数の極値～

(p59 77)

(p59～77)

鈴 木 聡

鈴 木 聡

◆ 極値

◆ 極値

・極小(大)値= 局地的な最小（最大）値 ある点 を含む、ある小さい領域内で が最大(最小)である時、極大(極小)値という ) , , (x1 xn ) , , (x1 x f  が最大(最小)である時、極大(極小)値という ・極値= 極大値と極小値をあわせた呼び名 ) , , (x1 xn f ©2008, Satoshi Suzuki

◆ 極値と停留点

◆ 極値と停留点

【定理2 7】 点( )で関数f( )が極値 【定理2.7】 点 で関数 が極値 をとれば、その点で各変数に関する偏微分係数は０ ) , , (x_1 x_n f(x₁,_,x_n) (2.65) 0 1        n x f x f  _{( )} 1 n ・式式(2 65)を満たす点は”(2.65)を満たす点は 停留点停留点” その関数値を”. その関数値を 停留停留 値” 定理2 7の逆は必ずしも常に成立しない ・定理2.7の逆は必ずしも常に成立しない ※反例： 双曲型2次曲面の鞍点 ©2008, Satoshi Suzuki

◆ 極値とヘッセ行列

・テイラー展開の2次までの項 = 2次近似

◆ 極値とヘッセ行列





           n i i j j n i i n II x x x x x x f x x x f f x x f 2 1 ( )( ) 2 1 ) ( ) , , (      i j ij i1 xi 2 1, 1 x x ・関数f(x₁,_,x_n)が点(x₁,_,x_n)で極値をとるとき、 その点での2次近似は次式で表現できる 1 n 1 n f n 1

_

      n j i j j i i ij n II x x f H x x x x f 1 , 1 1 ( )( ) 2 1 ) , , ( _ ©2008, Satoshi Suzuki は セ行列 ここで はヘッセ行列  2f/  2f/  ij H               n x x f x x f H / / 1 2 1 1 2     の点 での値の 行 列成分     f/xnx  f/xnxn 2 1 2  の点 での値のi 行j 列成分 ) , , (x_1 x_n 【定理2.8】 停留点におけるヘッセ行列が、 負定対称行列 あれば そ 点 極 大値をとる 正(負)定対称行列であれば、その点で極小(大)値をとる ・定理2 8の逆は必ずしも成立しない ・定理2.8の逆は必ずしも成立しない ©2008, Satoshi Suzuki

◆ 例題:

関数f(xy z)x3y2z33xz4yの極値を求めよ

◆ 例題:

関数f(x,y,z)x y z 3xz4yの極値を求めよ 解：まず停留点を求める. 定義式(2.65)より( ) 0 3 3 2_{ }    z x x f _{2 40}   y y f 0 3 3 2_{ }    x z z f x を満たすものが停留点。 上式を解くと y 0 ) 1 ( 3_{ } z z 0 ) 1 )( 1 (_{z z}2_{z } z ) 0 , 2 , 0 ( ) 1 , 2 , 1 ( ) , , (x y z  or 一方、ヘッセ行列は                         f f f z x f y x f x x f H / / / / / / 2 2 2 2 2 2       x  0 2 0 3 0 6                      z z f y z f x z f z y f y y f x y f H / / / / / / 2 2 2        z 6 0 3 0 2 0 Hの固有値の正負を調べれば極値が求まる…(簡単な方法は?) ©2008, Satoshi Suzuki

◆ 固有値の正負判定

シルベスタの定理

◆ 固有値の正負判定…シルベスタの定理

・対称行列が正定か負定かを, 固有値を計算せずに 調べる方法→ 主小行列式の正負を調べる 小行列式 て? 行列のk 行とl 列を除いてできた ・小行列式って?...行列のk 行とl 列を除いてできた 次元の行列 の行列式 ) 1 ( ) 1 (n n M_kl n ・行列式(determinant)って?



  _{ }   n j ij ij j i M a A 1 ) 1 ( | | aijは行列A の(i,j)成分 12 12 2 1 11 11 1 1 12 11 ) 1 ( ) 1 ( a M a M a a a a               例： 22 21 a a _  21 12 22 11 21 12 22 11|[a ]| a |[a ]| a a a a a       ©2008, Satoshi Suzuki

◆ 例題の続き

点(1,2,1)ではヘッセ行列は

◆ 例題の続き

       0 2 0 3 0 6 H 60 6 0 6 2 00 120 1,2,3次の主小行列式は        6 0 3 0 2 0 H 6 2 00 12 0 2 0 , 0 6       2 0 0 0 0 2 0 3 2 0 ) 3 ( 3 6 0 0 0 6 0 0 2 6           H 0 54 ) 6 ( 3 0 12 6       シルベスタの定理から 全ての小行列>0 シルベスタの定理から, 全ての小行列>0 →H は正定行列 ・この点で極小値をもつ ・極小値はf (1,2,1)=-5 ©2008, Satoshi Suzuki 方 点( ) は セ行列は 一方、点(0,2,0)ではヘッセ行列は  0 0 3 1,2,3次の主小行列式は           0 2 0 3 0 0 H 0 2 0 0 0 , 0  H180    3 0 0 , 0 2 “全ての小行列が正でも負でもない”ので 定理より全ての小行列が正でも負でもない ので、定理より この点は極値ではない _-3 ※実際、点(0,2,0)を通り, x 軸に 平行な直線上の関数値 4 -3.5 4 ) 0 , 2 , ( _{ x}3_ x f 平行な直線上の関数値 -4.5 -4 f は、 x=0 で極値をとらない -5 _{-1 0 1} x ©2008, Satoshi Suzuki

◆ まとめ・極値とヘッセ行列

前シートと同じなので 書写さなくてもＯＫ 【定理2.8】 停留点におけるヘッセ行列が、

◆ まとめ・極値とヘッセ行列

【定理 】 停留点 おける ッ 行列 、 正(負)定対称行列であれば、その点で極小(大)値をとる ・定理2.8の逆は必ずしも成立しない ヘッセ行列    2f/xx  2f/xx               n x x f x x f H / / 2 2 1 1 1         f/xnx  f /xnxn 2 1 2  ©2008, Satoshi Suzuki

◆ ラグランジュの未定係数法

◆ ラグランジュの未定係数法

・最大(小)値は、前述したように極値条件から求まる ・しかし一般の問題にはさらに制約条件がつき,複雑 ) (x f S x 目的関数： →最小 制約条件： …極値条件だけでは解くのが困難 ・ラグランジュの未定係数法 制約条件を表す関数の法線と、目的関数の法線は 制約条件を表す関数の法線と、目的関数の法線は 互いに平行であることを利用して、最適問題の解を 得る方法 得る方法 ©2008, Satoshi Suzuki

◆ 例題

(3回目講義と同じ) 前シートと同じなので 書写さなくてもＯＫ ・問

◆ 例題

(3回目講義と同じ) - 目的関数： の最大、最小値は？ - 制約条件： 2 2 _{4 3} 6x xy y f    1 2 2_{ y } x 制約条件： _{x  y 1} ©2008, Satoshi Suzuki

・解法 （未定ラグランジュ法による) 1 未定係数λ(ラグランジュ乗数という)を用い 1.未定係数λ(ラグランジュ乗数という)を用い, L =(目的関数)-λ(制約条件) なる関数を作る ) 1 ( 3 4 6 2_{ } 2_ 2_ 2_  x xy y x y L  2 次の条件を満たすとき 目的関数は最大/最小値をとる 2.次の条件を満たすとき, 目的関数は最大/最小値をとる 0 0 0      L L L 0 , 0 , 0      x y  0 2 4 12 /  L/x12x4y2x0 ① L x x y x 0 2 6 4 /     L y x y y …① …② 0 ) 1 ( /_{ } 2_ 2_{ } L  x y …③ ©2008, Satoshi Suzuki 3 ①～③を連立して解く 3.①～③を連立して解く ①②→ →(6)(3)y4y0 (2)(7)0 は自明 なぜならy=0 0  y は自明. なぜならy 0 とすると, ②式よりx=0となり、 制約条件を満たさないから 0  y 4-1.λ=2のとき ①に代入→ ④を③へ代入→ → ④ ... 0 2x y 1 ) 2 ( 2 2  _x  x x 1 y_ 2 ④を③ 代入 この座標値を f に代入して 1 ) 2 (  x x 5 , 5   y x 2 ) 2 , 1 ( _  f ) …最小値 5 , 5 ( f 4-2.λ=7のとき 同様の手順で 2 1 と求まり 同様の手順で と求まり、 5 1 , 5 2     y x 7 ) 1 2 (   f _{) 7} 最大値 5 , 5 (   f …最大値 ©2008, Satoshi Suzuki

◆ ラグランジュの未定係数法の原理

・制約条件の法線と、目的関数の法線は互いに平行

◆ ラグランジュの未定係数法の原理

・具体例： 条件: 関数：x y1 _f(x,y)_2x2_3y2の最小 ) 1 ( 3 2 2_ 2 _ L_2_x2_3_y2_(_xy1) 1‘条件’の L  0 4 /    L x x  ₁ 1.5 x y1      1 1     f 4x ‘条件’の 法線① 法線 0 6 /    L y y  0 ) 1 ( /     L  x y 0 0.5 1 _      y f 6 ‘関数’の 法線② 法線 平行 条件 ・①と②が平行→ 0 ) 1 ( /  L  x y -1 -0.5 0      f  1 法線② 条件 色は深さを表す . ) , (xy const f  -1.5 -1 -0.5 0 0.5 1 1.5 -1.5 1    1 f             4 1  x 色は深さを表す        6 y 1 ) 5 / 2 , 5 / 3 , 5 / 12 ( ) , , ( x y  minf(x,y)6/5 ©2008, Satoshi Suzuki

◆ ラグランジュの未定乗数法

【定理2.9】 制約条件 のもとで、

◆ ラグランジュの未定乗数法

0 ) , , (x₁ x_n  g _ 関数 _{( , , )}が極値をとる点は 1 xn x f _ ) ( ) ( ) (x x f x x g x x F _   _  _ とおくと、次式を満たす ) , , ( ) , , ( ) , , , (x₁ x_n f x₁ x_n g x₁ x_n F _   _  _  F F (2.82) 0 , , , 1 , 0         F n i x F i  ２つの法線が平行 制約条件 ・式(2.82) → n+1個の方程式 → 連立して解が求まる ・定理2 9は必要条件であって 十分条件ではない定理2.9は必要条件であって、十分条件ではない (極値をとるかどうかの判定が必要) ©2008, Satoshi Suzuki

数理計画・第６回

～勾配法による関数の最適化～

(p79 85)

(p79～85)

鈴 木 聡

鈴 木 聡

◆ 最適化問題を解くには

4回目講義と同じなので 書写さなくてもＯＫ ・テイラー展開の1次項で探索方向を決める

◆ 最適化問題を解くには

・その一次項を勾配（グラディエント）と呼ぶ ・今回は具体的に最適化問題を解く方法を説明 ©2008, Satoshi Suzuki