만약 학부 시절 OR에 대한 수업을 들었다면 LP, simplex method, IP, duality 등에 대한 내용을 공부한 적이 있을 것이다.

나의 경우에, LP나 simplex와 같은 내용들은 직관적으로 이해할 수 있었지만 유독 duality는 제대로 이해하기가 쉽지 않았다.

그래서 무작정 식을 외웠던 기억이 있다…

게다가, 이걸 어떻게 알아낸걸까? 하는 생각이 많이 들었다. 신기할 정도로 딱딱 맞아 떨어지는 게 많았고, 이걸 사람이 어떻게 알 수 있었던 건지 궁금했다.

그리고 얼마 전 수업으로 duality에 대해 좀 더 깊게 배웠고, 이제 조금은 이해한 것 같아 까먹기 전에 빠르게 글로 옮겨 보려 한다.

Duality가 왜 필요한가?

먼저, 이게 왜 필요한지를 알아야 한다.

결론부터 말하자면, dual을 통해 primal문제의 bound를 얻을 수 있다.

특히 LP의 경우에는 dual을 이용해서 문제에 대한 다양한 정보를 알아낼 수 있다.

예를 들어, primal문제가 infeasible한지 아닌지를 증명하고 싶을 때 dual이 unbounded임을 보이면 된다.

Duality는 어떻게 만들어졌나?

이를 이야기하기 위해서는 먼저 최적화의 발전 과정을 먼저 살펴볼 필요가 있다.
지금 최적화를 배울 때는 기본적으로 목적함수, 결정변수, 제약식 세가지 요소가 포함되어 있다.

하지만 오래 전에 최적화를 하는 방식에는 제약식이라는게 존재하지 않았다.
그럼 어떻게 제약을 뒀는가?

어떤 방식으로든 목적함수 안에 제약식을 포함시키고 목적함수를 이용해서 최적화를 했다.
물론 지금도 그러한 방식을 쓰는 경우가 있다.

그럼 어떻게 제약식을 목적함수에 넣었단 말인가?
목적함수 내에서 제약을 만족하지 못한다면, 패널티(penalty)를 주는 방식을 사용했다.

이러한 방법은 일종의 relaxation방법으로 사용될 수 있고,
그 중 dual을 만들어낸 것이 그 유명한 Lagrangian Relaxation이다.

Relaxation이란?
쉽게 말하자면, 복잡한 문제를 좀 더 쉽게 만드는 것이다. 예를 들어, IP에서 정수조건을 완화(relaxation)해서 LP를 만든다던가 하는 것 역시 relaxation의 일종이다.
조금 더 구체적으로 말해보자면, 어떤 문제 \(A\)가 있을 때, \(A\)의 feasible set을 포함하는 feasible set을 가지고, \(A\)의 solution보다 더 좋거나 같은 solution을 갖는 문제 \(B\)가 있다면, 문제 \(B\)는 문제 \(A\)의 relaxation인 것이다.

이러한 relaxation문제에서 중요한 이슈는 문제를 최대한 쉽고, tight하게 만드는 것이다.

이때 tight하다는 것은 optimal과 ralaxation문제를 통해 나온 해의 값이 최대한 가깝도록 하는 것을 의미한다. 그 이유는, relaxation의 방법은 매우 다양하고, 거기서 우리는 좋은 bound를 찾는 것이 목적이기 때문이다.

Lagrangian Relaxation

그렇다면 Lagrangian Relaxation에 대해서 알아보자.

자, 다음과 같은 문제가 있다.

\[\eqalignno{ min \quad c'x & \\ Ax &= b \\ x &\geq 0 }\]

위에서 언급했듯이, lagrangian relaxation에서는 패널티를 이용해서 제약식을 목적함수에 포함시킨다.

즉, \(Ax = b\)를 목적함수에 넣어야 하고, \(p'\)를 패널티라고 할 때 목적함수는 다음과 같이 만들 수 있다.

Lagrangian function : \(L(x,p) = c'x + p'(b-Ax)\)

그리고 이를 이용하여 문제를 다음과 같이 표현할 수 있다.

\[\eqalignno{ min \quad L(x,p) &= c'x + p'(b - Ax) \\ x &\geq 0 }\]

위 식에서 \(b-Ax = 0\), 즉 원래 문제의 제약식인 \(Ax = b\)가 아니라면 그 값이 패널티 \(p'\)와 곱해져 해에 영향을 주게 되는 것이다.

이때, 패널티 \(p\)를 실수라고 했을 때 Lagrangian relaxation 문제의 해를 \(g(p)\)라 하자, 이때 원래 문제의 optimal을 \(x^*\)이라 가정하면, \(x^*\)은 원 문제의 feasible solution이기도 하기에, 다음을 만족한다.

\[g(p) = min_{x\geq 0}[c'x + p'(b-Ax)] \leq c'x^* + p'(b-Ax^*) = c'x\]

즉, \(g(p)\)는 원래 문제의 lower bound가 되는 것이다.

그리고 우리는 optimal solution과 가장 가까운 lower bound를 찾고 싶은 것이다. 가장 tight한 문제를 찾는 것이다.
그러므로 우리는 (Minimization문제이기 때문에) 가장 큰 \(g(x)\)를 찾아야 하고, 이는 또 다른 최적화 문제와 같다.

이를 표현하면, 다음과 같다.

\[\eqalignno{ max \quad & g(p) \\ st. \quad & no \, constraints\, on\, p \\ where \quad & g(p) = min_{x\leq 0}[c'x + p'(b-Ax)] }\]

이때, \(g(p)\)는 다음과 같다.

\[\eqalignno{ g(p) &= min_{x\geq 0}[c'x + p'(b-Ax)] \\ &= p'b + min_{x\geq 0}(c' - p'A)x }\]

여기서 \(min_{x\geq 0}(c' - p'A)x\)는 다음과 같이 두가지 값으로 나뉘게 된다.

\[min_{x\geq 0}(c' - p'A)x = \begin{cases} 0, \quad if \, c'-p'A \geq 0 \\ -\infty, \quad otherwise \end{cases}\]

이때 우리는 g(p)를 최대화해야 하는데, \(min_{x\geq 0}(c' - p'A)x\)이 \(-infty\)이면 안되기 때문에,
값이 0만 나오도록 하는 제약을 걸어준다. 즉, \(c'-p'A \geq 0\)인 제약을 걸어준다.

그러면 다음과 같은 식이 나온다.

\[\eqalignno{ max &\quad p'b \\ s.t. &\quad p'A \leq c' \qquad (p'A_j \leq c_j, \quad \forall j) }\]

어디서 보던 것과 비슷한 형태라는 것을 알 수 있다.
이것이 바로 dual인 것이다.

참고