07-03-01 Subgradient Optimality Condition

Lemma

모든 함수 $f$에 대해서, 어떤 $x^{\ast }$에서 함수의 최소값을 갖는 것과 $x^{\ast }$에서 subgradient가 $0$인 것은 서로 필요충분조건이다.

$$f(x^{\ast })=\underset{x}{min}f(x)⟺0\in \partial f(x^{\ast })$$

Proof

$$\begin{array}{rl}& f(x^{\ast })=\underset{x}{min}f(x)\\ ⟺& f(y)\ge f(x^{\ast })\text{ for all }y\\ ⟺& f(y)\ge f(x^{\ast })+0^T(y-x^{\ast })\\ ⟺& 0\in \partial f(x^{\ast })\end{array}$$

위 증명에서 함수 $f$에 대한 볼록성은 전혀 이용되지 않았으며, 따라서 비볼록함수에서도 예외없이 적용되는 최적 조건이라고 할 수 있다.