Processing math: 69%

勾配法

提供: Internet Web School

UNIQ3d99028d200af4d4-MathJax-2-QINU2 による版

一次アルゴリズム

l(x,y)=x+y+x2+y2 を例にとる.l(x,y)を列ベクトルと行列

p=(11),x=(xy),Q=(1001)

を使って表現すると

l(x,y)=(1,1)(xy)+(x,y)(1001)(xy)

から l(x)=pTx+xTQx と書ける.


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

lx(x,y)=1+xly(x,y)=1+y

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

dldx(x)=(lx(x,y)ly(x,y))=p+2Qx

である。

また,l(x)の2階微分は

d2ldx2(x)=Q である。

Δx=(ΔxΔy) とすると

l(x+Δx)=pT(x+Δx)+(x+Δx)TQ(x+Δx)=pTx+xTQx+pTΔx)+2xTQΔx+12ΔxTQΔx=l(x)+dldx(x)TΔx+12ΔxTd2ldx2(x)Δx

である.


関数l(x)が解析的な関数なら,

l(x+Δx)=l(x)+dldx(x)TΔx+12ΔxTd2ldx2(x)Δx+o(Δx)

となる.o(Δx)は3次以上の高位の項である。

勾配を使う計算法

l(x)=l(x,y)を最小化するため先ず,

初期点   x0=(x0y0) を与えて,l(x0)を求め,次に,

x=x0でのl(x)の微分,

dldx(x0)=p+Qx0

を求め,これと微小な正数ϵ>0を使って,

Δx=ϵdldx(x0)

として,l(x0+Δx)を計算すると,

l(x0+Δx)=l(x0)+dldx(x0)TΔx+12ΔxTd2ldx2(x0)Δx=l(x0)ϵdldx(x0)Tdldx(x0)+ϵ2dldx(x0)Td2ld2x(x0)dldx(x0)

ここで,任意のベクトル z=(pq) について

zTz=p2+q2 であるからzTz0である。

同様に,

dldx(x0)Tdldx(x0)0

dldx(x0)TQdldx(x0)0

である。

0<ϵが十分小さければ, Δx=ϵdldx(x0) として, l(x0+Δx)<l(x0) となる.

x1=x0+Δx を新たな初期点としてこれを繰り返すことができる.このような方法を勾配法と呼ばれる.


特に,毎回の繰り返しで,

l(xnϵndldx(xn))=min

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

l({\bf x}_n+\epsilon_n {\bf \eta }_n) =\min_{\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_{\bf x} l({\bf x})

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

2次アルゴリズム

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}についての2次式である。この式が{\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) を繰り返すアルゴリズムはニュートン法と呼ばれる.

個人用ツール