📂최적화이론

서브그래디언트

정의 ^{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}) $$

같이보기

• 서브그래디언트 메서드