서브그래디언트
정의 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고 한다.
성질
- Scaling: $a \gt 0$에 대해서, $\partial (af) = a \partial f$
- Addition: $\partial(f + g) = \partial f + \partial g$
- Affine composition: $g(\mathbf{x}) = f(A \mathbf{x} + \mathbf{b})$이면, $$ \partial g(\mathbf{x}) = A^{T}\partial f(A \mathbf{x} + \mathbf{b}) $$
- Subgradient optimality condition: 임의의 함수 $f$에 대해서, $$ f(\mathbf{x}_{\ast}) = \min\limits_{\mathbf{x}} f(\mathbf{x}) \iff 0 \in \partial f(\mathbf{x}_{\ast}) $$
같이보기
Rockafellar, R. Tyrrell. Convex analysis. Vol. 11. Princeton university press, 1997. p214~215 ↩︎
https://www.stat.cmu.edu/~ryantibs/convexopt-F16/lectures/subgrad.pdf ↩︎