トップ > 数理計画用語集 > 劣勾配

数理計画用語集

劣勾配

読み:れつこうばい
英名: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)$ は,以下のようになる.

$$ \partial f(x) = \left\{ \begin{array}{ll} \{-1\} & (x < 1) \\ \left[ -1,1 \right] & (x = 1) \\ \{1\} & (1 < x) \end{array} \right. $$

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