最急降下法

この項目では、最適化アルゴリズムについて説明しています。解析的（漸近）近似については「最急降下法 (漸近解析)（英語版）あるいは鞍点法（英語版）」をご覧ください。

「勾配降下法」はこの項目へ転送されています。確率的勾配降下法については「確率的勾配降下法」をご覧ください。

最急降下法（さいきゅうこうかほう、英: gradient descent, steepest descent）^[1]は、関数（ポテンシャル面）の傾き（一階微分）のみから、関数の最小値を探索する連続最適化問題の勾配法のアルゴリズムの一つ。勾配法としては最も単純であり、直接・間接にこのアルゴリズムを使用している場合は多い。最急降下法をオンライン学習に改良した物を確率的勾配降下法と呼ぶ。

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

手法

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

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

${\begin{aligned}{\boldsymbol {x}}^{(k+1)}={\boldsymbol {x}}^{(k)}-\alpha \operatorname {grad} f({\boldsymbol {x}}^{(k)})={\boldsymbol {x}}^{(k)}-\alpha {\begin{bmatrix}\partial f({\boldsymbol {x}}^{(k)})/\partial x_{1}^{(k)}\\\partial f({\boldsymbol {x}}^{(k)})/\partial x_{2}^{(k)}\\\vdots \\\partial f({\boldsymbol {x}}^{(k)})/\partial x_{n}^{(k)}\end{bmatrix}}\end{aligned}}$

(最急降下法)

ここで α は 1 回に更新する数値の重みを決めるパラメータであり、通常は小さな正の定数である。パラメータ α の適正な範囲は多くの場合、取り扱う問題の性質によって決まる。例えば力学問題を計算する際、計算結果が発散するような設定を与えることは、何らかの意味で非物理的な仮定をしている（あるいは元々のモデルの適用範囲を超えている）ことを示している。

例えば、y = x² の最小値の探索において、α > 1 の場合、反復ごとに悪い解へと向かう。解の探索能力、収束速度は α に強く依存しており、α が大きすぎると発散の恐れがあり、小さすぎると収束が遅くなる（緩和法（英語版）も参照）。そのため、探索の初期では大きめにし、ある程度収束したら小さくする方法もとられる。小さくするやり方は反復回数の逆数や指数関数的減衰などがあり、焼きなまし法が参考になる。

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

最急降下法のスキームは以下のようになる^[1]：

x の初期値 x⁽⁰⁾ を決める（必要であれば、反復回数を記憶する変数を k = 0 と初期化しておく。実際には x を記憶する領域は 1 つで充分なので、単純に最急降下法のみを行う場合には必要ない）。
∂f (x^(k))/∂x_i^(k) = 0 (i = 1, ... , n) であるなら終了する（実際は正確に 0 になることはないので、十分小さな値になれば終了する）。
上記の記述に従って x^(k) を更新する。
2 に戻る（必要なら k の値を 1 つ進める）。

特徴

傾き（一階微分）のみしか見ないので手法として簡便で計算も速い。
勾配法のため、局所的な最小値に捉まり易く、大域的な最小値を求めるのは困難であることが欠点である。それを回避するために、複数の初期値から探索を行うなどの対策が必要である。対策としては確率的勾配降下法も参照。
関数 f の偏微分が計算できなくてはならない。

出典

^ ^a ^b ^c 茨木, 俊秀『最適化の数学』共立出版〈共立講座 21世紀の数学 13〉、2011年6月23日。ISBN 978-4320015654。

関連項目

数理最適化 • 最適化問題 : メソッド • ヒューリスティック

非線形(無制約)

… 関数　

黄金分割探索
直線探索
ネルダー–ミード法
連続放物線補間（英語版）

勾配法

収束性	信頼領域ウルフ条件（英語版）
準ニュートン法	BFGS法ブロイデン法 L-BFGS（英語版） DFP法対称ランク1法（英語版）
その他の求解法	ガウス・ニュートン法最急降下法レーベンバーグ・マルカート法共役勾配法（非線形共役勾配法）切り捨てニュートン法（英語版）ドッグレッグ法

… ヘッセ行列

最適化におけるニュートン法（英語版）

非線形(制約付き)

一般	バリア関数ペナルティ関数法（英語版）
微分可能	ラグランジュの未定乗数法逐次二次計画法連続線形計画（英語版）

凸最適化

凸縮小化

切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版）
簡約勾配法
劣勾配法（英語版）

線型および
二次

内点法	カチヤン楕円体法カーマーカーの投影アルゴリズム
ベイズ-交換	単体法改訂シンプレックス法（英語版）十字法（英語版）レムケの主ピボット操作法（英語版）

組合せ最適化

系列範例
(Paradigms)

グラフ理論

最小全域木	ベルマン–フォード法ブルーフカ法ダイクストラ法ワーシャル–フロイド法ジョンソン法（英語版）クラスカル法
最大フロー問題	Dinic法（英語版）エドモンズ・カープフォード・ファルカーソンプッシュリラベル最大流アルゴリズム（英語版）