[KKT 조건 - 3] 프라이멀 문제와 듀얼 문제

최적화 문제는 두 가지 관점에서 문제를 표현할 수 있는데 프라이멀 문제(primal problem)와 듀얼 문제(dual problem)가 그것이다. 어떤 문제에서는 프라이멀 문제보다도 듀얼 문제로 바꾸어 푸는 것이 더욱 효과적일 수 있다.

 

 

먼저 프라이멀 문제는 등식과 부등식 제약조건이 있는 본래의 최적화 문제를 말한다.

 

$$\begin{array}{rl}& p^{\star }=\underset{\mathbf{x}}{min}f(\mathbf{x})\\ \\ \text{subject to: }& g_i(\mathbf{x})\le 0,i=1,...,m\\ \\ & h_j(\mathbf{x})=0,j=1,...,k\end{array}$$

 

이 문제에 대한 라그랑지안을 다음과 같이 정의한 바 있다.

 

$$\begin{array}{rl}L(\mathbf{x},\mu ,\lambda )& =f(\mathbf{x})+{\mu }^T\mathbf{g}(\mathbf{x})+{\lambda }^T\mathbf{h}(\mathbf{x})\\ \\ & =f(\mathbf{x})+\sum _{i=1}^m{\mu }_i{g}_i(\mathbf{x})+\sum _{j=1}^k{\lambda }_j{h}_j(\mathbf{x})\end{array}$$

 

이제 라그랑지 듀얼 함수(Lagrange dual function)를 다음과 같이 정의한다.

 

$$\begin{array}{rl}d(\mu ,\lambda )& =\underset{\mathbf{x}}{min}L(\mathbf{x},\mu ,\lambda )\\ \\ & =\underset{\mathbf{x}}{min}(f(\mathbf{x})+\sum _{i=1}^m{\mu }_i{g}_i(\mathbf{x})+\sum _{j=1}^k{\lambda }_j{h}_j(\mathbf{x}))\end{array}$$

 

여기서 $\mathbf{x}\in {\mathbb{R}}^n$ 을 프라이멀 변수, $\mu \in {\mathbb{R}}^m,$ 와 $\lambda \in {\mathbb{R}}^k$ 를 듀얼 변수라고 한다. 라그랑지 듀얼 함수는 프라이멀 변수에 대해서 라그랑지안이 최소값을 갖는 함수다.

라그랑지 듀얼 함수는 $\mu \ge 0$일 때 프라이멀 최적화 문제의 해 $p^{\star }$ 보다 항상 같거나 작기 때문에 프라이멀 최적해의 하한선(lower bound)을 제공해 준다. 이에 대한 증명은 아래와 같다.

만약 $\mathbf{x}$가 등식과 부등식 제약조건을 모두 만족한다면,

 

$$f(\mathbf{x})\ge L(\mathbf{x},\mu ,\lambda )\ge \underset{\mathbf{x}}{min}L(\mathbf{x},\mu ,\lambda )=d(\mu ,\lambda )$$

 

가 된다. 참고로 여기서 $f(\mathbf{x})$와 $d(\mu ,\lambda )$의 차이를 듀얼리티 갭(duality gap)이라고 한다. 위 부등식 관계식은 모든 실행 가능(feasible)한 $\mathbf{x}$에 대해서 성립하므로

 

$$p^{\star }=\underset{\mathbf{x}}{min}f(\mathbf{x})\ge d(\mu ,\lambda )$$

 

가 됨을 알 수 있다.

프라이멀 문제에 대한 듀얼 문제는 다음과 같이 정의한다.

 

$$\begin{array}{rl}& d^{\star }=\underset{\mu ,\lambda }{max}d(\mu ,\lambda )=\underset{\mu ,\lambda }{max}\underset{\mathbf{x}}{min}L(\mathbf{x},\mu ,\lambda )\\ \\ \text{subject to: }& {\mu }_i\ge 0,i=1,...,m\\ \\ \text{or }& \mu \ge 0\end{array}$$

 

듀얼 문제의 해 $d^{\star }$는 라그랑지 듀얼 함수가 가질 수 있는 최대값이므로 프라이멀 최적해 $p^{\star }$에 대한 최상의 하한선을 제공해 준다.

 

$$p^{\star }\ge d^{\star }$$

 

 

 

예를 들어보자. 다음과 같은 최적화 문제가 있다.

 

$$\begin{array}{rl}& \underset{\mathbf{x}}{min}{\mathbf{x}}^T\mathbf{x}\\ \\ \text{subject to: }& A\mathbf{x}=\mathbf{b}\end{array}$$

 

이 문제에 대한 라그랑지안은 다음과 같다.

 

$$L(\mathbf{x},\lambda )={\mathbf{x}}^T\mathbf{x}+{\lambda }^T(A\mathbf{x}-\mathbf{b})$$

 

$\mathbf{x}$에 대한 라그랑지안의 최소값을 구하기 위해서 그래디언트를 0으로 놓는다.

 

$$\begin{array}{rl}& {\mathrm{\nabla }}_{\mathbf{x}}L(\mathbf{x},\lambda )=2\mathbf{x}+A^T\lambda =0\\ \\ & \to \mathbf{x}=-\frac{1}{2}{A}^T\lambda \end{array}$$

 

$\mathbf{x}$를 라그랑지안에 대입하면 라그랑지 듀얼 함수를 구할 수 있다.

 

$$\begin{array}{rl}d(\lambda )& =\underset{\mathbf{x}}{min}L(\mathbf{x},\lambda )\\ \\ & =\frac{1}{4}{\lambda }^{T}A{A}^T\lambda -\frac{1}{2}{\lambda }^{T}A{A}^T\lambda -{\lambda }^T\mathbf{b}\\ \\ & =-\frac{1}{4}{\lambda }^{T}A{A}^T\lambda -{\lambda }^T\mathbf{b}\end{array}$$

 

결과적으로 라그랑지 듀얼 함수는 $\lambda$에 대해서 컨케이브(concave) 함수가 됐다. 그러면 최적해 $p^{\star }$의 하한선(lower bound)은 다음과 같이 된다.

 

$$p^{\star }\ge -\frac{1}{4}{\lambda }^{T}A{A}^T\lambda -{\lambda }^T\mathbf{b}$$

 

 

예제에서 라그랑지 듀얼 함수가 컨케이브 함수가 됐는데 이는 특별한 결과가 아니고 라그랑지 듀얼 함수는 항상 컨케이브 함수다. 그리고 어떤 $\mu ,\lambda$ 값에서는 듀얼 함수의 값이 $-\mathrm{\infty }$ 가 될 수도 있다.

프라이멀 문제의 해 $p^{\star }$가 듀얼 문제의 해 $d^{\star }$ 보다 항상 크거나 같지만 ($p^{\star }\ge d^{\star }$) 어떤 조건(Slater's condition)을 만족한다면 두 해가 같아진다 ($p^{\star }=d^{\star }$). 이 경우를 일컬어 강한 듀얼리티(strong duality) 관계에 있다고 한다.

강한 듀얼리티가 성립하는 문제의 경우는 프라이멀 문제를 듀얼 문제로 바꾸어 풀 수도 있다. 일반적으로 컨벡스 최적화 문제에서는 강한 듀얼리티가 성립한다.