logo

サブグラディエント 📂最適化理論

サブグラディエント

定義 1 2

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

f(y)≥f(x)+gT(y−x)∀y∈Rn f(\mathbf{y}) \ge f(\mathbf{x}) + \mathbf{g}^{T}(\mathbf{y} - \mathbf{x}) \qquad \forall \mathbf{y} \in \mathbb{R}^{n}

説明

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

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

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

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

性質

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

参照

  1. Rockafellar, R. Tyrrell. Convex analysis. Vol. 11. Princeton university press, 1997. p214~215 ↩︎

  2. https://www.stat.cmu.edu/~ryantibs/convexopt-F16/lectures/subgrad.pdf ↩︎