勾配法

提供: Internet Web School

---

2020年11月25日 (水) 05:42時点における版

１次アルゴリズム

関数の勾配 \( 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) \) を繰り返すアルゴリズムはニュートン法と呼ばれる．