[최적화] 라그랑주 쌍대 문제 (Lagrange Dual Problem)
쌍대 문제 (Dual problem)
원래의 최적화 문제 (Primal problem)를 직접 푸는 대신, 이와 관련된 다른 문제인 쌍대 문제 (Dual problem)를 풀어서 해를 유도하거나 문제의 하한 (Lower Bound)을 구할 수 있다.
즉, primal 문제는 원래의 최적화 문제, dual 문제는 새롭게 정의한 최적화 문제를 의미한다.
라그랑주 쌍대 함수 (Lagrangian Dual function)
라그랑주 함수에 대한 dual 함수를 아래와 같이 정의한다. 이는 라그랑주 함수를 원문제의 변수 $\mathbf{x}$에 대해 최소화한 값이다.
\[\mathcal{D}(\boldsymbol\lambda,\boldsymbol\mu) :=\inf_{\mathbf x}\mathcal{L}(\mathbf x,\boldsymbol\lambda,\boldsymbol\mu)\]최솟값이 항상 존재하지 않을 수도 있기 때문에 $\inf$를 사용한다.
$\min$은 실제로 도달한 최저점, $\inf$는 도달하지는 못해도 내려갈 수 있는 최저 한계 (이론적 최저점)를 의미한다.
예를 들어 $S=(0,1)$은 열구간이기 때문에, $\min S$는 존재하지 않지만 $\inf S=0$으로 존재한다.
$\inf$의 반대는 $\sup$이다.
라그랑주 쌍대 문제 (Lagrangian Dual problem)
Dual 문제는 위에서 정의한 dual 함수를 최대화하는 문제이다.
\[\begin{aligned} \max_{\boldsymbol\lambda,\boldsymbol\mu}\mathcal{D}(\boldsymbol\lambda,\boldsymbol\mu)~~~~\\ \text{subject to}~~\boldsymbol\mu\geq0 \end{aligned}\]Example 1
1. Lagrangian 함수를 정의한다.
\[\mathcal{L}(x,y,\lambda)=\frac{1}{2}(x^2+y^2)+\lambda(x+y-1)\]2. Dual 함수를 정의한다.
\[\mathcal{D}(\lambda)=\underset{x,y}\min~\mathcal{L}(x,y,\lambda)= \underset{x,y}\min~\big(\frac{1}{2}(x^2+y^2)+\lambda(x+y-1)\big)=-\lambda^2-\lambda\]3. Dual problem의 해를 구한다.
\[\underset{\lambda}\max~\mathcal{D}(\lambda)=\underset{\lambda}\max~(-\lambda^2-\lambda)=\frac{1}{4}=d^*\]구한 dual 문제의 최적해는 primal 문제의 최적해의 lower bound가 된다.
\[\underset{x,y}\min~\underset{\lambda}\max~\mathcal{L}(x,y,\lambda)\geq \underset{\lambda}\max~\mathcal{D}(\lambda)=\frac{1}{4} ~\rightarrow~p^*\geq\frac{1}{4}\]최소-최대 부등식 (Min-Max Inequality)
임의의 함수 $f$에 대해 항상 아래의 식이 성립한다.
\[\underset{\lambda}{\max}~\underset{x}{\min} ~f(x,\lambda)\leq\underset{x}{\min}~\underset{\lambda}{\max}~f(x,\lambda)\]즉, 최대화하고 최소화하는 것이 최소화하고 최대화하는 것보다 항상 크다는 의미이다.
공식 유도
1. $f$를 최소화한 함수를 $g$라고 정의한다.
\[g(x,\lambda):=\underset{x}{\min} ~f(x,\lambda)\]2. $g$는 $f$를 최소화한 함수이기 때문에 항상 $f$ 이하이다.
\[g(x,\lambda)\leq f(x,\lambda)\]3. 양변에 $\max_{\lambda}$ 함수를 취한다.
\[\underset{\lambda}{\max} ~g(x,\lambda)\leq\underset{\lambda}{\max} ~f(x,\lambda)\]4. 우변을 $\mathbf{x}$에 대해 최소화한다.
\[\underset{\lambda}{\max} ~g(x,\lambda)\leq\underset{x}{\min} ~\underset{\lambda}{\max} ~f(x,\lambda)\]이는 primal 문제와 dual 문제와 관련이 있다.
Primal 문제는 본질적으로 아래와 같이 표현할 수 있다.
\[p^*=\min_{\mathbf{x}}\max_{\lambda,\mu\geq0}~\mathcal{L}(\mathbf{x},\lambda,\mu)\]Dual 문제는 본질적으로 아래와 같이 표현할 수 있다.
\[d^*=\max_{\lambda,\mu\geq0}\min_{\mathbf{x}}~\mathcal{L}(\mathbf{x},\lambda,\mu)\]따라서 primal 문제의 최적값 $p^$ 의 하한은 dual 문제에서의 최적값 $d^$으로 제한된다.
\[\max_{\lambda,\mu\geq0}\min_{\mathbf{x}}~\mathcal{L}(\mathbf{x},\lambda,\mu) \leq\min_{\mathbf{x}}\max_{\lambda,\mu\geq0}~\mathcal{L}(\mathbf{x},\lambda,\mu)\]Duality gap
Primal 문제의 최적해과 dual 문제의 최적해 값의 차이를 duality gap이라고 한다.
약한 쌍대성 (Weak duality)
\[d^*\leq p^*\]위의 부등식은 항상 성립한다.
강한 쌍대성 (Strong duality)
\[d^*=p^*\]위의 등식은 Convex 문제에서 Slater의 정규성 조건이 만족될 때 성립한다.