読者です 読者をやめる 読者になる 読者になる

MATHGRAM

主に数学とプログラミング、時々趣味について。

ニュートン法の理論(1変数の場合)

最適化 数学

こんにちはketです。初記事です。

本記事の構成

◇目次

  1. 適用条件と特徴
  2. ニュートン法の理論
  3. アルゴリズム

って感じの流れです。今回は、長くなりすぎてしまうので1変数の場合のみについてまとめたいと思います。n変数の場合に関しては別記事で。

ではさっそく。

※勾配法を知らない場合は勾配法を勉強してからの方がいいと思います!勾配法のまとめページも完成させたらリンク貼ります。

 

ニュートン法の適用条件と特徴

適用できる条件は以下の3つ
  • 1回微分 f'(x) と、2回微分{ \displaystyle f''(x)\ }が計算可能の場合。
  • 目的関数に制約がない場合。
  • 凸関数の場合、もしくは最大値に近い点がわかってる場合。
ニュートン法の特徴は何と言ってもこれ
  • 収束がめっちゃ早い。(2次収束する)

軽くまとめると、

定義域に縛りがない、いっぱい微分できる凸関数 \displaystyle f(x) の最大値(もしくは最小値)を探す時に使えて、すぐ答えが見つかるよ

って感じ。

ニュートン法の理論

ニュートン法が、なぜ収束しやすく、またなぜ二回微分が必要なのか等を数学的に確認していきます。

1変数の場合

 x 軸上の点 \displaystyle \overline{x} の近くの点 \displaystyle \overline{x} + \Delta xでの関数 f(x) の値はテイラー展開して、

 { \displaystyle f( \overline{x} + \Delta x ) = f( \overline{x} ) + f'(\overline{x})\Delta x + \frac{1}{2}f''(\overline{x})\Delta x^2 + \cdots }

のように書けます。

具体的に考えてみましょう。例えばある点 \displaystyle \overline{x} = 2だとします。そしてその近くの点 \displaystyle \overline{x} + \Delta x = 2.1の値を求めるために \Delta x = 0.1とし、テイラー展開を用いて計算しよう(近似しよう)としています。何も難しいことはしていません。

上式の \cdotsの部分は \Delta x3次以上の項であるため \Delta xがとても小さな数の場合、急速に0に近づきます。そこでこれらの項を無視して近似した新たな関数を次のように定めます。

 { \displaystyle f_2( \Delta x ) = f( \overline{x} ) + f'( \overline{x})\Delta x + \frac{1}{2}f''( \overline{x} )\Delta x^2 }

かなりスッキリしましたね。添字の2は2次の項まで近似しましたよ〜っていう意味です。最初の目的関数の代わりに、この2次近似した関数の最大(最小)を求めよう!というのがニュートン法の根幹の考え方になっています。

関数の最大を求めると言ったら、おなじみの微分ですね。 \Delta x \displaystyle f_2( \Delta x ) 微分して値が0になる x を探しましょう。

 \displaystyle f'( \overline{x}) + f''(\overline {x}) \Delta x = 0
 
 \displaystyle \Leftrightarrow \Delta x = -\frac{f'(\overline{x})}{f''(\overline{x})}

 

このように求めた2次近似関数の最大値に移動する、つまりは以下のように

 \displaystyle x ← \overline{x} - \frac{f'(\overline{x})}{f''(\overline{x})}

 xを更新することによって、近似する前の目的関数の最大値に近づくことがことができます。

この近づいた点で、また同じように

2次近似を行い→最大値を求め→ x を更新

を繰り返すことによって徐々に目的関数の最大値に近づくことができます。

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

それではアルゴリズムを確認しましょう。

-------procedure Newton(f'(x),f"(x))-----------------------

  1.  x に初期値を代入する。
  2.  \displaystyle \overline{x} ← x と置き、以下のように x を更新する。

     \displaystyle x ← \overline{x} - \frac{f'(x)}{f''(x)}
  3. ステップ2に戻り、これを \displaystyle |x - \overline{x}| \lt \delta となるまで繰り返す。
  4.  x を返す。

※ここでの \deltaはとても小さな定数ということを意味します。

--------------------------------------------------------------------------------------

 

以上が、ニュートン法の理論とアルゴリズムです。

収束がすごく早いことを意味する2次収束の証明、またpythonでの実装はまた今度。

 

それでは。