11月12日

最適化手法講義資料（平成 26 年度冬学期）
準 Newton 法の概要
連続微分可能な関数 f : Rn → R の無制約最小化問題を考える．簡単のために，記号
fk := f (xk ),
∇fk := ∇f (xk ),
∇2 fk := ∇2 f (xk )
を用いる．
Newton 法では，Newton 方程式
∇2 fk d = −∇fk
(1)
の解として探索方向 dk を定義する．一方，準 Newton 法では，(1) の ∇2 fk を適当な正定値行列 Bk
で近似する．つまり，準 Newton 法における探索方向 dk は，線形方程式
Bk d = −∇fk
(2)
の解として定められる．準 Newton 法の概要は，次の通りである．
アルゴリズム 1 (準 Newton 法のプロトタイプ).
Step 0: 初期点 x0 および B0 ≻ O を選ぶ．十分小さい ϵ > 0 を定め，k = 0 とおく．
Step 1: 停止条件 ∥∇fk ∥ < ϵ が満たされていれば，xk を解として終了．
Step 2: 線形方程式 (2) を解いて探索方向 dk を求める.
Step 3: 直線探索により αk を定める（Wolfe の条件などを用いる）．
Step 4: xk+1 = xk + αk dk と更新する．
Step 5: Bk+1 ≻ O を生成する（後述）．k ← k + 1 とおいて Step 1 へ．
アルゴリズム 1 の Step 5 では，Bk , xk , xk+1 , ∇fk , ∇fk+1 を用いて ∇2 fk+1 の近似行列 Bk+1 を
生成する．簡単のために
sk := xk+1 − xk = αk dk ,
y k := ∇fk+1 − ∇fk ,
ρk :=
1
y⊤
k sk
とおく．Bk+1 を生成する方法として，次の二つの公式がよく知られている：
1. BFGS 公式
Bk+1 = Bk −
Bk sk s⊤
k Bk
+ ρk y k y ⊤
k.
⊤
sk Bk sk
(3)
2. DFP 公式
⊤
⊤
Bk+1 = (I − ρk y k s⊤
k )Bk (I − ρk sk y k ) + ρk y k y k .
1
(4)
(3) や (4) で定められる Bk+1 は，次の性質を満たすことが確認できる：
(a) Bk+1 はセカント条件 Bk+1 sk = y k を満たす．
(b) Bk が対称行列ならば Bk+1 も対称行列である．
(c) Bk ≻ O かつ s⊤
k y k > 0 ならば Bk+1 ≻ O である．
このうち，性質 (c) の仮定に注目する．実は，Step 3 において αk を Wolfe の条件を満たすように
選ぶと，条件 s⊤
k y k > 0 は自動的に満たされる．というのも，まず，sk の定義および Wolfe の条件
⊤ s ≥ c ∇f ⊤ s が得られる．このことと y の定義より
∇f (xk + αk dk )⊤ dk ≥ c2 ∇fk⊤ dk より ∇fk+1
2
k
k
k k
⊤
⊤
⊤
y⊤
k sk = (∇fk+1 − ∇fk ) sk ≥ (c2 − 1)∇fk sk = (c2 − 1)αk ∇fk dk
(5)
が得られる．Bk ≻ O ならば，dk は降下方向である（つまり，∇fk⊤ dk < 0 を満たす）．このことと
c2 < 1 より，(5) の最右辺は正である．従って，s⊤
k y k > 0 が成り立つことが分かる．
Bk の更新公式 (3) や (4) に対して Sherman–Morrison–Woodbury の公式 1 を適用すると，Bk+1 の
−1
逆行列 Hk+1 ≡ Bk+1
を陽に求めることができる．このようにして得られる Hk の更新公式を，H 公
式と呼ぶ．これに対して，(3) および (4) は B 公式と呼ばれることもある．
1. BFGS 公式の H 公式
⊤
⊤
Hk+1 = (I − ρk sk y ⊤
k )Hk (I − ρk y k sk ) + ρk sk sk .
(6)
2. DFP 公式の H 公式
Hk+1 = Hk −
Hk y k y ⊤
k Hk
+ ρk sk s⊤
k.
y k Hk y k
(7)
アルゴリズム 2 (BFGS 公式の H 公式を用いた準 Newton 法).
Step 0: 初期点 x0 および H0 ≻ O を選ぶ．十分小さい ϵ > 0 を定め，k = 0 とおく．
Step 1: 停止条件 ∥∇fk ∥ < ϵ が満たされていれば，xk を解として終了．
Step 2: 探索方向を dk = −Hk ∇fk により求める．
Step 3: 直線探索により Wolfe の条件を満たすように αk を定める．
Step 4: xk+1 = xk +αk dk と更新する．また，sk = xk+1 −xk , y k = ∇fk+1 −∇fk , ρk = 1/y ⊤
k sk
とおく．
Step 5: (6) により Hk+1 を計算する．k ← k + 1 とおいて Step 1 へ．
アルゴリズム 2 では，Step 2 において探索方向 dk は行列にベクトルを乗じることで求められる．
従って，アルゴリズム 2 を実行するには，1 回の反復あたり O(n2 ) の計算で済む．つまり，探索方向
を求めるために (2) のような線形方程式を解く必要がないことが，H 公式の利点である．
(November 12, 2014, 寒野)
ˆ = A + ab⊤ を考える．このとき，Aˆ が正則なら
正則な行列 A ∈ Rn×n およびベクトル a, b ∈ Rn に対して，行列 A
−1
⊤ −1
(A
a)(b
A
)
ˆ−1 = A−1 −
ばA
が成り立つ．
1 + b⊤ A−1 a
1
2

Download Report