Duality 변환 공식 암기하지말고 이해하기

Duality 변환 공식

선형계획법에서 Duality 에 대해 배우다보면 아래와 같은 dual 변환 공식을 종종 접한다.

다음과 같이 규칙 기반으로 표를 외우는 방법도 있다.

1. 한쪽 문제의 equality constraints는 다른쪽 문제의 free variables 과 대응된다.
2. minimize 문제의 constrainst 와 그의 dual 인 maximize 문제의 variables 의 부호는 같다.
3. minimize 문제의 variables 과 그의 dual 인 maximize 문제의 contraints 부호는 다르다.

하지만 왜 꼭 이렇게 되어야만 하는것인지 규칙에 숨겨진 원리를 당위적으로 이해하고 싶은 사람이라면 아래 예제를 살펴보자.

다음 LP 예제를 살펴보자
$\min x_1+3x_2$
s.t.
$x_1+x_2\geq 2$
$x_2\geq1$

선행 지식이 없어도 이 문제를 푸는 것은 쉽다. 두번째 제약식에 2를 곱한다음 첫번째 제약식에 더해주면 $x_1+3x_2 \geq 4$를 얻을 수 있다. 이를 lower bound 라하며 최소값은 자연스럽게 4로 구해진다.

이렇게 자연스럽게 진행된 과정의 숨겨진 의미를 한번 살펴보자. 우리는 주어진 제약식을 선형 결합해서 목적함수를 만들 수 있는지를 살펴보았다. 첫번째 제약식에 $p_1$을 곱하고 두번째 제약식에 $p_2$를 곱한다 했을때 $x_1$ 관점에서는 $p_1 =1$, $x_2$ 관점에서는 $p_1 + p_2=3$, 이렇게 두 식을 만족하는 $p_1, p_2$ 값을 찾은 것이고 그것이 곧 아까 제약식에 곱한 $p_1=1, p_2=2$ 이다.

우리가 제약식에 곱할 $p_1, p_2$를 찾을때 자연스럽게 고려하지 않는 것이 있다. 바로 음수이다. 음수를 곱하면 부등호의 방향이 뒤바뀌기 때문에 lower bound를 찾으려는 우리의 목적에 맞지 않다. (부등호의 방향이 $\geq$ 가 아니라 $\leq$로 주어졌더라면 음수만 고려했을 것이라는 사실도 자연스럽게 알 수 있다.)

따라서 이 문제의 dual 은 다음과 같다.
$\max p_1+p_2$
s.t.
$p_1 =1$
$p_1 + p_2=3$
$p_1, p_2 \geq 0$

이 문제에 해당하는 공식을 아까 표에서 찾아보면 성립하는 것을 쉽게 확인할 수 있다.

이제 LP를 조금 변형해보자. 제약식의 부등호를 등호로 바꾸어보았다.
$\min x_1+3x_2$
s.t.
$x_1+x_2 = 2$
$x_2 = 1$

더 이상 등식의 방향을 신경쓸 필요가 없기 때문에 dual 에서 $p$가 양수라는 조건이 필요치 않아진다.

아까 표에서 찾아 성립하는지 확인해보자.

LP를 한번 더 변형해보자. $x$가 0 이상이여야 한다는 조건을 추가해보았다. 설명의 용이성을 위해 제약식 하나를 없앴다.
$\min x_1+3x_2$
s.t.
$x_1+x_2 = 2$
$x_1, x_2 \geq 0$

또 어떤 변화가 생길까? $p$를 찾음에 있어 꼭 목적함수의 계수와 딱 맞는 선형결합식을 찾을 필요가 없어졌다.
$x_1+3x_2 > x_1+x_2$ 라는 조건을 주기 때문에 목적함수의 계수보다 같거나 작은 선형 결합식을 찾아주기만 하면 된다. (x가 음수였다면 반대 부호의 관계가 성립했을 것이라는 사실도 자연스럽게 알 수 있다.) dual 은 다음과 같다.

$\max p_1+p_2$
s.t.
$p_1 \leq 1$
$p_2 \leq 3$

역시나 표에서 찾아보면 성립하는 것을 확인할 수 있다.

이렇게해서 표에 제시된 총 6개 쌍을 하나하나 따라가보며 전부 이해해보는 과정이 완료되었다.