Search
Duplicate

수학/ sub-gradient, super-gradient

sub-gradient

subgradient는 볼록 함수(convex)에서 미분 불가능한 점 —연속인데 뾰족하거나 연속이 아닌 점— 에 대한 미분값을 정의하는 개념으로 다음과 같이 정의된다. 아래는 실수에 대해 설명하지만 벡터에 대해서도 동일하게 확장 가능하다.
함수 f:R→Rf : \mathbb{R} \to \mathbb{R}의 모든 점 x∈Rx \in \mathbb{R} 대해, 아래 부등식을 만족하면 g∈Rg \in \mathbb{R}를 점 x0x_0에서 ff의 subgradient라고 한다.
f(x)≥f(x0)+g⋅(x−x0)f(x) \ge f(x_0) + g \cdot (x-x_0)
이 식을 gg에 대해 정리하면 익숙한 모양을 얻을 수 있다. 이러면 gg가 점 x0x_0의 미분값에 대해 하한(lower bound)함을 알 수 있다.
g≤f(x)−f(x0)x−x0g \le {f(x) - f(x_0) \over x-x_0}
이 부등식은 기본적으로 gg가 ff의 그래프 아래에 있는 모든 점에 대해 x0x_0에서의 선형 근사보다 항상 낮거나 같다는 것을 의미한다. 이는 gg가 ff의 그래프를 x0x_0에서 지지(support)한다는 개념이다. 미분이 가능한 점에 대해 subgradient는 일반적인 미분값과 동일하다.
예컨대 f(x)=∣x−1∣f(x) = |x-1|의 함수는 x=1x = 1인 지점에서 미분이 불가능하다. 따라서 x=1x = 1인 지점을 기준으로 함수를 다음과 같이 두 부분으로 나눌 수 있다.
f(x)={1−xx<1x−1x>1f(x) = \begin{cases} 1 - x & x < 1 \\ x - 1 & x > 1 \end{cases}
두 부분에 대해 각각 미분값을 구하면 다음과 같다.
f(x)′={−1x<1+1x>1f(x)' = \begin{cases} -1 & x < 1 \\ +1 & x > 1 \end{cases}
이를 이용해서 다음과 같이 함수에 대해 subgradient를 정의할 수 있다. x=1x = 1인 점에서는 x<1x < 1의 값과 x>1x > 1의 값 사이의 값을 구간으로 갖는다.
f(x)′={{−1}x<1[−1,1]x=1{+1}x>1f(x)' = \begin{cases} \{ -1\} & x < 1 \\ [-1, 1] & x = 1 \\ \{+1\} & x > 1 \end{cases}

super-gradient

sub-gradient가 볼록 함수에서 하한인 점을 찾는 것에 반해, 이와 반대로 오목(concave) 함수에서는 상한인 점을 찾는 super-gradient가 존재한다. 상한이므로 subgradient와는 부등식 방향이 반대이다.
f(x)≤f(x0)+g⋅(x−x0)f(x) \le f(x_0) + g \cdot (x-x_0)
이 식을 gg에 대해 정리하면 익숙한 모양을 얻을 수 있다. 이 경우 gg가 점 x0x_0의 미분값에 대해 상한(upper bound)임을 알 수 있다.
g≥f(x)−f(x0)x−x0g \ge {f(x) - f(x_0) \over x-x_0}

참조

Made with