勾配法
提供: Internet Web School
1 行: | 1 行: | ||
- | |||
==一次アルゴリズム== | ==一次アルゴリズム== | ||
<math> | <math> | ||
230 行: | 229 行: | ||
<math> | <math> | ||
l({\bf x}_n+\epsilon_n {\bf \eta }_n) | l({\bf x}_n+\epsilon_n {\bf \eta }_n) | ||
- | =\min_{ | + | =\min_{\epsilon>0} l({\bf x}_n+\epsilon {\bf \eta }_n)\\ |
{\bf x}_{n+1}={\bf x}_n+\epsilon_n {\bf \eta }_n \\ | {\bf x}_{n+1}={\bf x}_n+\epsilon_n {\bf \eta }_n \\ | ||
{\bf \eta}_{n+1}:{\bf x}_{n+1}によって決まる何らかの方向ベクトル | {\bf \eta}_{n+1}:{\bf x}_{n+1}によって決まる何らかの方向ベクトル |
2020年11月25日 (水) 10:35時点における版
一次アルゴリズム
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についての偏微分係数はそれぞれ,
∂l∂x(x,y)=1+x∂l∂y(x,y)=1+y
である。これらを要素にもつ列ベクトルは, l(x)=l(x,y)のxについて の微分であり,
dldx(x)=(∂l∂x(x,y)∂l∂y(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 であるからzTz≥0である。
同様に,
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) を繰り返すアルゴリズムはニュートン法と呼ばれる.