全文

(1)

制約なし問題の解法

 最急降下法( steepest descent methods )

 ニュートン法( Newton’s method )

 準ニュートン法( quasi Newton method )

 共役勾配法( conjugate gradient methods )

 記憶制限付き準ニュートン法( limited

) (

min f x

(2)

最急降下法

勾配(ベクトル)は,関数値が最も増加する方向

どこまで進めばよいか? → 直線探索で決める

値は減少 の方向へ進めば,関数

)

( x

f

d  

(3)

x

k

) (xk f d 

直線探索のイメージ

x k x k   d

)

( x d

f k  

d x k

このような範囲 をみつける

(4)

直線探索のいろいろ

 厳密な直線探索( exact line search ) 最急降下法などで用いられる

 アルミホ( Armijo) ルール

を満たす最小の非負整数 を求める ニュートン法などで用いられる

( )min( )

min )

( x d 0 f x d 0 1 f x d

f   

  

  または  

d x

f x

f d

x

f (  2 i )  ( )  0 . 001  2 i  ( ) T

i

直線探索も反復法であることに注意

詳しくはまたあとで

(5)

最急降下法のアルゴリズム

 

へ.

として

を求め,

なる とおく

いとき ならば終了.そうでな

とおく を選び,

初期点

1 Step 1

: , :

) (

min )

( : 2 Step

) (

0 )

( :

1 Step

0 : :

0 Step

1

0 0



k k

d x

x

d x

f d

x f

x f d

x f

k x

k k k

k

k k

k k

k k

k k

k

 

(6)

x 0

x 1

x 2

x 3

最急降下法のイメージ

(7)

 最も基本的な方法

 最急降下法は大域的収束 停留点に必ず収束

大域的最小解に収束するとは限らない

 収束は遅い(高々一次収束率,計算例はあと で)

 ニュートン法などの補助として使うことが多い

(8)

主な制約なし問題の解法

 最急降下法( steepest descent methods )

 ニュートン法( Newton’s method )

 準ニュートン法( quasi Newton method )

 信頼領域法( trust region methods )

 共役勾配法( conjugate gradient methods )

 記憶制限付き準ニュートン法( limited memory quasi Newton methods )

) (

min f x 前半で説明した

(9)

ニュートン法

 2次微分(ヘッセ行列)を利用して高速化

 

 

で最小となる

正定値ならば

) (

) (

)

~ (

: ) (

) 2 (

) 1 (

) (

)

~ (

2 1 2

T 2 T

k k

k k

k k

k k

k k

k k

k k

x f x

f d

d x

f x f

d x

f d

d x

f x

f d

x f

(10)

 もう一つの見方 ( 非線形方程式に対する ニュートン法を適用 )

 

となる

正則ならば

線形化 を非線形方程式とみて

一次の必要条件

) (

) (

: ) (

0 )

( )

( )

(

0 )

(

2 1 2

2

k k

k k

k k

k k

k

x f x

f d

x f

d x

f x

f d

x f

x f

(11)

ニュートン法のアルゴリズム

へ.

として

を求める の解

いとき ならば終了.そうでな

とおく を選び,

初期点

1 Step 1

: , :

: 2 Step

0 )

( )

(

0 )

( :

1 Step

0 : :

0 Step

1

2 0

 x d k k

x

d d

x f x

f x f

k x

k k

k

k k

k k

k

直線探索による大域化

(降下方向)

正定値

2 f ( x k ) : f ( x k ) T d k 0

(12)

ニュートン法の特徴

 2次収束性:解の近くで,

これは非常に速い

 ただし,初期点を解の近くにとらねばならない

 最急降下法などと組みあわせて用いられる

* 2

*

1 x x x

x k    k

(13)

準ニュートン法

 ニュートン法はヘッセ行列が必要

 ヘッセ行列を逐次近似

 正定値性,対称性を保つ

 DFP法,BFGS法

(14)

BFGS法のアルゴリズム

   

     

 

として

とする

を求め,

なる とおく

いとき ならば終了.そうでな

とおく を選び,

と初期行列 初期点

1 Step 1

: : 3 Step

:

) (

min )

( : 2 Step

) (

0 )

( :

1 Step

0 : :

0 Step

T

T T

T 1

1

0 1

0 0

k k

s B s

B s

s B s

y y B y

B

d x

x

d x

f d

x f

x f B

d

x f

k B

x

k k k

k k

k k k

k k k k

k

k k k

k

k k

k k

k k

k k

k

k

  ( 1 ) ( )

1

k k

k

k k

k

x f x

f s

x x

y

(15)

準ニュートン法の特徴

 大域的収束性(降下方向 + 直線探索)

 超1次収束性

かなり速い

0

lim *

* 1

 

 

 x x

x x

k

k

k

(16)

計算例

2 2 2

1 2

1 1 ) 10 ( )

( )

( x x x x

f    

(17)

0 0.5 1

1.5 steepst descent

newton qnewton

結果

(18)

解との距離をプロット

1e-14 1e-12 1e-10 1e-08 1e-06 0.0001 0.01 1

0 5 10 15 20 25 30 35 40 45 50

Iterations

steepst descent newton qnewton

(19)

共役勾配法

n n

n

n

x R b R

R A b

Ax  , 

,  , 

正定値対称行列を係数に持つ連立一次方程式

を解くための解法

x b Ax x

x

f 

T

T

2 ) 1 ( min

この最小化問題を解くことと同値

特徴:前回の探索方向と共役な方向に探索

R

n

x

0

初期点 とした時,高々

n

回の反復で最小解が得られる

u

v

P P

A 

T

P P

1

x

*

Px

*

 Pu

Pv

(20)

共役勾配法のアルゴリズム

Step 0 Step 1 Step 2 Step 3

Step 4 Step 5 Step 6

初期点 を与える.初期探索方向 を最急降下方向とし,

k = 0

とする

(厳密な)直線探索を行い,ステップ幅 を求める

=

とおく

停止条件が満たされていれば を解とみなして停止する.

そうでなければ

Step 4

へ.

パラメータ を計算する

k = k + 1

とおいて

Step 1

   

2

1 2

1

x

x

k k

k

f

f

 

Fletcher-Reeves

の公式

1

回前の勾配情報と

探索方向の保存で適用可能

1

k

(21)

共役勾配法の特徴

 凸二次関数 に対しては

理論上 n 回の反復で終了

 数値誤差に弱い → 反復法,リスタート

 β の決め方はいろいろ提案されている(凸二 次計画の場合は全て同じ)

 超大規模(変数が 1000 以上)な問題では

(準)ニュートン法などよりも有効なことがある

(22)

信頼領域法 (Trust region method)

 直線探索のかわりに 2 次モデルの近似が妥 当と思われる範囲(信頼領域)で最小化

 大域的収束性かつ二次収束

狭い(近似が悪い) 広い(近似が良い)

(23)

 反復 では以下の部分問題を解く

または

 この解を としたとき,近似度 を計算

(24)

信頼領域法のアルゴリズム

へ として

とする そうでなければ

, ならば

を計算 と近似度

部分問題の解

とおく を選び,

と初期半径 初期点

を選ぶ.

定数

1 Step 1

: : 3 Step

: : :

2 Step

: 1 Step

0 :

1 0

, 1 0

: 0 Step

1 1

1

1 2

1

2 1

2

1 1 1

0 0

2 1

2 1

k k

r

r r

x x

d x

x r

r d

k x

k k

k

k k

k

k k

k

k k

k k

k k

k k

(25)

信頼領域法の収束性

 大域的収束

 かつ収束した点において二

次の十分条件が成り立てば二次収束

(26)

演習問題

2 変数関数

に初期点 から共役勾配法を適用したとき の最初の 2 反復を求めよ.

(一回目は最急降下方向,二回目で最小解に 到達します.)

締切: 6 月 28 日 ( 木 )16 時 Ⅳ系事務室まで

Updating...

参照

Updating...

関連した話題 :