劣勾配#
読み: れつこうばい
英名: 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}\]
また,離散最適化問題のラグランジュ双対問題を解く際には,劣勾配が容易に得られることから,劣勾配法を用いることができる.