12-05 Constrained and Lagrange forms

통계학과 기계학습에서는 종종 constrained form과 Lagrange form 사이를 오가곤 한다. Constrained form과 Lagrangian form을 다음과 같이 정의해보자.

Constrained Form (이하 (C))

$$\begin{gathered} \underset{x}{min}f(x)\text{ subject to }h(x)\le t, \\ \text{where }t\in \mathbb{R}\text{ is a tuning parameter.} \end{gathered}$$

Lagrange Form (이하 (L))

$$\begin{gathered} \underset{x}{min}f(x)+\lambda \cdot h(x), \\ \text{where }\lambda \ge 0\text{ is a tuning parameter.} \end{gathered}$$

$f,h$가 convex라고 가정할때, 두 문제가 동일한 solution을 도출하는 경우에 대해 알아보도록 하자.

1. (C) to (L): (C)가 strictly feasible (Slater’s condition을 만족)하여 strong duality를 만족할 때, (C)의 solution인 $x^{\star }$에 대해 다음의 목적함수를 최소화하는 dual solution ${\lambda }^{\star }\ge 0$가 존재한다면 $x^{\star }$는 또한 (L)의 solution이다.

1. (L) to (C): 만약 $x^{\star }$가 (L)의 solution이고, $t=h(x^{\star })$인 (C)가 KKT conditions를 만족하면, $x^{\star }$는 또한 (C)의 solution이다. (L)의 KKT conditions를 만족하는 ${\lambda }^{\star },x^{\star }$는 $t=h(x^{\star })$인 (C)의 KKT conditions를 또한 만족하기 때문이다.

$\to$ (L)의 KKT conditions:

$$\begin{array}{rl}{\mathrm{\nabla }}_{x}f(x^{\star })+{\lambda }^{\star }{\mathrm{\nabla }}_{x}h(x^{\star })& =0\\ \\ {\lambda }^{\star }& \ge 0\\ \end{array}$$

$\to$ $t=h(x^{\star })$인 (C)의 KKT conditions:

$$\begin{array}{rl}{\mathrm{\nabla }}_{x}f(x^{\star })+{\lambda }^{\star }{\mathrm{\nabla }}_{x}h(x^{\star })& =0\\ \\ {\lambda }^{\star }& \ge 0\\ \\ {\lambda }^{\star }(\underset{=0}{\underbrace{h(x^{\star })-h(x^{\star })}})& =0\end{array}$$

결론적으로 1과 2는 각각 다음과 같은 관계를 보인다.

그렇다면 어떤 상황에서 (C)와 (L)이 perfect equivalence를 보이게 될까?
가령, $h(x)\ge 0$ (예를 들어 norm), $t=0$이고, $\lambda =\mathrm{\infty }$인 경우에는 perfect equivalence를 보인다. 주어진 조건에 의해 (C)에서의 제약조건은 $h(x)=0$이 되는데, $\lambda$를 $\mathrm{\infty }$으로 설정하게되면 (L)에서 또한 동일한 제약조건($h(x)=0$)을 거는 것과 같은 효과를 보인다.