劣勾配法
劣勾配法（れつこうばいほう、英: Subgradient methods）とは、劣微分を用いた凸最適化の解法である。1960年代から1970年代にかけてナウム・ショアによって編み出された解法であり、微分不可能な目的関数に対して収束性を持つことが知られている。目的関数が微分可能な関数で無制約な問題の場合は最急降下法と同様の探索方向が使用される。
劣勾配法は2階微分可能な連続凸最小化問題に対してニュートン法より収束が遅いが、ニュートン法は微分不可能な点を持つ問題に対して適用することができないことから、汎用性が高い解法である。
近年では、凸最適化問題に対して内点法が提案されているが、射影劣勾配法やバンドル法といった解法も研究がなされている。劣勾配法などは計算にかかるメモリの量が比較的少量で済むことから、高次元の凸最適化問題に対しては適した解法である。
射影劣勾配法は大規模問題に対して分解法と共に使用されることが多い。分解法を用いることで問題を分割して問題を安易に扱うことができる。
古典的な劣勾配法の規則
定義域 
| 一般 | |
|---|---|
| 微分可能 |
| 凸縮小化 | |||||||
|---|---|---|---|---|---|---|---|
| 線形 および 二次 |
|
| 系列範例 (Paradigms) | |||||
|---|---|---|---|---|---|
| グラフ理論 |
| ||||
| ネットワークフロー (最大流問題) |
