📂最適化理論

サブグラディエント法

定義¹

目的関数 $f : \mathbb{R}^{n} \to \mathbb{R}$が凸関数だとしよう。点$\mathbf{x}^{(k)}$での$f$のサブグラディエントを$\mathbf{g}^{(k)}$としよう。以下の方法で$\mathbf{x}^{(k)}$をアップデートして$f$に対する最適化問題を解く方法をサブグラディエント法^{subgradient method}という。

$$\mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} - \alpha \mathbf{g}^{(k)}$$

説明²

勾配降下法でグラディエントがサブグラディエントに置き換えられた形だ。

$$\text{gradient descent: } \mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} - \alpha \nabla f(\mathbf{x}^{(k)})$$

$f$が微分可能なら勾配降下法を使えばいいので、目的関数が微分可能ではない時に選べる最適化方法だ。ただし収束速度が遅いという欠点がある。