[선형 계획법] 쌍대성(Duality)
Linear programming은 최적화 분야에서 잘 알려지고 연구되었으며 실제로도 많이 응용되는 기법입니다. 줄여서 LP라고도 하며, 우리말로는 선형계획법으로 불립니다. 이름이 뭔가 멋들어져서 괜스레 어렵게 느껴질 수도 있겠습니다만, 사실 별것 아닙니다. 고등학교 수학 시간에 다음과 같은 문제를 풀어보신 적이 있을 겁니다.
여러분은 빵집 사장님입니다. 식빵과 크루아상, 두 종류의 빵을 팔고 있습니다. 식빵 1kg을 만들기 위해서는 밀가루 5kg, 설탕 3kg이 필요하고 크루아상 1kg을 만들기 위해서는 밀가루 2kg, 설탕 5kg이 필요하다고 합시다. 1kg 당 식빵과 크루아상의 가격은 같습니다. (저는 제빵을 잘 모릅니다. 수치는 그저 예시일 뿐입니다.) 하루에 밀가루 20kg, 설탕 15kg이 들어온다고 합니다. 장사가 아주 잘 돼서 만든 빵이 모두 판매된다고 할 때, 과연 각각의 빵을 얼마큼 만들어야 할까요?
위 문제는 다음과 같은 식으로 간단히 해결할 수 있습니다. 생산할 식빵의 kg 수를 \(x\), 크루아상의 kg 수를 \(y\)라고 하겠습니다. 일단, 빵을 0kg보다 적게 생산할 수는 없으므로 \[x \geq 0, \quad y \geq 0\]이 성립해야 합니다. 밀가루는 \(5x + 2y\) (kg) 필요합니다. 하루에 20kg의 밀가루가 들어온다고 하였으므로 \(x\)와 \(y\)는 \[5x+2y \leq 20\]를 만족해야 합니다. 비슷하게 설탕에 대해서도 생각해보면, \[3x + 5y \leq 15\]를 만족해야 합니다. 두 종류의 단위 가격은 동일하므로 우리는 \(x+y\)가 최대가 되는 지점을 찾으면 됩니다. 고등학교 때 직교 좌표계를 그려서 열심히 꼭짓점을 찾았던 기억이 나네요.
더도 말고 덜도 말고 딱 위와 같은 최적화 방법을 linear programming이라고 합니다. 좀 더 엄밀히 말씀을 드리자면, 주어지는 linear constraint(선형 조건)를 모두 만족하면서 함께 주어지는 linear function(선형 함수)을 최적화시키는 것입니다. 이때 linear constraint는 equality constraint와 inequality constraint 두 가지가 있습니다. 최적화시키려는 함수를 objective function(목적 함수)라고 부릅니다. 위의 예시는 다음과 같이 나타낼 수 있게 됩니다.
\[ \begin{array}{lrcl} \text{maximize } & x + y & & \\ \text{subject to } & 5x + 2y & \leq & 20, \\ & 3x + 5y & \leq & 15, \\ & x & \geq & 0, \\ & y & \geq & 0. \end{array} \]
간략하게 설명한다는 것이 약간 길어졌군요. 일단 이번 포스팅의 주제는 LP 그 자체가 아니어서 LP에 대한 설명은 이정도로만 하겠습니다. 제목에서 알 수 있다시피 포스팅의 주된 주제는 LP duality입니다. 네이버에 "LP duality"로 검색을 해 보니 우리말로 된 웹문서가 두어 개 정도 나오더군요. 모두 잘 설명이 되어있었습니다만, LP가 가진 효용과 재미에 비해서는 그 수가 너무 적다고 생각했습니다. 또, 앞으로 제가 포스팅하고자 하는 내용에서도 duality는 매우 많이 쓰일 것이 분명하기에 저도 한 번 적어보고자 합니다. 참고로 Williamson and Shmoys의 「The design of approximation algorithms」의 Appendix A를 참조하였음을 알려드립니다. (무료로 온라인 버전을 배포하였습니다. 관심 있으신 분들은 http://www.designofapproxalgs.com/로 가시기 바랍니다.)
일단 우리를 도와 줄 linear program을 하나 가지고 오겠습니다.
\[ \begin{array}{lrcl} \text{minimize } & 6 x_1 + 4 x_2 + 2 x_3 & & \\ \text{subject to } & 4 x_1 + 2 x_2 + x_3 & \geq & 5, \\ & x_1 + x_2 & \geq & 3, \\ & x_2 + x_3 & \geq & 4, \\ & x_1, x_2, x_3 & \geq & 0. \end{array} \]
위 program의 목표는 주어진 linear constraint를 모두 만족하면서 \(6 x_1 + 4 x_2 + 2 x_3\)를 최소화시키는 것입니다. 근데 잘 살펴보면 한 가지 재밌는 사실을 발견할 수 있습니다. 첫 번째 constraint의 계수가 objective function의 계수보다 모두 작다는 점입니다. 이는, \(x_1, x_2, x_3\)이 모두 음수가 아니라는 조건과 함께,
\[6 x_1 + 4 x_2 + 2 x_3 \geq 4 x_1 + 2 x_2 + x_3 \geq 5\]
라는 사실을 도출합니다. 여기서 우리는 아무리 \(x_1, x_2, x_3\)에 적절한 수를 넣어봤자 objective function이 5보다는 작은 값을 가질 수가 없다는 사실을 알 수 있습니다.
5라는 lower bound(하한)를 얻은 것은 매우 고무적인 일입니다만 아무래도 우리는 이보다 더 잘할 수 있을 것입니다. 아직 계수를 더 증가시킬 수 있는 여지가 충분하기 때문입니다. 다른 linear constraint와 함께 조합한다면 어떻게 될까요? 이번에는 첫 번째 constraint는 그대로 가져오고, 두 번째 constraint는 2를 곱해서 가져와 보겠습니다. 그러면 위와 비슷한 방식으로 다음을 이끌어낼 수 있습니다.
\[6 x_1 + 4 x_2 + 2 x_3 \geq (4 x_1 + 2 x_2 + x_3) + 2 \cdot (x_1 + x_2) \geq 11\]
똑같이, \(x_1, x_2, x_3\)는 모든 constraint를 만족해야 하므로, objective function은 아무리 작아져도 11보다 작아질 수 없다는 사실을 알 수 있습니다.
이러한 것들을 발견하고 나면 자연스럽게 따라오는 질문은 주어지는 linear constraint를 어떻게 잘 조합하면 "가장 좋은" lower bound를 얻을 수 있을까일 것입니다. 이것이 바로 LP duality의 시작점입니다. 위의 linear program을 좀 더 어렵게 바꿔보도록 하겠습니다.
\[ \begin{array}{lrcl} \text{minimize } & 6 x_1 + 4 x_2 + 2 x_3 & & \\ \text{subject to } & 4 x_1 + 2 x_2 + x_3 & \geq & 5, \\ & x_1 + x_2 & \leq & 3, \\ & x_2 + x_3 & = & 4, \\ & x_1 & \geq & 0, \\ & x_2 & \leq & 0, \\ & (x_3 & \text{is} & \text{free}). \\ \end{array} \]
복잡하게 바뀌어도 정의에 따른다면 엄연한 linear program입니다. 참고로, 현재 \(x_3\)는 아무 값이나 가져도 괜찮다는 의미입니다. 즉, 양수도 될 수 있고, 음수도 될 수 있습니다.
위에서 논의한 대로 주어진 linear constraint에 적당한 값을 곱하고 이들을 더하여 objective function의 유효한 lower bound 중 가장 좋은 것을 만드는 것이 목표입니다. Constraint에 곱해질 숫자를 위에서부터 각각 \(y_1, y_2, y_3\)라고 하겠습니다. 일단, \(x_1 \geq 0\), \(x_2 \leq 0\) \((, x_3 \text{ free}) \)일 때,
\[ 6 x_1 + 4 x_2 + 2 x_3 \geq y_1 \cdot (4 x_1 + 2 x_2 + x_3) + y_2 \cdot (x_1 + x_2) + y_3 \cdot (x_2 + x_3) \]
가 항상 만족을 해야 합니다. 이때, 처음 주어진 program의 constraint를 이용하면 다음과 같이
\[ y_1 \cdot (4 x_1 + 2 x_2 + x_3) + y_2 \cdot (x_1 + x_2) + y_3 \cdot (x_2 + x_3) \geq 5 y_1 + 3 y_2 + 4 y_3 \]
우변에 한 차례 더 lower bound를 줄 수 있게 됩니다. 하지만 이는 아무 \(y_1\), \(y_2\), \(y_3\)에 대해서 성립하는 것이 아닙니다. 이를 항상 만족하는 \(y_1\), \(y_2\), \(y_3\)를 찾아봅시다. 일단 \(4 x_1 + 2 x_2 + x_3 \geq 5\)이므로 위 식이 계속 만족하려면 \(y_1 \geq 0\)이 되어야 합니다. 음수가 되면 부등호의 방향이 바뀔 거니까요. 다음은 \(x_1 + x_2 \leq 3\)입니다. 따라서 \(y_2 \leq 0\)으로 만들어서 부등호 방향을 바꿔주어야 원하는 결과를 얻을 수 있습니다. 마지막으로 \(x_2 + x_3 = 4\)입니다. 따라서 \(y_3\)가 어떤 값을 가지든 좌변과 우변 각각에 \(y_3\)가 딸린 항은 크기가 같습니다. 정리하면, \(y_1\), \(y_2\), \(y_3\)는
\[y_1 \geq 0, \quad y_2 \leq 0, \quad y_3 \text{ free}\]
를 만족해야 합니다.
아직 끝나지 않았습니다. 이번에는 우변을 다음과 같이 정리해보겠습니다.
\[ 6 x_1 + 4 x_2 + 2 x_3 \geq x_1 \cdot (4 y_1 + y_2) + x_2 \cdot (2 y_1 + y_2 + y_3) + x_3 \cdot (y_1 + y_3) \]
우변을 그냥 다시 정리한 것 뿐입니다. 여기서도 우리는 주어지는 \(x_1\), \(x_2\), \(x_3\)에 대해서 항상 위 식을 만족하게 하는 \(y_1\), \(y_2\), \(y_3\)의 조건을 구할 수 있습니다. 먼저 \(x_1\)을 살펴보겠습니다. 이 변수는 0보다 크거나 같은 수를 가집니다. 따라서 식이 항상 만족하려면
\[6 \geq 4 y_1 + y_2\]
를 만족해야 합니다. 다음으로, \(x_2 \leq 0\)이기 때문에, 식이 항상 만족하기 위해서는
\[4 \leq 2 y_1 + y_2 + y_3\]
가 되어야 합니다. 마지막으로 \(x_3\)는 아무 값이나 가질 수 있습니다. 따라서 부등호를 계속 유지하기 위해서는
\[2 = y_1 + y_3\]
밖에 방법이 없습니다.
앞에서 얻은 결과들을 한 데 모아 식을 써보면 우리는 다음과 같은 새로운 linear program을 얻을 수 있게 됩니다.
\[ \begin{array}{lrcl} \text{maximize } & 5 y_1 + 3 y_2 + 4 y_3 & & \\ \text{subject to } & y_1 & \geq & 0, \\ & y_2 & \leq & 0, \\ & (y_3 & \text{is} & \text{free}), \\ & 4 y_1 + y_2 & \leq & 6, \\ & 2 y_1 + y_2 + y_3 & \geq & 4, \\ & y_1 + y_3 & = & 2.\end{array} \]
이 program의 objective가 최대화인 이유는 현재 우리의 목표가 원래 program의 objective function에 유효한 lower bound 중에서 가장 좋은, 즉 가장 큰 값을 찾는 것이기 때문입니다. 우리는 이렇게 구한 program을 원래 program의 dual program이라고 합니다. 이에 대응하도록 처음 주어지는 program을 primal program이라고 부릅니다.
Dual program은 여러 가지 재미있고 유용한 성질을 가지고 있습니다. 앞에서 우리는 primal (minimization) program의 constraint를 모두 만족하는 feasible한 solution에 대해서 dual (maximization) program은 항상 lower bound를 형성한다는 것을 유추할 수 있습니다. 왜냐면 우리가 그렇게 되도록 dual program에 constraint를 넣었기 때문입니다. 우리는 이 성질을 weak duality라고 부릅니다.
Weak duality
어떤 linear (minimization) program의 feasible solution이 이루는 objective function의 값은 그것의 dual program의 feasible solution이 이루는 objective function의 값보다 항상 크거나 같다.
그리고 놀랍게도! 두 program의 optimal solution이 이루는 값은 항상 동일합니다.
Strong duality
어떤 linear program과 그것의 dual program이 주어졌을 때, 각각의 optimal solution이 이루는 objective function의 값은 항상 같다.
이를 증명하는 것은 훨씬 어렵다고 합니다. 당장에 제가 참조한 책에서도 증명이 적혀있지는 않았습니다. 기회가 되면 따로 공부해서 포스팅할 수 있기를 바랍니다.
Strong duality를 통해서 우리는 새로운 사실을 발견할 수 있습니다. 앞의 예시를 다시 가지고 오겠습니다. Primal program의 optimal solution을 \(x^\star\), dual의 optimal solution을 \(y^\star\)라고 하겠습니다. 그러면 strong duality에 의해서 우리는 다음과 같은 결과를 얻게 됩니다.
\[ \begin{align} 6 x^\star_1 + 4 x^\star_2 + 2 x^\star_3 &= y^\star_1 \cdot (4 x^\star_1 + 2 x^\star_2 + x^\star_3) + y^\star_2 \cdot (x^\star_1 + x^\star_2) + y^\star_3 \cdot (x^\star_2 + x^\star_3) \\ &= x^\star_1 \cdot (4 y^\star_1 + y^\star_2) + x^\star_2 \cdot (2 y^\star_1 + y^\star_2 + y^\star_3) + x^\star_3 \cdot (y^\star_1 + y^\star_3) \\ &= 5 y^\star_1 + 3 y^\star_2 + 4 y^\star_3 \end{align} \tag{1} \]
위 식에서 먼저 이 부분에 집중해 보겠습니다.
\[ y^\star_1 \cdot (4 x^\star_1 + 2 x^\star_2 + x^\star_3) + y^\star_2 \cdot (x^\star_1 + x^\star_2) + y^\star_3 \cdot (x^\star_2 + x^\star_3) = 5 y^\star_1 + 3 y^\star_2 + 4 y^\star_3 \]
이를 정리하면 다음과 같아집니다.
\[ y^\star_1 \cdot (4 x^\star_1 + 2 x^\star_2 + x^\star_3 - 5) + y^\star_2 \cdot (x^\star_1 + x^\star_2 - 3) + y^\star_3 \cdot (x^\star_2 + x^\star_3 - 4) = 0 \tag{2}\]
이제 식 (2)가 성립하기위한 조건을 찾아 보고자 합니다. 여기서 중요한 것은 \(x^\star\)와 \(y^\star\)가 모두 각각의 program에 feasible한 solution이라는 점입니다. 첫 번째 항을 보겠습니다. Primal program에는 \(4 x_1 + 2 x_2 + x_3 \geq 5\)라는 constraint가 있습니다. 그에 대응하여 dual program에는 \(y_1 \geq 0\)이 존재합니다. 따라서 feasible한 \(x\), \(y\)에 대해서는 반드시
\[ y_1 \cdot (4 x_1 + 2 x_2 + x_3 - 5) \geq 0\]
이라는 사실을 알 수 있습니다. 두 번째 항도 비슷하게 분석할 수 있습니다. Primal program의 \(x_1 + x_2 \leq 3\)과 dual program의 \(y_2 \leq 0\)을 조합하여, feasible한 \(x\), \(y\)에 대해서,
\[ y_2 \cdot (x_1 + x_2 - 3) \geq 0\]
임을 이끌어낼 수 있습니다. 마지막 항의 경우에는 priaml program에서 이미 \(x_2 +x_3 = 4\)라는 constraint가 존재하므로 항상
\[ y_3 \cdot (x_2 + x_3 - 4) = 0\]
이라는 점을 알게 됩니다. 따라서 \(x^\star\), \(y^\star\)가 각각의 program에 feasible하면서 식 (2)를 만족시키기 위해서는
\[\begin{array} {rcl} y^\star_1 = 0 & \text{or} & 4 x^\star_1 + 2 x^\star_2 + x^\star_3 = 5, \\ y^\star_2 = 0 & \text{or} & x^\star_1 + x^\star_2 = 3, \\ y^\star_3 = 0 & \text{or} & x^\star_2 + x^\star_3 = 4 \end{array} \tag{3} \]
를 만족해야 한다는 것을 알 수 있습니다.
식 (1)에서 이번에는
\[ 6 x^\star_1 + 4 x^\star_2 + 2 x^\star_3 = x^\star_1 \cdot (4 y^\star_1 + y^\star_2) + x^\star_2 \cdot (2 y^\star_1 + y^\star_2 + y^\star_3) + x^\star_3 \cdot (y^\star_1 + y^\star_3) \]
를 생각해 보겠습니다. 앞에서의 논의한 것을 그대로 적용하면 \(x^\star\), \(y^\star\)가
\[\begin{array} {rcl} x^\star_1 = 0 & \text{or} & 4 y^\star_1 + y^\star_2 = 6, \\ x^\star_2 = 0 & \text{or} & 2 y^\star_1 + y^\star_2 + y^\star_3 = 4, \\ x^\star_3 = 0 & \text{or} & y^\star_1 + y^\star_3 = 2 \end{array} \tag{4} \]
를 모두 만족해야 한다는 점을 볼 수 있습니다.
더욱 흥미로운 점은 역도 성립한다는 것입니다. 만약 각각의 program에 feasible한 두 solution을 가지고 왔을 때, 두 solution이 조건 (3), (4)를 모두 만족한다면, 그 solution이 식 (1)과 같은 등식이 성립하게 된다는 것을 알 수 있습니다. 이는 앞서 보인 weak duality에 의해서 두 solution이 각 program의 optimal solution이라는 점을 보여줍니다. 이러한 성질을 우리는 complementary slackness라고 하며 조건 (3), (4)와 같이 어떤 변수가 0이 아닐 때 그에 대응하는 dual의 constraint가 등식이 성립하는 조건을 complementary slackness condition이라고 합니다.
Complementary slackness
어떤 linear program과 그것의 dual program 각각에 feasible한 solution이 서로의 program의 optimal solution이 될 필요충분조건은 두 solution이 complementary slackness condition을 만족하는 것이다.
지금까지 linear programming에 대한 개괄적인 설명과 함께 LP duality에 대해서 알아보았습니다. Linear programming은 매우 다양한 분야에서 널리 활용되고 있으며, 제가 주로 공부하는 분야에도 매우 유용한 도구로 알려져 있습니다. 그러다 보니 다른 글들을 포스팅하려고 할 때, LP와 LP duality에 관련된 지식이 선행되어야 해서 글을 적지 못한 경우도 많이 있었습니다. 이제 LP duality에 대해서 적었으니 다른 재미있는 주제들도 가지고 올 수 있게 되었습니다. 꾸준히 적어 보도록 하겠습니다.
감사합니다.