Document

主な制約なし問題の解法
min
f ( x)
前回説明済み
最急降下法（steepest descent methods）
ニュートン法（Newton’s method）
準ニュートン法（quasi Newton method）
信頼領域法（trust region methods）
共役勾配法（conjugate gradient methods）
記憶制限付き準ニュートン法（limited
memory quasi Newton methods）
2015/6/12
1
ニュートン法
２次微分（ヘッセ行列）を利用して高速化
~ k
f (x
2
k
d )
k
f (x )
f (x ) d
f ( x k ) : 正定値ならば
~ k
f (x d k ) は d k
2015/6/12
k T
2
k
1 k
d
2
k
f (x )
1
T
2
f ( x k )d k
f ( x k ) で最小となる
2
もう一つの見方(非線形方程式に対する
ニュートン法を適用)
一次の必要条件 f ( x) 0 を非線形方程式とみて線形化
f (xk
2
dk)
k
f (xk )
f ( x ) : 正則ならば d
2015/6/12
2
k
f ( x k )d k
2
0
k
f (x )
1
f ( x k ) となる
3
ニュートン法のアルゴリズム
Step 0 : 初期点 x 0を選び，k : 0とおく
Step 1 : f ( x k ) 0 ならば終了．そうでないとき
f (xk )
2
Step 2 : x k 1 : x k
2
f ( x k ) : 正定値
f ( x k )d k
0 の解d k を求める
d k , k : k 1 としてStep 1へ．
f (xk ) Td k
0 （降下方向）
直線探索による大域化
2015/6/12
4
ニュートン法の特徴
２次収束性：解の近くで，
x
k 1
x
*
x
k
x
* 2
これは非常に速い
ただし，初期点を解の近くにとらねばならない
最急降下法などと組みあわせて用いられる
2015/6/12
5
準ニュートン法
ニュートン法はヘッセ行列が必要
ヘッセ行列を逐次近似
正定値性，対称性を保つ
ＤＦＰ法，ＢＦＧＳ法
2015/6/12
6
ＢＦＧＳ法のアルゴリズム
Step 0 : 初期点 x 0と初期行列 B 0を選び，k : 0とおく
Step 1 : f ( x k ) 0 ならば終了．そうでないとき
d
k
B
Step 2 : f ( x k
k
f ( x k ) とおく y k x k 1 x k
k k
k
d ) min f ( x k k d k ) なる
k 1 を求め，
k
1
s
0
xk 1 : xk
Step 3 : B k
1
Bk
k
f (x
)
f (x )
d k とする
k
y y
y
k T
k T
s
k k
B s s
k
s
k T
k T
Bk
Bk sk
k : k 1 として Step 1へ
2015/6/12
7
準ニュートン法の特徴
大域的収束性（降下方向+直線探索）
超１次収束性
lim
k
2015/6/12
x
k 1
x
k
x
x
*
*
0
かなり速い
8
計算例
f ( x) ( x1 1) 2 10( x12
2015/6/12
x2 ) 2
9
結果
1.5
steepst descent
newton
qnewton
1
0.5
0
-0.5
-0.5
2015/6/12
0
0.5
1
1.5
10
解との距離をプロット
steepst descent
newton
qnewton
1
0.01
0.0001
1e-06
1e-08
1e-10
1e-12
1e-14
0
5
10
15
20
25
30
35
40
45
50
Iterations
2015/6/12
11
共役勾配法
正定値対称行列を係数に持つ連立一次方程式
Ax b, A R n n , x R n , b R n
x*
v
を解くための解法
min f ( x)
1 T
x Ax bT x
2
u
A PT P
この最小化問題を解くことと同値
特徴：前回の探索方向と共役な方向に探索
初期点 x0
2015/6/12
P
P
1
Px*
Pv
Pu
R n とした時，高々n回の反復で最小解が得られる
12
共役勾配法のアルゴリズム
Step 0
Step 1
Step 2
Step 3
Step 4
Step 5
Step 6
2015/6/12
初期点
を与える．初期探索方向
を最急降下方向とし，k = 0 とする
（厳密な）直線探索を行い，ステップ幅
=
+
とおく
停止条件が満たされていれば
そうでなければStep 4へ．
パラメータ
=−
k 1
を求める
を計算する
+
k = k + 1 とおいてStep 1へ
を解とみなして停止する．
f
k 1
2
k 1
x
f x
k
2
Fletcher-Reevesの公式
1回前の勾配情報と
探索方向の保存で適用可能
13
共役勾配法の特徴
凸二次関数
=
−
に対しては
理論上n回の反復で終了
数値誤差に弱い→反復法，リスタート
βの決め方はいろいろ提案されている（凸二
次計画の場合は全て同じ）
超大規模（変数が1000以上）な問題では
（準）ニュートン法などよりも有効なことがある
2015/6/12
14
信頼領域法(Trust region
method)
直線探索のかわりに2次モデルの近似が妥
当と思われる範囲（信頼領域）で最小化
大域的収束性かつ二次収束
狭い（近似が悪い）
2015/6/12
広い（近似が良い）
15
反復では以下の部分問題を解く
min
s.t.
または
=
≤∆
s.t.
≤∆
min
=
この解を
+
+
1
+
2
としたとき，近似度を計算
=
2015/6/12
+
− ( + )
0 − ( )
16
信頼領域法のアルゴリズム
Step 0 : 定数0
1
2
1, 0
1
1
を選ぶ．
2
初期点 x 0と初期半径 0を選び，k : 0とおく
Step 1 : 部分問題の解 d kと近似度rkを計算
Step 2 : rk
k 1
k
ならば
x
:
x
1
dk ，
そうでなければx k 1 : x kとする
Step 3 : rk
2
k 1
2 k
1
rk
2015/6/12
rk
2
1
k 1
k 1
1
k
k
k : k 1として Step 1へ
17
信頼領域法の収束性
大域的収束
=
かつ収束した点において二
次の十分条件が成り立てば二次収束
2015/6/12
18
演習問題
2変数関数
,
=
−
+3
+2
−4
+1
に初期点 0,0 から共役勾配法を適用したとき
の最初の2反復を求めよ．
（一回目は最急降下方向，二回目で最小解に
到達します．）
2015/6/12
19

Download Report