Convex 함수에서 first order 조건식 유도하기

Convex 함수의 정의를 먼저 살펴보자.

$$ \alpha f(y) + (1 - \alpha) f(x) \ge f \left( \alpha y + \left( 1 - \alpha \right) x \right) \; \; such \; that \; ^\forall x, y \in \mathbb{R}^d \;\; 0 \le \alpha \le 1 \;\; f : \mathbb{R}^d \rightarrow \mathbb{R} $$

여기서 왼쪽 항을 아래와 같이 수정한다.

$$ \alpha f(y) + (1-\alpha) f(x) = f(x) + \alpha \left( f \left( y \right) - f \left( x \right) \right) $$

그리고 오른쪽 항을 아래와 같이 수정한다.

$$ f \left( \alpha y + \left( 1 - \alpha \right) x \right) = f \left( x + \alpha \left( y - x \right) \right) $$

그럼 아래와 같이 부등식을 바꿔쓸 수 있다.

$$ f(x) + \alpha \left( f \left( y \right) - f \left( x \right) \right) \ge f \left( x + \alpha \left( y - x \right) \right) $$

여기서 부등식 항을 정리하면 다음과 같이 표현할 수 있다.

$$ \alpha \left( f \left( y \right) - f \left( x \right) \right) \ge f \left( x + \alpha \left( y - x \right) \right) - f(x) $$

여기서 $\left( y - x \right)^\top \left( y - x \right)$를 양쪽 항에 곱한다. 이 값은 해당 벡터의 norm을 의미하므로 항상 양수다. 따라서 부등호의 방향은 바뀌지 않는다.

$$ \alpha \left( f \left( y \right) - f \left( x \right) \right) \left( y - x \right)^\top \left( y - x \right) \ge \left( f \left( x + \alpha \left( y - x \right) \right) - f(x) \right) \left( y - x \right)^\top \left( y - x \right) $$

$\Delta x = \alpha \left( y - x \right)$로 표현하면 다음과 같아진다.

$$ \left( f \left( y \right) - f \left( x \right) \right) \Delta x^\top \left( y - x \right) \ge \left( f \left( x + \Delta x \right) - f(x) \right) \left( y - x \right)^\top \left( y - x \right) $$

여기서 $\lim_{\Delta x \rightarrow 0} f(x + \Delta x) - f(x) = \lim_{\Delta x \rightarrow 0} \nabla f^\top (x) \Delta x$를 이용하기 위해서 $\lim_{\Delta x \rightarrow 0}$를 붙여주면 다음과 같아진다.

$$ \left( f \left( y \right) - f \left( x \right) \right) \Delta x^\top \left( y - x \right) \ge \nabla f^\top (x) \Delta x \left( y - x \right)^\top \left( y - x \right) $$

여기서 전치 성질을 이용해서 아래와 같이 바꾼다. 그리고 $\Delta x^\top \left( y - x \right)$는 방향이 같은 벡터를 내적한 것이기 때문에 항상 양수이다. 따라서, 이를 양쪽에다가 나누어도 부등호의 방향이 바뀌지 않는다.

$$ \left( f \left( y \right) - f \left( x \right) \right) \Delta x^\top \left( y - x \right) \ge \nabla f^\top (x) \left( y - x \right) \Delta x^\top \left( y - x \right) $$

$$ \left( f \left( y \right) - f \left( x \right) \right) \ge \nabla f^\top (x) \left( y - x \right) $$

마지막으로, $f(x)$를 오른쪽으로 넘기면 전개가 끝난다.

$$ f \left( y \right) \ge f(x) + \nabla f^\top (x) \left( y - x \right) $$