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

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

 

 

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

 

\[ \begin{align} & p^\star = \min_{\mathbf{x}} f(\mathbf{x}) \\ \\ \mbox{subject to: } \ \ & g_i (\mathbf{x}) \le 0, \ \ \ i=1,...,m \\ \\ & h_j (\mathbf{x}) = 0, \ \ \ j=1,...,k \end{align} \]

 

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

 

\[ \begin{align} L( \mathbf{x}, \mathbf{\mu}, \mathbf{\lambda}) &= f(\mathbf{x})+ \mathbf{\mu}^T \mathbf{g}(\mathbf{x})+ \mathbf{\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{align} \]

 

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

 

\[ \begin{align} d(\mathbf{\mu}, \mathbf{\lambda} ) &= \min_{\mathbf{x}} ⁡L( \mathbf{x}, \mathbf{\mu}, \mathbf{\lambda}) \\ \\ &= \min_{\mathbf{x}} \left( f(\mathbf{x})+ \sum_{i=1}^m \mu_i g_i (\mathbf{x}) + \sum_{j=1}^k \lambda_j h_j (\mathbf{x}) \right) \end{align} \]

 

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

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

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

 

\[ f( \mathbf{x} ) \ge L(\mathbf{x}, \mathbf{\mu}, \mathbf{\lambda}) \ge \min_{\mathbf{x}} ⁡ L(\mathbf{x}, \mathbf{\mu}, \mathbf{\lambda}) = d( \mathbf{\mu}, \mathbf{\lambda}) \]

 

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

 

\[ p^\star = \min_{\mathbf{x}} f(\mathbf{x}) \ge d( \mathbf{\mu}, \mathbf{\lambda}) \]

 

가 됨을 알 수 있다.

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

 

\[ \begin{align} & d^\star = \max_{\mathbf{\mu}, \mathbf{\lambda}} d( \mathbf{\mu}, \mathbf{\lambda}) = \max_{\mathbf{\mu}, \mathbf{\lambda}} \ \min_{\mathbf{x}} ⁡L(\mathbf{x}, \mathbf{\mu}, \mathbf{\lambda}) \\ \\ \mbox{subject to: } \ \ & \mu_i \ge 0, \ \ \ i=1,...,m \\ \\ \mbox{or } \ \ & \mathbf{\mu} \ge 0 \end{align} \]

 

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

 

\[ p^\star \ge d^\star \]

 

 

 

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

 

\[ \begin{align} & \min_{\mathbf{x}} \mathbf{x}^T \mathbf{x} \\ \\ \mbox{subject to: } \ \ & A \mathbf{x} = \mathbf{b} \end{align} \]

 

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

 

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

 

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

 

\[ \begin{align} & \nabla_{\mathbf{x}} L( \mathbf{x}, \mathbf{\lambda}) =2 \mathbf{x}+ A^T \mathbf{\lambda}=0 \\ \\ & \ \ \to \mathbf{x}= -\frac{1}{2} A^T \mathbf{\lambda} \end{align} \]

 

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

 

\[ \begin{align} d( \mathbf{\lambda}) &= \min_{\mathbf{x}} ⁡L(\mathbf{x}, \mathbf{\lambda}) \\ \\ &= \frac{1}{4} \mathbf{\lambda}^T A A^T \mathbf{\lambda} - \frac{1}{2}\mathbf{\lambda}^T AA^T \mathbf{\lambda}- \mathbf{\lambda}^T \mathbf{b} \\ \\ &=- \frac{1}{4}\mathbf{\lambda}^T AA^T \mathbf{\lambda}- \mathbf{\lambda}^T \mathbf{b} \end{align} \]

 

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

 

\[ p^\star \ge - \frac{1}{4}\mathbf{\lambda}^T AA^T \mathbf{\lambda}- \mathbf{\lambda}^T \mathbf{b} \]

 

 

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

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

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