Lagrange Multiplier 로 유도해보는 dual

공식을 써보지 않고 Lagrange Multiplier Method 에 대한 선행 지식만 가지고 있다고 가정한 채 dual 을 유도해볼 것이다. 과정을 한번 따라 써보면 dual에 대해 다른 관점으로 이해할 수 있을 것이다.

아래는 LP minimization 문제의 standard form 이다.

$\min c'x$
s.t. $Ax = b$
$x \geq 0$

이러한 LP 문제를 보면 가장 먼저 궁금해져야하는 것이 각 벡터와 행렬의 차원이다. c, x 는 n 차원의 벡터이며 A는 m x n 행렬, b는 m 차원의 벡터이다. c와 x 벡터를 내적해주기 위해 그냥 c 벡터가 아니라 $c'$를 사용한다. 참고로 $c'$는 c벡터를 transpose 한 $c^T$를 의미한다.

지금 우리가 풀려고 하는 문제처럼 어떤 제약식 하에서 어떤 수식을 최소화하는 문제를 풀기 위해서는 라그랑주 승수법(Lagrange Multiplier Method)의 도입을 고려해볼 수 있다.

$\min_x c'x+p'(b-Ax)$
단, $x \geq 0$

여기서의 p’는 Lagrange Multiplier 이다. 라그랑주 승수법을 처음 들어봤더라도 p벡터를 패널티라 생각하면 쉽게 이해할 수 있다. p를 어떤 양의 벡터로 설정한다면 우리는 목적 함수 전체를 최소화 하기 위해 $c'x$, $b-Ax$ 각각을 최소화하려고 할 것이고 이 문제에서 $b-Ax$가 0이되면 우리의 제약식을 만족하는 셈이 될 것이다. $b-Ax=0$ 제약식을 반드시 만족해야했던 본래 문제와 달리 바뀐 문제에서는 제약식의 조건이 완화된 셈이다. 따라서 목적함수를 최소화하는 $x$를 $x^*$이라 하면
$\min_x c'x+p'(b-Ax) \leq c'x^*$
를 만족한다. 우리의 새로운 목적함수는 원래 문제의 최적해의 lower bound 인 셈이다.

자 이제 목적 함수를 전개해서 조금 다른 관점으로 살펴보자.
$\min_x c'x+p'(b-Ax)$
$=\min_x c'x+p'b- p'Ax$
$=\min_x p'b+(c'-p'A)x$
min 안에 있는 항 중 $p'b$는 최소화하려는 $x$ 와 상관이 없으므로 밖으로 꺼내쓸 수 있다.
$p'b+\min_x(c'-p'A)x$

우리가 다루고 있는 새로운 LP는 본래 문제의 lower bound 라 했으므로 본래 문제의 최적해를 찾기 위해서는 lower bound를 최대화 시키면 된다. 따라서 목적함수에 max 까지 취해주면 본래의 LP 문제와 완전히 동치가 되며 아래의 수식은 본래 문제(primal)와 동치이지만 관점이 다른 dual 문제이다.

$\max_p\{p'b+\min_x(c'-p'A)x\}$

이 dual 문제에 조건식은 어떻게 돼야할지 생각해보자. $x \geq 0$라는 사실은 이미 알고 있으므로 $c'-p'A$의 부호에 따라 최적값이 어떻게 달라지는지 살펴보자. $c'-p'A \geq 0$라면 $\min_x(c'-p'A)x$는 0 혹은 양수의 어떤 값을 가질 것이다. 하지만 $c'-p'A < 0$라면 $-\infty$의 값을 가지며 우리는 이 상황에는 관심이 없다 ($-\infty$를 최대화 시키는 것은 의미가 없으므로). 이렇게 $c'-p'A \geq 0$라는 조건식이 생기며 min 항은 어떤 특정 상수로 귀결되므로 무시할 수 있다. 최종적으로 깔끔하게 다시 써준 dual 문제는 다음과 같다.

$\max_pp'b$
s.t.
$p'A \leq c'$