📂最適化理論

サブグラディエント

定義 ^{1 2}

関数$f : \mathbb{R}^{n} \to \mathbb{R}$に対して、以下を満たす$\mathbf{g} \in \mathbb{R}^{n}$を点$\mathbf{x}$での$f$のサブグラディエント^subgradientという。

$$ f(\mathbf{y}) \ge f(\mathbf{x}) + \mathbf{g}^{T}(\mathbf{y} - \mathbf{x}) \qquad \forall \mathbf{y} \in \mathbb{R}^{n} $$

説明

凸関数$f$が$\mathbf{x}$で微分可能であれば、$\mathbf{g} =$$\nabla f(\mathbf{x})$は一意である。逆に$\partial f(\mathbf{x}) = \left\{ \mathbf{g} \right\}$であれば、$f$は$\mathbf{x}$で微分可能であり、$\nabla f (\mathbf{x}) = \mathbf{g}$である。

$\mathbf{x}$での$f$のサブグラディエントの集合を代替微分^{subdifferential}といい、以下のように記される。

$$ \partial f(\mathbf{x}) := \left\{ \mathbf{g} : \mathbf{g} \text{ is subgradient of } f \text{ at } \mathbf{x} \right\} $$

$\partial f(\mathbf{x}) \ne \varnothing$であれば、$f$は$\mathbf{x}$で代替微分可能^{subdifferentiable}であるという。

性質

• スケーリング: $a \gt 0$に対して、$\partial (af) = a \partial f$
• 加法: $\partial(f + g) = \partial f + \partial g$
• アフィン合成: $g(\mathbf{x}) = f(A \mathbf{x} + \mathbf{b})$であれば, $$ \partial g(\mathbf{x}) = A^{T}\partial f(A \mathbf{x} + \mathbf{b}) $$
• サブグラディエント最適条件: 任意の関数$f$に対して、 $$ f(\mathbf{x}_{\ast}) = \min\limits_{\mathbf{x}} f(\mathbf{x}) \iff 0 \in \partial f(\mathbf{x}_{\ast}) $$

参照

• サブグラディエントメソッド