劣勾配法

OR事典

劣勾配法

読み方：れつこうばいほう
【英】：subgradient method

微分不可能な関数における非線形最適化手法の1つ. 最適解に近づくように, 解を改善する方向ベクトル(劣勾配)と, その方向に移動する距離とを求め, これを繰り返しながら解を改善する. 組合せ最適化問題(最小化とする)において, ラグランジュ緩和問題が簡単に解けるような場合には, 適切なラグランジュ乗数を決定する問題が, (微分不可能な)区分線形関数の最大値を求める問題になることから, よりよい下界値を求めるときに常套的に用いられる.

「OR事典」の他の用語

組合せ最適化：

分散アルゴリズム  分枝切除法  分枝限定法  劣勾配法  動的木  動的計画  多面体理論

ウィキペディア

劣勾配法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/05/08 07:59 UTC 版)

劣勾配法（れつこうばいほう、英: Subgradient methods）とは、劣微分を用いた凸最適化の解法である。1960年代から1970年代にかけてナウム・ショアによって編み出された解法であり、微分不可能な目的関数に対して収束性を持つことが知られている。目的関数が微分可能な関数で無制約な問題の場合は最急降下法と同様の探索方向が使用される。

劣勾配法は2階微分可能な連続凸最小化問題に対してニュートン法より収束が遅いが、ニュートン法は微分不可能な点を持つ問題に対して適用することができないことから、汎用性が高い解法である。

近年では、凸最適化問題に対して内点法が提案されているが、射影劣勾配法やバンドル法といった解法も研究がなされている。劣勾配法などは計算にかかるメモリの量が比較的少量で済むことから、高次元の凸最適化問題に対しては適した解法である。

射影劣勾配法は大規模問題に対して分解法と共に使用されることが多い。分解法を用いることで問題を分割して問題を安易に扱うことができる。

古典的な劣勾配法の規則

定義域 $\mathbb {R} ^{n}.$

Optimization computes maxima and minima.

非線形（制約付き）

凸最適化

組合せ最適化

メタヒューリスティクス

• 進化的アルゴリズム（進化戦略・遺伝的アルゴリズム）
• 山登り法
• 局所探索法
• 焼きなまし法
• タブーサーチ
• ベイスンホッピング法
• 量子焼きなまし法

• カテゴリ（最適化 • アルゴリズム） • ソフトウェア