劣勾配#
読み: れつこうばい
英名: Subgradient
凸関数 \(f \colon \mathbb{R}^n \to \mathbb{R}\) に対して点 \(x \in \mathbb{R}^n\) における劣勾配とは，任意の \(y \in \mathbb{R}^n\) に対して \(f(y) - f(x) \ge \xi^\top (y-x)\) -(*) が成立するようなベクトル \(\xi \in \mathbb{R}^n\) のことを表す．
また，(*) を満たすベクトル \(\xi\) 全体の集合を \(\ \partial f(x)\) で表し，\(f\) の点 \(x\) における劣微分と呼ぶ．
例えば，関数 \(f \colon \mathbb{R} \to \mathbb{R}\) が \(f(x) = |x-1|\) で与えられているとき，その劣微分 \(\ \partial f(x)\) は，以下のようになる．
(110)#\[\begin{split}\partial f(x) = \left\{
\begin{array}{ll}
\{-1\} & (x < 1) \\
\left[ -1,1 \right] & (x = 1) \\
\{1\} & (1 < x)
\end{array}
\right.\end{split}\]
また，離散最適化問題のラグランジュ双対問題を解く際には，劣勾配が容易に得られることから，劣勾配法を用いることができる．