最急降下法

出典: フリー百科事典『ウィキペディア(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 と初期化しておく。実際には x を記憶する領域は 1 つで充分なので、単純に最急降下法のみを行う場合には必要ない)。
  2. f (x(k))/xi(k) = 0 (i = 1, ... , n) であるなら終了する(実際は正確に 0 になることはないので、十分小さな値になれば終了する)。
  3. 上記の記述に従って x(k) を更新する。
  4. 2 に戻る(必要なら k の値を 1 つ進める)。

特徴[編集]

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

出典[編集]

参考文献[編集]

  • 茨木, 俊秀 『最適化の数学』 共立出版〈共立講座 21世紀の数学 13〉、2011年6月23日

関連項目[編集]