Linear Programming Duality

관련 내용이 이 블로그에도 매우 잘 나와 있으니 같이 보면 좋을듯. 이 글에서는 LP에 대한 정의를 안다는 것을 가정하기 때문에, 정의를 모른다면 링크한 블로그를 참고해야 한다.

직관

다음과 같은 LP 문제를 생각해 보자.

$\text{Maximize: } 4x + 4y$

$\text{Subject to: } x + y \leq 3,x, y \geq 0 $

이 문제의 답은 굉장히 자명하다. $(x+y) \leq 3$ 이라는 조건이 있으니, $4(x+y) \leq 12$ 를 만족한다. 그 외에 다른 제약 조건은 $x, y \ge 0$ 뿐이니 답은 간단히 12로 결정된다.

이를 조금 더 어려운 예시로 바꿔보자.

$\text{Maximize: } 4x + y $

$\text{Subject to: } x+y \leq 2, 2x+y \leq 3, x, y \geq 0$

위 예시와 다르게 이 문제의 답은 자명하지 않다. 위 문제의 답이 자명할 수 있었던 것은, 제약 조건 항이 유일했으며 그것이 최적화 함수의 형태와 일치했기 때문이다. 지금의 경우에는 제약 조건의 항이 유일하지도 않으며, 최적화 함수와도 독립적이다.

LP Duality의 접근은, 이 식을 최대한 "당연하게" 만드는 것이다. 새로운 변수 $a, b$ 를 도입하자. 그러면, 다음과 같은 것이 성립한다. 이 때 $a, b \geq 0$ 임에 유의하자! 아니면 부등호가 바뀌어서 엉망이 된다.

$a(x + y) \leq 2a, b(2x+y) \leq 3b$

$(a + 2b)x + (a + b)y \leq 2a + 3b​$

직관적으로 생각했을 때, 이 수식을 "끼워맞춰서" $4x+y$ 로 만들기 위해서는 $a+2b = 4, a+b = 1$ 을 만족시켜야 한다. 하지만, 이를 모두 만족시키는 해는 존재하지 않는다. 즉, 이 경우에는 위와 같은 형태의 부등식을 즉각적으로 얻을 수는 없다. 하지만, $4x + 2y \leq 18, 5x + y \leq 18$ 와 같은 제약조건도 답의 상한을 찾기에는 충분히 도움이 되니, 위 제약 조건을 $a + 2b \ge 4, a + b \ge 1$ 로 바꾸자.

이 때 답의 상한을 최대한 낮춰서 많은 정보를 얻으려면, 우변의 항이 최소화되어야 한다. 그렇다면 이것 역시 LP 문제가 된다.

$\text{Minimize: } 2a + 3b $

$\text{Subject to: } a+2b\ge 4, a+b\ge 1, a, b \geq 0$

이 LP를 손으로 풀어보면 $a = 0, b = 2$ 임을 알 수 있다. 이 때 $2a + 3b = 6$ 이므로, 이제 우리는 원래 LP 문제의 답은 적어도 6보다는 작다는 것을 알 수 있다. 실제로 원래 LP를 풀어보면, $x = 1.5, y = 0$ 을 대입하여 답이 정확히 6인 해를 얻을 수 있고, 그것보다 더 큰 해를 얻을 수는 없다.

우리가 지금까지 한 과정은 LP Duality 개념을 손으로 유도해낸 것이다. 원래 형태의 문제를 Primal 문제, 변형된 형태의 문제를 Dual 문제라고 부르자. 우리는 Primal 문제에서, 답에 대한 상한을 찾기 위해 계수를 맞춰주는 방식으로 Dual 문제를 직접 유도해 냈다. 그리고 이 과정에서 새로운 결론을 얻어냈는데, Primal 문제의 답은 Dual 문제보다 작거나 같다는 것이다. 이러한 결론을 Weak Duality 라고 부른다. 보다시피, Weak Duality는 자명한 과정만을 거쳐서 도입할 수 있기 때문에 정당성도 자명하다. 이보다 더 강한 명제인 Strong Duality 는, 더 나아가서 Primal 문제의 답이 Dual 문제의 답과 같다는 명제이다. Strong Duality는 참이고, 그 증명은 자명하지 않다. 관심이 있다면 이 링크를 참고.

일반화와 결론

위의 예시는 특수한 경우에 불과하니, 이를 일반적인 경우로 바꾼다. 다음과 같은 LP 문제를 생각해 보자.

$\text{Maximize: } c^Tx$

$\text{Subject to: } Ax \leq b, x \geq 0$

$\sum_{1 \leq i \leq n}{(y_i \times A_{i, j} )\geq c_j}$앞서 말한 Dual Problem이라는 것은, $Ax \leq b$ 라는 식을 이루는 각 행 벡터에 대해 적당한 선형 결합을 찾아서. 그 값을 $c^Tx$ 보다 크게 하는 것이었다. 다시 한번 이거를 시도해 보자. $i$ 번째 행에 대해서 그 항에 붙일 계수를 $y_i$ 라고 하자. 그러면, 모든 열 $j$ 에 대해서 다음이 성립한다.

$\sum_{1 \leq i \leq n}{(y_i \times A_{i, j} )\geq c_j} \text{ for all }j \implies$ $A^T_{j} \times y \geq c_j \text{ for all }j \implies$ $A^Ty \geq c, y \geq 0$\

각 $y_i$ 에 대해서 계수로 붙었던 것은 $b_i$ 였다. 고로, 최소화해야 할 대상은 $b^Ty$ 이다. 이제 위 Primal 문제에 대응되는 Dual 문제를 다음과 같이 정의할 수 있다.

$\text{Minimize: } b^Ty$

$\text{Subject to: } A^T y \geq c, y \geq 0$

그리고, Strong Duality 에 의해, Primal 문제의 최댓값과 Dual 문제의 최솟값은 동일하다.

몇 번 문제를 풀어보다 보면 알겠으나, 사실 위 식과 아래 식은 아주 비슷하다. Max 문제를 풀다가 안 풀릴 때는, 풀고 있던 종이를 뒤집어 버리자. 행렬도 돌아가고, $b, c$ 벡터도 돌아가고. 이제 거기서 minimization을 그냥 그대로 풀면 Dual 문제가 되는 것이다. 또 하나의 결론은, Dual Problem을 똑같은 과정으로 변환하면 다시 Primal Problem이 된다는 것이다. 고로 Dual의 Dual은 Primal.

알아두면 쓸데있는 잡지식

$x \geq 0$ 조건이 강제되는 게 걸릴 수 있는데, 저것이 문제라면 양수와 음수를 쪼개는 식의 테크닉을 사용하자. 정확히는, 변수 $x^{+}_i, x^{-}_i$ 를 만든다. $x_i = x^{+}_i - x^{-}_i$ 로 전부 대체해주고, $x^{+}_i, x^{-}_i \geq 0$ 을 적어주자. 그러면 저 조건이 없는 상황에서도 항상 이를 강제시킬 수 있다.

Convex Hull Trick의 모티베이션이 된 point-line duality 랑은 다른 개념이다.

연습 문제

꼭 Duality를 알아야만 풀 수 있는 문제는 많지 않지만, Duality를 사용하면 굉장히 깔끔하게 생각할 수 있는 문제들이 많다.

다음 세 문제는 Duality를 사용하면 바로 기하 문제로 환원할 수 있는 문제들이다. 안 쓰고 안 풀어봐서 모르겠는데, 내가 옛날에 335C 풀었을 때를 생각해 보면 그닥 쉽지 않았던 것 같다..

• CF Div1 335C. Freelancers Dreams
• JAG Autumn 2014. Flowers
• ICPC Pacific NW 2018. Mobilization

다음 문제는 Primal, Dual 모두 효율적인 풀이가 있으나 Dual의 관점에서 생각하는 게 훨신 더 빠르게 풀 수 있는 문제이다. 이 문제에 대해서 이 곳에 적었다.

• Topcoder SRM 744. CoverTreePaths

다음 두 문제는 Duality를 사용하지 않으면 simplex algorithm이 필요해서 TLE가 나지만, Duality를 사용하면 Min-cost flow로 환원되어서 풀 수 있는 문제들이다.

• BOJ 1281. 보석상
• JAG Autumn 2015. Longest Shortest Path