프라이멀 문제와 듀얼 문제의 유도

제약조건을 갖는 최적화 문제는 지시함수(indicator function)를 이용하면 제약조건이 없는 최적화 문제로 바꿀 수 있다.

 

 

지시함수는 어떤 집합에 어떤 값이 속하는지를 표시하는 함수로서 어떤 집합 \(\mathcal{X}\) 의 지시함수 \(I_{\mathcal{X}}\) 는 다음과 같이 정의된다.

 

\[ I_{\mathcal{X}} (\mathbf{x}) = \begin{cases} 0, & \mbox{if } \mathbf{x} \in \mathcal{X} \\ \infty, & \mbox{if } \mathbf{x} \notin \mathcal{X} \end{cases} \tag{1} \]

 

 

 

다음과 같은 제약조건을 갖는 최적화 문제가 있을 때,

 

\[ \begin{align} & \min_{\mathbf{x} \in \mathbb{R}^n} f(\mathbf{x}) \tag{2} \\ \\ \mbox{subject to: } & \mathbf{x} \in \mathcal{X} \end{align} \]

 

지시함수를 이용하면 위 최적화 문제를 다음과 같이 제약조건이 없는 형태로 변환할 수 있다.

 

\[ \min_{\mathbf{x} \in \mathbb{R}^n} f(\mathbf{x}) + I_{\mathcal{X}}(\mathbf{x}) \tag{3} \]

 

구체적으로 등식 제약조건과 부등식 제약조건이 있는 최적화 문제에 대해서 지시함수를 이용하여 제약조건이 없는 최적화 문제로 변환해 보자. 먼저 등식 제약조건이 있는 경우다.

 

\[ \begin{align} & \min_{\mathbf{x}} f(\mathbf{x}) \tag{4} \\ \\ \mbox{subject to: } & h_j (\mathbf{x})=0, \ \ j=1, ..., k \end{align} \]

 

등식 제약함수의 지시함수는 다음과 같이 함수의 max 연산으로 표현 가능하다.

 

\[ \begin{align} I_j (h_j (\mathbf{x})) & = \begin{cases} 0, & \mbox{if } h_j (\mathbf{x})= 0 \\ \infty, & \mbox{if } h_j (\mathbf{x}) \ne 0 \end{cases} \tag{5} \\ \\ &= \max_{\lambda_j} \lambda_j h_j (\mathbf{x}) \end{align} \]

 

여기서 \(\lambda_j\) 는 일종의 패널티 함수(penalty function)에서의 패널티 항이라고 볼 수 있다. 식 (5)를 (3)에 대입하면 등식 제약조건이 있는 최적화 문제 (4)를 다음과 같이 minmax 문제로 바꿀 수 있다.

 

\[ \min_{\mathbf{x}}⁡ \max_{\lambda_j} f(\mathbf{x})+ \sum_{j=1}^k \lambda_j h_j (\mathbf{x}) \tag{6} \]

 

식 (6)은 등식 제약조건이 있는 최적화 문제를 minmax 문제로 정식화한 것이다. 한편, 라그랑지 곱수법(Lagrange multiplier)을 이용하면 등식 제약조건이 있는 최적화 문제를 다음과 같이 정식화 할 수 있었다.

 

\[ \min_{\mathbf{x}, \lambda_1, \lambda_2, ..., \lambda_k}⁡ f(\mathbf{x})+ \sum_{j=1}^k \lambda_j h_j (\mathbf{x}) \tag{7} \]

 

식 (6)과 (7)은 동일한 최적화 문제에 대한 두가지 관점으로 해석할 수 있다. 식 (6)에 있는 \(\lambda_j\) 도 식 (7)에서와 같이 라그랑지 곱수라고 한다.

 

 

부등식 제약조건이 있는 최적화 문제는 다음과 같다.

 

\[ \begin{align} & \min_{\mathbf{x}} f(\mathbf{x}) \tag{8} \\ \\ \mbox{subject to: } & g_i (\mathbf{x}) \le 0, \ \ i=1, ..., m \end{align} \]

 

마찬가지로 부등식 제약함수의 지시함수도 다음과 같이 함수의 max 연산으로 표현 가능하다.

 

\[ \begin{align} I_i (g_i (\mathbf{x})) & = \begin{cases} 0, & \mbox{if } g_i (\mathbf{x}) \le 0 \\ \infty, & \mbox{if } g_i (\mathbf{x}) \gt 0 \end{cases} \tag{9} \\ \\ &= \max_{\mu_i \ge 0} \mu_i g_i (\mathbf{x}) \end{align} \]

 

 

 

위 식에서 식 (5)와 차이점은 라그랑지 곱수 \(\mu_i\) 가 음수(마이너스)가 아니라는 조건이 있다는 것이다. 이것은 식 (9)를 지시함수로 만들기 위해 필요한 조건이다. 식 (9)를 (3)에 대입하면 부등식 제약조건이 있는 최적화 문제 (8)을 다음과 같이 minmax 문제로 바꿀 수 있다.

 

\[ \min_{\mathbf{x}}⁡ \max_{\mu_i \ge 0} f(\mathbf{x})+ \sum_{i=1}^m \mu_i g_i (\mathbf{x}) \tag{10} \]

 

최종적으로 식 (6)과 (10)을 이용하면 등식과 부등식 제약조건이 있는 일반적인 최적화 문제를 다음과 같이 제약조건이 없는 minmax 문제로 바꿀 수 있다.

 

\[ \min_{\mathbf{x}}⁡ \max_{\lambda_j , \ \mu_i \ge 0} f(\mathbf{x})+ \sum_{i=1}^m \mu_i g_i (\mathbf{x}) + \sum_{j=1}^k \lambda_j h_j (\mathbf{x}) \tag{11} \]

 

식 (11)의 함수를 라그랑지안(Lagrangian)이라고 한다.

 

\[ L(\mathbf{x}, \mu_1, ..., \mu_m, \lambda_1, ..., \lambda_k )= f(\mathbf{x})+ \sum_{i=1}^m \mu_i g_i (\mathbf{x}) + \sum_{j=1}^k \lambda_j h_j (\mathbf{x}) \tag{12} \]

 

식 (11)에서 min과 max의 순서를 바꾸면 다음과 같이 maxmin 문제가 된다.

 

\[ \max_{\lambda_j , \ \mu_i \ge 0} \min_{\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}) \tag{13} \]

 

식 (13)을 듀얼 문제(dual problem)라고 하고, 식 (11)을 프라이멀 문제(primal problem)라고 한다. 이 둘은 최적화 문제에 대한 두가지 관점을 보여주는데 어떤 문제에서는 프라이멀 문제보다도 듀얼 문제로 바꾸어서 푸는 것이 효과적일 수 있다. 프라이멀 문제와 듀얼 문제에 대한 논의는 다음 게시글을 참고하기 바란다.

 

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