듀얼 문제 (Dual Problem)

최적화 이론에서 쌍대성(Duality)은 최적화 문제를 원초 문제(Primal problem)와 듀얼 문제(Dual problem)로 바라볼 수 있다는 원칙입니다. 예를 들어 아래와 같이 제약식 $f_i(x)$와 $h_i(x)$를 만족하는 목적함수 $f_0(x)$의 최솟값을 찾으려고 합니다.

$$\begin{aligned} \underset{x}{min} \text{ }\text{ }\text{ }\text{ }\text{ } & f_0(x) \\ subject \text{ }to \text{ }\text{ }\text{ }\text{ }\text{ } & f_i(x) \le 0 (i = 1, ..., m) \\ & h_i(x) = 0 (i = 1, ..., p) \end{aligned}$$

위와 같은 원초 문제의 듀얼 문제를 라그랑주 승수법을 이용해 찾을 수 있습니다. 위 식의 목적 함수와 제약식을 라그랑주 승수법의 보조 함수 형태로 바꾸어 보겠습니다.

$$L(x, \lambda, \mu) = f_0(x) + \sum_i \lambda_i f_i(x) + \sum_i \mu_i h_i(x) \text{ }\text{ }\text{ }\text{ }\text{ } (\lambda \ge 0)$$

보조함수 $L$의 형태를 자세히 보면 목적함수 $f_0(x)$에 나머지 항들을 더하는 형태를 가집니다. 나머지 항들 $\sum_i \lambda_i f_i(x) + \sum_i \mu_i h_i(x)$을 살펴보겠습니다. $\sum_i \lambda_i f_i(x)$의 경우 $f_i(x)$는 항상 0보다 작고 $\lambda$는 0보다 크므로 $\sum_i \lambda_i f_i(x)$ 는 0보다 작습니다. $\sum_i \mu_i h_i(x)$ 항은 $h_i(x)$가 항상 0이므로 $\sum_i \mu_i h_i(x)$ 역시 0입니다. 따라서 $f_0$의 최솟값을 만족하는 미지수 $x$를 $x^*$라 할 때 다음이 성립합니다.

$$f(x^*) \ge L(x^*, \lambda, \mu) \ge \underset{x}{inf}\text{ }L(x, \lambda, \mu)$$

위 부등식에서 $inf$는 정해진 범위내에서의 최대 하한(infimum)을 뜻합니다. $\underset{x}{inf}\text{ }L(x, \lambda, \mu)$을 $g(\lambda, \mu)$라 하면 목적 함수의 최솟값을 찾는 문제는 $g(\lambda, \mu)$의 최댓값을 찾는 문제로 바뀝니다. 이 때 $g(\lambda, \mu)$를 듀얼 문제라 합니다. 제약식 중 부등식은 항상 0보다 작거나 같은 형태를 갖고 대응하는 라그랑주 승수($\lambda$)는 0보다 크거나 같습니다. 듀얼 문제는 다음과 같이 쓸 수 있습니다.

$$\begin{aligned} \underset{x}{max} \text{ }\text{ }\text{ }\text{ }\text{ } & g(\lambda, \mu) \\ subject \text{ }to \text{ }\text{ }\text{ }\text{ }\text{ } & \lambda_i \ge 0 (i = 1, ..., m) \end{aligned}$$

듀얼 문제를 선형 계획법에 적용시켜 보겠습니다. 아래와 같은 원초 문제가 있습니다.

$$\begin{aligned} \underset{x}{min} \text{ }\text{ }\text{ }\text{ }\text{ } & c^T x \\ subject \text{ }to \text{ }\text{ }\text{ }\text{ }\text{ } & Ax + b \le 0 \\ & Gx + h = 0 \end{aligned}$$

원초 문제의 듀얼 문제를 만들기 위해 라그랑주 승수법을 이용하겠습니다.

$$L(x, \lambda, \mu) = c^T x + \lambda^T(Ax + b) + \mu^T(Gx + h)$$

보조 함수에 대한 식 $\underset{x}{inf}\text{ }L$을 만들기 위해 $L$을 $x$에 대한 식으로 바꾸어 보겠습니다.

$$\begin{aligned} L(x, \lambda, \mu) & = c^T x + \lambda^T(Ax + b) + \mu^T(Gx + h) \\ & = \lambda^T b + \mu^T h + (\lambda^T A + \mu^T G + c^T)x \\ & = b^T \lambda + h^T \mu + (A^T \lambda + G^T \mu + c)^Tx \end{aligned}$$

구하고 싶은 듀얼문제는 $\underset{x}{inf}\text{ }L$이므로 듀얼 문제 $g(\lambda, \mu)$를 아래와 같이 쓸 수 있습니다.

$$\begin{aligned} g(\lambda, \mu) = \underset{x}{inf}\text{ }L(x, \lambda, \mu) & = b^T \lambda + h^T \mu + \underset{x}{inf}\text{ }(A^T \lambda + G^T \mu + c)^Tx \end{aligned}$$

이 때 $x$와 관련된 항 $\underset{x}{inf}\text{ }(A^T \lambda + G^T \mu + c)^Tx$은 계수 벡터 $A^T \lambda + G^T \mu + c$가 양수일 경우 $x$값이 무한히 작아지면 음의 무한으로 발산합니다. 계수 벡터가 음수일 경우 $x$값이 무한히 커질 때 음의 무한으로 발산합니다. 따라서 계수 벡터에 대한 식 $A^T \lambda + G^T \mu + c = 0$ 이어야 하는 듀얼 문제의 제약식을 얻습니다. 그리고 $b^T \lambda + h^T \mu$ 는 원초 문제의 목적 함수의 최대 하한입니다. 아래는 위의 선형계획법 문제로 부터 구한 듀얼 문제입니다.

$$\begin{aligned} \underset{x}{max} \text{ }\text{ }\text{ }\text{ }\text{ } & b^T \lambda + h^T \mu \\ subject \text{ }to \text{ }\text{ }\text{ }\text{ }\text{ } & \lambda \ge 0 \\ & A^T \lambda + G^T \mu + c = 0 \end{aligned}$$

출처 및 참고

• www.youtube.com/watch?v=pJsekSDXDlU
• ratsgo.github.io