선형계획법에서의 듀얼
빌드업
$x_{1} , x_{2} \ge 0$ 에 대해 다음과 같은 선형계획문제가 주어져 있다고 하자. $$ \begin{matrix} \text{Maximize} & & 2x_{1} & + & 3x_{2} \\ \text{subject to} & & 4x_{1} & + & 8x_{2} & \le & 12 \\ & & 2x_{1} & + & x_{2} & \le & 3 \\ & & 3x_{1} & + & 2x_{2} & \le & 4 \end{matrix} $$
우리의 목표는 주어진 제약조건 아래에서 목적 함수 $\zeta = 2x_{1} + 3x_{2}$ 를 최대로 하는 최적해 $x_{1}^{\ast}, x_{2}^{\ast}$ 를 구하는 것이긴 하다. 그런데 식을 잘 보면 문제를 안 풀어봐도 최대값의 상한이 있다는 사실을 알 수 있다. 첫번째 제약조건에서, $$ 2x_{1} + 3x_{2} \le 4x_{1} + 8x_{2} \le 12 $$ 이고, 사실 $4x_{1} + 8x_{2} \le 12$ 의 양변을 $2$ 로 나누면 $$ 2x_{1} + 3x_{2} \le 2x_{1} + 4x_{2} \le 6 $$ 이므로 목적 함수의 값은 아무리 커도 $6$ 임을 알 수 있다. 그 뿐만이 아니다. 두번째 제약조건까지 생각해보면 $$ 2x_{1} + 3x_{2} = {{ 1 } \over { 3 }} \left( 4x_{1} + 8x_{2} + 2x_{1} + x_{2} \right) \le {{ 1 } \over { 3 }} (12 + 3) = 5 $$ 와 같이 상한을 더 줄일 수도 있다. 다시 말해 $$ d_{1} x_{1} + d_{2} x_{2} \le h $$ 과 같은 부등식이 있을 때, 이 $h$ 를 줄여나가는 접근법을 생각해볼 수 있다는 것이다. 목적 함수부터가 바운드되어 있으니 이렇게 상한을 계속 줄이다보면 더 이상 못 줄이는 때, 그러니까 상한의 최솟값을 찾는 때가 올텐데 잘 생각해보면 이 상한을 줄인다는 것부터가 또 다른 최적화 문제기도 하다. 직관적으로 보았을 때 원래의 최대화 문제를 풀든 상한의 최소화 문제를 풀든 같은 결론에 도달할 수 있을 것 같다.
특히 $d_{1} x_{1} + d_{2} x_{2} \le h$ 의 형태는 ‘또 다른 어떤 선형계획문제’의 제약조건처럼 보이기도 한다. 이에 따라 다음과 같이 그 ‘다른 어떤 선형계획문제’를 정의한다.
정의 1
$$ \begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} \le \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix} $$
행렬 $A \in \mathbb{R}^{m \times n}$ 과 $\mathbf{b} \in \mathbb{R}^{m \times 1}$ 와 $\mathbf{c} \in \mathbb{R}^{n}$ 에 대해 선형계획문제가 위와 같이 주어져 있다고 하자.
- 위 문제에 대응되는 상한의 최소값을 찾는 다음의 선형계획문제를 듀얼 선형계획문제dual Linear Program라 한다. $$ \begin{matrix} \text{Minimize} & \mathbf{b}^{T} \mathbf{y} \\ \text{subject to} & A^{T} \mathbf{y} \ge \mathbf{c} \\ & \mathbf{y} \ge \mathbf{0} \end{matrix} $$
- 듀얼 선형계획문제에 대비되는 표현으로써, 주어졌던 원래의 최대화 문제를 프라이멀 선형계획문제primal Linear Program이라 한다.
설명 2
듀얼과 프라임의 풀이를 시각적으로 나타내보면 위와 같다. 프라이멀 문제는 아래에서 위로 목적 함수를 최대화해가며, 듀얼 문제는 위에서 아래로 상한을 내려와서 해의 공간을 줄여나간다. 그 둘이 정확히 같아졌을 때, 우리는 의심의 여지 없이 그것이 최적해임을 납득할 수 있을 것이다.
쌍대성이란?
쌍대성duality이란 수학 전반에서 보편적으로 등장하는 개념으로써, 함수해석에서의 쌍대 공간이나 기하적 쌍대 그래프 등과 같이 대칭symmetric과 비슷하되 한차원 높은 추상화 수준의 성질을 총칭한다.
같이보기
선형계획법에서의 쌍대성
최적화를 전공할 게 아니라 한 과목으로 다룬다면 선형계획법은 심플렉스 메소드와 쌍대성 이 두가지만 배우면 모든 걸 다 배운 것이다. 물론 그 둘 뿐이라고해서 딱히 그 과정이 쉽다는 말은 아니다.
심플렉스 메소드가 구체적인 그 방법에 대해 논한다면, 쌍대성은 프라이멀 문제에 대해 듀얼 문제가 존재하고, 그 최적해가 서로 같다는 식의 다분히 이론적인―순수수학적인 논의다. 이는 다음의 쌍대성 정리들로 보장된다.
약한 쌍대성 정리
$$ \sum_{j=1}^{n} c_{j} x_{j}^{\ast} \le \sum_{i=1}^{m} b_{i} y_{i}^{\ast} $$
강한 쌍대성 정리
$$ \sum_{j=1}^{n} c_{j} x_{j}^{\ast} = \sum_{i=1}^{m} b_{i} y_{i}^{\ast} $$