11月5日

最適化手法講義資料（平成 26 年度冬学期）
直線探索による降下法の大域的収束性
（☆試験の範囲外☆）
関数 f : Rn → R の無制約最小化問題を考える．更新公式
xk+1 = xk + αk dk
(1)
に基づく反復法を用いる．Wolfe の条件に基づく直線探索を用いたとき，任意の初期点 x0 に対して
(1) により生成される点列 {xk } が f の停留点に収束するための条件を考える．
以下では，探索方向 dk が降下方向であること，即ち
∇fk⊤ dk < 0
を満たすことをを仮定する．また，dk と最急降下方向 −∇fk のなす角度を θk とおく．つまり，θk を
cos θk =
−∇fk⊤ dk
∥∇fk ∥∥dk ∥
(2)
で定義する．定数 c1 ∈ (0, 1), c2 ∈ (c1 , 1) を選ぶと，ステップ幅 αk に対する Wolfe の条件は
f (xk + αk dk ) ≤ fk + c1 αk ∇fk⊤ dk ,
(3)
∇f (xk + αk dk )⊤ dk ≥ c2 ∇fk⊤ dk ,
(4)
である．
• 次の命題 1 は，工学教程『最適化と変分法』の命題 2.4 である．
命題 1 (Zoutendijk). 探索方向 dk が降下方向であり，ステップ幅 αk が Wolfe の条件を満たすことを
仮定する．f : Rn → R のレベル集合 L = {x | f (x0 ) ≥ f (x)} を含む開集合を N とおく．f が下に
有界であり，N において連続微分可能であることを仮定する．さらに，∇f は N 上でリプシッツ連
続であること，つまり
∥∇f (x) − ∇f (x′ )∥ ≤ L∥x − x′ ∥,
∀x, x′ ∈ N
を満たす定数 L > 0 が存在することを仮定する．このとき，
∞
∑
cos2 θk ∥∇fk ∥2 < ∞
(5)
k=0
が成り立つ．
証明. 更新公式 (1) と Wolfe の条件の (4) より
⊤
∇fk+1
dk ≥ c2 ∇fk⊤ dk
が得られる．両辺に −∇fk⊤ dk > 0 を加えると
(∇fk+1 − ∇fk )⊤ dk ≥ (c2 − 1)∇fk⊤ dk
1
(6)
が得られる．一方，∇f がリプシッツ連続であることより
(∇fk+1 − ∇fk )⊤ dk ≤ ∥∇fk+1 − ∇fk ∥∥dk ∥ ≤ αk L∥dk ∥2
(7)
が成り立つ．(6) と (7) より
αk ≥
c2 − 1 ∇fk⊤ dk
L ∥dk ∥2
(8)
が成り立つ．Wolfe の条件の (3) に (8) を代入すると，
fk+1 ≤ fk + c1
c2 − 1 (∇fk⊤ dk )2
L
∥dk ∥2
(9)
が得られる．θk の定義 (2) を用いると，(9) は
1 − c2
(10)
L
と書き直せる．(10) を 0 から k ステップまで足し合わせることで不等式 fk+1 ≤ f0 −
∑
c kj=0 cos2 θj ∥∇fj ∥2 が得られる．これは次のように書き直せる：
fk+1 ≤ fk − c cos2 θk ∥∇fk ∥2 ,
c
k
∑
c = c1
cos2 θj ∥∇fj ∥2 ≤ f0 − fk+1 .
(11)
j=0
(11) の左辺は非負である．また，右辺において f は下に有界であるから，任意の k に対
して f0 − fk+1 < γ を満たす正の定数 γ が存在する．従って，(5) が成り立つ．
Zoutendijk の条件 (5) は
cos2 θk ∥∇fk ∥2 → 0
(12)
を意味している．いま，最急降下法を用いることを考え，θk が 90◦ から十分に遠いことを仮定する
と，cos θk ≥ δ > 0 (∀k) を満たす定数 δ > 0 が存在する．従って，(12) より lim ∥∇fk ∥ = 0 が得ら
れる．これは，直線探索付き最急降下法の大域的収束性を表している．
k→∞
一方，Newton 法や準 Newoton 法において，探索方向 dk が Bk dk = −∇fk で定義される場合を考
える．Bk が正定値であり，ある定数 M > 0 に対して
∥Bk ∥∥Bk−1 ∥ ≤ M,
∀k
(13)
を満たすことを仮定する．∥Bk ∥∥Bk−1 ∥ を Bk の条件数と呼ぶ．任意の正則行列 A が ∥Ax∥ ≥ ∥x∥/∥A−1 ∥
および ∥A∥∥x∥ ≥ ∥Ax∥ を満たすことを用いると，
∥Bk dk ∥2
−∇fk⊤ dk
d⊤
k Bk dk
=
=
cos θk =
∥∇fk ∥∥dk ∥
∥Bk dk ∥∥dk ∥
∥Bk dk ∥∥dk ∥
1/2
−1/2
≥
(∥dk ∥/∥Bk ∥)2
∥dk ∥
1
=
≥
≥ 1/M
−1
∥Bk dk ∥∥dk ∥
∥Bk dk ∥∥Bk ∥
∥Bk ∥∥Bk−1 ∥
(14)
が得られる．(5) と (14) より lim ∥∇fk ∥ = 0 が成り立つ．従って，
（準）Newton 法において，Bk が
k→∞
正定値でかつ (13) を満たし，ステップ幅が Wolfe の条件を満たすならば，大域的収束性が保証される．
参考
[1] Nocedal, J., Wright, S.J.: Numerical Optimization (2nd ed.). Springer, New York (2006).
(November 5, 2014, 寒野)
2

Download Report