勾配を使う計算法

さて, $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})$を計算すると,

$$\begin{eqnarray*} &&l({\bf x}_0 +\Delta {\bf x}) \\ &&=l({\bf x}_0)+\frac{d l}{... ...2 l}{d^2 {\bf x}}({\bf x}_0) \frac{d l}{d {\bf x}}({\bf x}_0)\\ \end{eqnarray*}$$

ここで,任意のベクトル

$${\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)) =\m... ...ilon>0} l({\bf x}_n-\epsilon \frac{d l}{d {\bf x}}({\bf x}_n))$$

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

$$\begin{eqnarray*} &&l({\bf x}_n+\epsilon_n {\bf\eta }_n) =\min_{\epsilon,\epsilo... ... {\bf\eta}_{n+1}:{\bf x}_{n+1}によって決まる何らかの方向ベクトル \end{eqnarray*}$$

を繰り返しながら

$$\{ {\bf x}_n\},\{{\bf\eta }_n \},\{ \epsilon_n \}$$

を生成し,

$$\lim_{n \to \infty } l({\bf x}_n)=min_{{\bf x}}l({\bf x})$$

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