勾配法

提供: Internet Web School

１次アルゴリズム

関数の勾配 \( l(x,y)=x+y+x^2+y^2 \) を例にとって説明します。\(l(x,y)\)を 列ベクトルと行列

\( {\bf p} =\left ( \begin{array}{c} 1\\ 1\\ \end{array} \right ), {\bf x} =\left ( \begin{array}{c} x\\ y\\ \end{array} \right ), {\bf Q}= \left ( \begin{array}{cc} 1&0\\ 0&1\\ \end{array} \right ) \)

を使って表現すると

\( l(x,y) =(1,1) \left ( \begin{array}{c} x\\ y\\ \end{array} \right ) + (x,y) \left ( \begin{array}{cc} 1&0\\ 0&1\\ \end{array} \right ) \left ( \begin{array}{c} x\\ y\\ \end{array} \right ) \)

から

\( l({\bf x}) ={\bf p}^T {\bf x} + {\bf x}^T {\bf Q}{\bf x} \)

と書ける．

ここで,\(l(x,y)\)の\(x,y\)についての偏微分係数はそれぞれ,

\( \frac{\partial l}{\partial x}(x,y)=1+x \\ \frac{\partial l}{\partial y}(x,y)=1+y \)

である。これらを要素にもつ列ベクトルは, \(l({\bf x})=l(x,y)\)の\({\bf x}\)について の微分であり,

\( \frac{d l}{d {\bf x}}({\bf x}) =\left ( \begin{array}{c} \frac{\partial l}{\partial x}(x,y)\\ \frac{\partial l}{\partial y}(x,y)\\ \end{array} \right ) ={\bf p}+ 2 {\bf Q} {\bf x} \)

である。 また,\(l({\bf x})\)の２階微分は

\( \frac{d^2 l}{d {\bf x}^2}({\bf x})= {\bf Q} \)

である。

\( \Delta {\bf x}= \left ( \begin{array}{c} \Delta x\\ \Delta y\\ \end{array} \right ) \)

として,

\( l({\bf x} +\Delta {\bf x}) \\ ={\bf p}^T ( {\bf x} +\Delta {\bf x}) + ({\bf x}+\Delta {\bf x})^T {\bf Q}({\bf x}+\Delta {\bf x}) \\ ={\bf p}^T {\bf x} +{\bf x}^T {\bf Q} {\bf x} +{\bf p}^T \Delta {\bf x}) +2{\bf x}^T {\bf Q} \Delta {\bf x} +\frac{1}{2} \Delta {\bf x}^T {\bf Q} \Delta {\bf x} \\ =l({\bf x})+\frac{d l}{d {\bf x}}({\bf x})^T\Delta {\bf x} +\frac{1}{2} \Delta {\bf x}^T \frac{d^2 l}{d {\bf x}^2}({\bf x}) \Delta {\bf x} \)

結局,

\( l({\bf x} +\Delta {\bf x}) =l({\bf x})+\frac{d l}{d {\bf x}}({\bf x})^T\Delta {\bf x} +\frac{1}{2} \Delta {\bf x}^T \frac{d^2 l}{d {\bf x}^2}({\bf x}) \Delta {\bf x} \)

となる．

無論,一般の関数\(l({\bf x})<math>,解析的な関数なら, <math> l({\bf x} +\Delta {\bf x}) =l({\bf x})+\frac{d l}{d {\bf x}}({\bf x})^T\Delta {\bf x} +\frac{1}{2} \Delta {\bf x}^T \frac{d^2 l}{d {\bf x}^2}({\bf x}) \Delta {\bf x} +{\bf o}(\Delta {\bf x}) \) となる．\({\bf o}(\Delta {\bf x})<math>は３次以上の高位の項である。 勾配を使う計算法 <math>l({\bf x})=l(x,y)\)を最小化するため,先ず,

初期点 \( {\bf x}_0= \left ( \begin{array}{c} x_0\\ y_0\\ \end{array} \right ) \)

を与えて,\(l({\bf x}_0)\)を求め,次に,

\({\bf x}={\bf x}_0\)での\(l({\bf x})\)の微分,

\( \frac{d l}{d {\bf x}}({\bf x}_0) = {\bf p}+ {\bf Q}{\bf x}_0 \)

を求め,これと微小な正数\(\epsilon >0\)を使って,

\( \Delta {\bf x} = -\epsilon \frac{d l}{d {\bf x}}({\bf x}_0) \)

として,\(l({\bf x}_0 +\Delta {\bf x})\)を計算すると,

\( l({\bf x}_0 +\Delta {\bf x}) \\ =l({\bf x}_0)+\frac{d l}{d {\bf x}}({\bf x}_0)^T\Delta {\bf x} +\frac{1}{2} \Delta {\bf x}^T \frac{d^2 l}{d {\bf x}^2}({\bf x}_0) \Delta {\bf x} \\ =l({\bf x}_0) -\epsilon \frac{d l}{d {\bf x}}({\bf x}_0) ^T \frac{d l}{d {\bf x}}({\bf x}_0) +\epsilon^2 \frac{d l}{d {\bf x}}({\bf x}_0)^T \frac{d^2 l}{d^2 {\bf x}}({\bf x}_0) \frac{d l}{d {\bf x}}({\bf x}_0)\\ \)

ここで,任意のベクトル

\( {\bf z} =\left ( \begin{array}{c} p\\ q\\ \end{array} \right ) \)

について

\( {\bf z}^T{\bf z}=p^2+q^2 \) である,\({\bf z}^T{\bf z} \ge 0\)である。同様に, \( \frac{d l}{d {\bf x}}({\bf x}_0) ^T \frac{d l}{d {\bf x}}({\bf x}_0) \ge 0 \)

\( \frac{d l}{d {\bf x}}({\bf x}_0)^T {\bf Q} \frac{d l}{d {\bf x}}({\bf x}_0) \ge 0 \)

である。

\(\epsilon\)が十分小さければ,

\( \Delta {\bf x} = -\epsilon \frac{d l}{d {\bf x}}({\bf x}_0) \)

として,

\(l({\bf x}_0 +\Delta {\bf x}) < l({\bf x}_0)\) となる．

\( {\bf x}_1 ={\bf x}_0 +\Delta {\bf x} \) を新たな初期点としてこれを繰り返すことができる．このような方法を勾配法と呼ばれる．特に,毎回の繰り返しで,

\( l({\bf x}_n-\epsilon_n \frac{d l}{d {\bf x}}({\bf x}_n)) =\min_{\epsilon,\epsilon>0} l({\bf x}_n-\epsilon \frac{d l}{d {\bf x}}({\bf x}_n)) \)

となるように,\(\epsilon_n\)を選ぶ繰り返し計算法を最急降下法と呼ぶ．

\( l({\bf x}_n+\epsilon_n {\bf \eta }_n) =\min_{\epsilon,\epsilon>0} l({\bf x}_n+\epsilon {\bf \eta }_n)\\ {\bf x}_{n+1}={\bf x}_n+\epsilon_n {\bf \eta }_n \\ {\bf \eta}_{n+1}:{\bf x}_{n+1}によって決まる何らかの方向ベクトル \)

を繰り返しながら

\( \{ {\bf x}_n\},\{{\bf \eta }_n \},\{ \epsilon_n \} \)

を生成し, \( \lim_{n \to \infty } l({\bf x}_n)=min_[[:Template:\bf x]]l({\bf x}) \)

とする計算法は,一次アルゴリズムと呼ばれている． ２次アルゴリズム

\( l({\bf x} +\Delta {\bf x}) =l({\bf x})+\frac{d l}{d {\bf x}}({\bf x})^T\Delta {\bf x} +\frac{1}{2} \Delta {\bf x}^T \frac{d^2 l}{d {\bf x}^2}({\bf x}) \Delta {\bf x} \)

を使って,高速なアルゴリズムを造る．

\( \Delta {\bf x}={\bf y}-{\bf x} \)

とおき,上の式の右辺を書き換える．

\( l({\bf x})+\frac{d l}{d {\bf x}}({\bf x})^T({\bf y}-{\bf x}) +\frac{1}{2} ({\bf y}-{\bf x})^T \frac{d^2 l}{d {\bf x}^2}({\bf x}) ({\bf y}-{\bf x}) \)

これは\({\bf y}\)についての２次式である。この式が\({\bf y}\)について,極小になるための 条件は,極値条件(\({\bf y}\)についての微分が{\bf 0}ベクトル)

\( \frac{d l}{d {\bf x}}({\bf x})+\frac{d^2 l}{d {\bf x}^2}({\bf x}) {\bf y}={\bf 0} \)

である。これから,行列

\( \frac{d^2 l}{d {\bf x}^2}({\bf x}) \)

が正則(逆行列をもつ)とすれば,

\( {\bf y}=-(\frac{d^2 l}{d {\bf x}^2}({\bf x}))^{-1}\frac{d l}{d {\bf x}}({\bf x}) \)

が得られる．

\( {\bf x}_{k+1}=-(\frac{d^2 l}{d {\bf x}^2}({\bf x}_k))^{-1} \frac{d l}{d {\bf x}}({\bf x}_k) \) を繰り返すアルゴリズムはニュートン法と呼ばれる．