劣勾配法

OR事典

劣勾配法

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

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

「OR事典」の他の用語

組合せ最適化：

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

ウィキペディア

劣勾配法

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

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

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

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

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

古典的な劣勾配法の規則

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

Optimization computes maxima and minima.

非線形（制約付き）

一般	バリア関数 ペナルティ関数法
微分可能	ラグランジュの未定乗数法 拡張ラグランジュ関数法 逐次二次計画法 逐次線形計画法

凸最適化

凸縮小化	切除平面法 簡約勾配法 劣勾配法
線形 および 二次	内点法 アフィンスケーリング法 カーマーカーの射影変換法 メロートラの予測子修正子法 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法 有効制約法 列生成法 ベンダーズ分解法

組合せ最適化

系列範例 (Paradigms)	近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法）
グラフ理論	最小全域木 ブルーフカ法 クラスカル法 プリム法 最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法
ネットワークフロー (最大流問題)	ディニッツ法 エドモンズ・カープ法 フォード・ファルカーソン法 プリフロープッシュ法

メタヒューリスティクス

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

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