[Convex Optimization] Conjugate Function

 

Conjugate function은 최적화 문제를 상응하는 Dual problem으로 변환하여 풀도록 하는 핵심 개념입니다. 

함수 \(f: \mathbf{R}^n \to \mathbf{R}\)가 주어졌을 때, \(f\)의 켤레 함수(conjugate function) \( f^{*}: \mathbf{R}^n \to \mathbf{R} \) 는 아래와 같이 정의됩니다. $$f^*(y) = \sup_{x \in \mathrm{dom}(f)} (y^T x - f(x))$$

여기서 \(\sup\) 즉, supermum은 주어진 set의 상한(least upper bound)을 나타냅니다. 

 

Conjugate function의 기하학적 의미

예를 들어 1차원 함수 \(f(x)\)의 conjugate function을 생각해볼까요?

\( f^*(y) = \sup_x (yx - f(x)) \)

이는 기울기(slope)가 \(y\)인 모든 직선 중에서, \(f(x)\)의 그래프를 아래에서 support하면서 최대의 \(y\)-절편을 가지는 직선을 찾는 것으로 해석해볼 수 있습니다. 다시 말해, 1차원 함수에서 \(f^*(y)\)는 기울기 \(y\)를 가진 모든 supporting hyperplane 중에서 \(f(x))\)의 epigraph epi(\(f\))에 접하면서 가장 큰 \(y\)절편을 가지는 직선(혹은 hyperplane)의 절편값입니다. 

 

Conjugate 함수의 속성

1) 항상 convex function이다. (conjugate function이 항상 affine function의 pointwise supremem으로 정의되기 때문)

2) Fenchel's Inequality

임의의 \(x \in dom(f) \)와 임의의 \(y \in dom(f^{*) \)에 대해 다음 부등식이 성립합니다. $$f(x) + f^*(y) \ge y^T x$$

3) Conjugate of the Conjugate

conjugate에 conjugate을 취한 것은 이중 켤레(biconjugate) \(f^{**}\)라고 합니다. 

만약 \(f\)함수가 closed convex 함수라면 이중 켤레는 원래 함수 \(f\)와 동일합니다. 

4) \(f\)가 미분 가능한 convex함수라면 \( y^{T}x-f(x) \)를 최대화하는 x는 기울기가 0인 지점에서 발생합니다. 즉, \(y- \nabla f(x) = 0\) 이므로 \(y = \nabla f(x) \)입니다. 이 경우 conjugate function은 다음과 같이 표현될 수 있습니다. 

$$f^*(\nabla f(x)) = \nabla f(x)^T x - f(x)$$

르장드르 변환(legendre transform)과의 관련성은 추후 포스팅 하겠습니다.