最急降下法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

最急降下法(さいきゅうこうかほう、: Steepest descent method[1]は、関数(ポテンシャル面)の傾き(一階微分)のみから、関数の最小値を探索する勾配法アルゴリズムの一つ。勾配法としては最も単純であり、直接・間接にこのアルゴリズムを使用している場合は多い。

尚、最急降下法の“最急”とは、最も急な方向に降下することを意味している。すなわち、収束の速さに関して言及しているわけではない(より速いアルゴリズムがあり得る)。

手法[編集]

n 次のベクトル x = (x1, x2, ... , xn ) を引数とする関数f (x) としてこの関数の極小値を求めることを考える。

勾配法では反復法を用いてx を解に近づけていく。k 回目の反復で解が x(k) の位置にあるとき、最急降下法では次のようにして値を更新する[1]

\begin{align}\boldsymbol{x}^{(k+1)} &= \boldsymbol{x}^{(k)} - \alpha \operatorname{grad} f(\boldsymbol{x}^{(k)})\\
&= \boldsymbol{x}^{(k)} - \alpha\begin{bmatrix} \dfrac{\partial f(\boldsymbol{x}^{(k)})}{\partial x^{(k)}_1} \\ \dfrac{\partial f(\boldsymbol{x}^{(k)})}{\partial x^{(k)}_2} \\ \vdots \\ \dfrac{\partial f(\boldsymbol{x}^{(k)})}{\partial x^{(k)}_n} \end{bmatrix}
\end{align}

ここでα は1回で更新する数値の割合を決めるパラメータであり、通常は小さな正の定数である。

勾配ベクトル grad f (x)は関数f の変化率が最も大きい方向を向く。したがってαが適当な値ならば、f (x(k+1))は必ずf (x(k))より小さくなる。

最急降下法の流れは以下のようになる[1]

  1. x の初期値 x(0) を決めて、k = 0 とする。
  2. f (x(k))/∂xi(k) = 0 (i = 1 , ... ,n ) であるなら終了する(実際は正確に0になることはないので、十分小さな値になれば終了する)。
  3. 上記の記述に従って x(k) を更新する。
  4. k = k + 1 として 2. に戻る。

特徴[編集]

  • 傾き(一階微分)のみしか見ないので手法として簡便で計算も速い。
  • 勾配法のため、局所的な最小値に捉まり易く、大域的な最小値を求めるのは困難であることが欠点である。それを回避するために、複数の初期値から探索を行うなどの対策が必要である。
  • 関数f の偏微分が計算できなくてはならない。
  • 例えば、y = x2 の最小値の探索において、α > 1 の場合、反復ごとに悪い解へと向かう。解の探索能力、収束速度はαに強く依存しており、αが大きすぎると発散の恐れがあり、小さすぎると収束が遅くなる(緩和法英語版も参照)。そのため、探索の初期では小さめにし、ある程度収束したら大きくする方法もとられる。

参考文献[編集]

  1. ^ a b c 茨木俊秀 ;「最適化の数学 (共立講座 21世紀の数学 13) 」共立出版 (2011/6/23)

関連項目[編集]