最急降下法

最急降下法（さいきゅうこうかほう、テンプレート:Lang-en-short）は、関数（ポテンシャル面）の傾き（一階微分）のみから、関数の最小値を探索する勾配法のアルゴリズムの一つ。勾配法としては最も単純であり、直接・間接にこのアルゴリズムを使用している場合は多い。

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

手法

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

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

<math>\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}</math> ここでα は1回で更新する数値の割合を決めるパラメータであり、通常は小さな正の定数である。

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

最急降下法の流れは以下のようになる：

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

特徴

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

関連項目

• 数値解析
• 共役勾配法