11月19日

最適化手法講義資料（平成 26 年度冬学期）
準 Newton 法の超 1 次収束性
（☆証明は試験の範囲外☆）
関数 f : Rn → R の無制約最小化問題を，準 Newton 法で解くことを考える．∇2 fk の近似行列 Bk
を用いて探索方向 dk を
Bk dk = −∇fk
(1)
xk+1 = xk + αk dk
(2)
で定義し，更新公式
に従って点列 {xk } を生成する．最適解の十分近くにおいて，ステップ幅 αk = 1 が採用されること
が期待される．このとき，条件
∥(Bk − ∇2 f (x∗ ))dk ∥
=0
k→∞
∥dk ∥
lim
(3)
は準 Newton 法が局所的に超 1 次収束することの必要十分条件であり，Dennis–Mor´e の条件とよばれ
ている．
• 次の命題 1 は，工学教程『最適化と変分法』の命題 2.6 である．
命題 1. f : Rn → R は連続微分可能とする．(1) と (2) により解を更新する準 Newton 法において，
αk = 1 が採用されると仮定する．このときに生成される点列 {xk } が ∇f (x∗ ) = 0 を満たす点 x∗ に
収束することを仮定する．さらに，∇2 f (x∗ ) が正則であり，∇2 f (x) が x = x∗ で連続であることを
仮定する．このとき，{xk } が x∗ に超 1 次収束することの必要十分条件は，Bk が (3) を満たすこと
である．
証明. (1) より，
(Bk − ∇2 f (x∗ ))dk = −∇fk − ∇2 f (x∗ )dk
(4)
が成り立つ．まず，条件 (3) が成立することを仮定する．∇f のテイラー展開より，
∇fk+1 = ∇fk + ∇2 fk dk + O(∥dk ∥2 )
(5)
が得られる．∇2 f の連続性より ∇2 fk → ∇2 f (x∗ ) を用いると，次式が得られる．
∥ − ∇fk − ∇2 f (x∗ )dk ∥
∥∇fk+1 ∥
= lim
k→∞
k→∞
∥dk ∥
∥dk ∥
∥(Bk − ∇2 f (x∗ ))dk ∥
= lim
k→∞
∥dk ∥
lim
((5) より)
((4) より)
((3) より)
= 0.
(6)
次に，∇f (x∗ ) = 0 に注意すると，∇f のテイラー展開より
∇fk+1 = ∇fk+1 − ∇f (x∗ ) = ∇2 f (x∗ )(xk+1 − x∗ ) + O(∥xk+1 − x∗ ∥2 )
1
(7)
が得られる．命題の仮定より ∇2 f (x∗ ) は正則だから，条件
∥∇fk+1 ∥ ≥ β∥xk+1 − x∗ ∥
(8)
を満たす定数 β > 0 が存在する 1 ．(8) と三角不等式より，
∥∇fk+1 ∥
∥∇fk+1 ∥
β∥xk+1 − x∗ ∥
=
≥
∥dk ∥
∥xk+1 − xk ∥
∥xk+1 − x∗ ∥ + ∥xk − x∗ ∥
(9)
が得られる．簡単のために
ρk =
∥xk+1 − x∗ ∥
∥xk − x∗ ∥
とおくと，(6) と (9) より
∥∇fk+1 ∥
ρk
≥ lim β
=0
k→∞ ∥xk+1 − xk ∥
k→∞ 1 + ρk
lim
が得られる．即ち ρk は 0 に収束するので，{xk } は x∗ に超 1 次収束する．
逆に，{xk } が x∗ に超１次収束することを仮定する．超 1 次収束の定義と三角不等式より
∥xk+1 − xk ∥ − ∥xk − x∗ ∥ ∥xk+1 − x∗ ∥
∥xk+1 − xk ∥
≤
→0
∥xk − x∗ ∥ − 1 = ∥xk − x∗ ∥
∥xk − x∗ ∥
が得られるので，
lim
k→∞
∥xk+1 − xk ∥
=1
∥xk − x∗ ∥
(10)
が成り立つ．∇f (x∗ ) = 0 を用いると
∥∇fk+1 ∥
∥∇fk+1 ∥
∥∇fk+1 − ∇f (x∗ )∥ ∥xk − x∗ ∥
=
=
∥dk ∥
∥xk+1 − xk ∥
∥xk − x∗ ∥
∥xk+1 − xk ∥
(11)
が得られる．(7) と (10) を用いると，(11) より
∥∇fk+1 ∥
∥∇2 f (x∗ )∥∥xk+1 − x∗ ∥
= lim
=0
k→∞
k→∞
∥dk ∥
∥xk − x∗ ∥
lim
が得られる．そこで (4) を用いると，(6) と同様にして (3) が得られる．
Dennis–Mor´e の条件 (3) は，Bk が探索方向に沿ってみればヘシアン ∇2 f (x∗ ) の良い近似になって
いることを要求しているのであり，Bk が ∇2 f (x∗ ) そのものに収束することを要求しているのではな
いことがポイントである．
(November 19, 2014, 寒野)
1
一般に，正則な行列 B に対して ∥Bx∥ ≥
x∗ )∥ ≥
∥xk+1 − x∗ ∥
が得られる．
∥∇2 f (x∗ )−1 ∥
∥x∥
が成り立つ．これを (7) に適用すると，∥∇fk+1 ∥ = ∥∇2 f (x∗ )(xk+1 −
∥B −1 ∥
2

Download Report