劣勾配

劣勾配#

  • 読み: れつこうばい

  • 英名: 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}\]

また,離散最適化問題のラグランジュ双対問題を解く際には,劣勾配が容易に得られることから,劣勾配法を用いることができる.