📂최적화이론

선형계획법에서의 강한 쌍대성 정리 증명

정리

$$ \begin{align*} \text{Maximize} & \sum_{j=1}^{n} c_{j} x_{j} & \text{(Primal)} \\ \text{subject to} & \sum_{j=1}^{n} a_{ij} x_{j} \le b_{i} & i = 1 ,\cdots , m \\ & x_{j} \ge 0 & j = 1, \cdots , n \end{align*} $$ $$ \begin{align*} \text{Minimize} & \sum_{i=1}^{m} b_{i} y_{i} & \text{(Dual)} \\ \text{subject to} & \sum_{i=1}^{m} y_{i} a_{ij} \ge c_{j} & j = 1 ,\cdots , n \\ & y_{i} \ge 0 & i = 1, \cdots , m \end{align*} $$

주어진 선형계획문제의 프라이멀 문제와 듀얼 문제가 위와 같이 나타난다고 하자. 만약 $\mathbf{x}^{\ast} = \left( x_{1}^{\ast} , \cdots , x_{n}^{\ast} \right)$ 가 프라이멀 문제의 최적해고, $\mathbf{y}^{\ast} =\left( y_{1}^{\ast} , \cdots , y_{m}^{\ast} \right)$ 가 듀얼 문제의 최적해라면, 다음 부등식이 성립한다. $$ \sum_{j=1}^{n} c_{j} x_{j}^{\ast} = \sum_{i=1}^{m} b_{i} y_{i}^{\ast} $$

설명

강한 쌍대성 정리는 쉽게 말해서 위 그림처럼 프라이멀 문제와 듀얼 문제의 최적값이 실제로 일치함을 보장한다.

증명 ¹

듀얼 가용해 $\mathbf{y}^{\ast}$ 가 $\sum_{j=1}^{n} c_{j} x_{j}^{\ast} = \sum_{i=1}^{m} b_{i} y_{i}^{\ast}$ 를 만족하는 것을 보이면 충분하다. 우선 최적화문제를 풀기 위해 심플렉스 메소드를 사용했다고 가정하자. 우리는 심플렉스 메소드가 최적해가 존재하든 말든 일단 하나를 만들어내긴 만들어내는 걸 알고 있는데, 실제로도 존재한다고 가정한다. 심플렉스 메소드를 통해 얻은 마지막 딕셔너리를 $$ \zeta = \overline{\zeta} + \sum_{j \in \mathcal{N}} \overline{c_{j}} x_{j} $$ 과 같이 쓸 수 있을텐데, 이는 최적의 딕셔너리임을 상정하기 때문에 표기는 바 $\overline{\cdot}$ 대신 애스터리스크 $\cdot^{\ast}$ 를 쓰도록 하겠다. 이를 기저 변수 $\left\{ x_{j} \right\}_{j=1}^{n}$ 와 비기저 변수 $\left\{ w_{i} \right\}_{i=1}^{m}$, 그 계수 $d_{i}^{\ast}$ 에 대해 적어보면 $$ \zeta = \zeta^{\ast} + \sum_{j=1}^{n} c_{j}^{\ast} x_{j} + \sum_{i=1}^{m} d_{i}^{\ast} w_{i} $$ 이다. 한편 $\zeta^{\ast}$ 은 프라이멀 문제의 최적해이므로 $$ \zeta^{\ast} = \sum_{j=1}^{n} c_{j} x_{j}^{\ast} $$ 이다. 이에 따라 $i = 1 , \cdots, m$ 에 대해 $$ y_{i}^{\ast} := - d_{i}^{\ast} $$ 라 두면 $$ \begin{align*} \sum_{j=1}^{n} c_{j} x_{j} =& \zeta^{\ast} + \sum_{j=1}^{n} c_{j}^{\ast} x_{j} + \sum_{i=1}^{m} d_{i}^{\ast} w_{i} \\ =& \zeta^{\ast} + \sum_{j=1}^{n} c_{j}^{\ast} x_{j} + \sum_{i=1}^{m} \left( - y_{i}^{\ast} \right) \left( b_{i} - \sum_{j=1}^{n} a_{ij} x_{j} \right) \\ =& \zeta^{\ast} - \sum_{i=1}^{m} b_{i} y_{i}^{\ast} + \sum_{j=1}^{m} \left( c_{j}^{\ast} + \sum_{i=1}^{m} y_{i}^{\ast} a_{ij} \right) x_{j} \end{align*} $$ 위 등식을 $x_{j}$ 에 대한 선형방정식으로 보고 계수를 맞춰보면 $$ \begin{align*} \zeta^{\ast} =& \sum_{i=1}^{m} b_{i} y_{i}^{\ast} \\ c_{j} =& c_{j}^{\ast} + \sum_{i=1}^{m} y_{i}^{\ast} a_{ij} \qquad j = 1, \cdots , n \end{align*} $$ 를 얻는다. 앞서 이미 $\zeta^{\ast} = \sum_{j=1}^{n} c_{j} x_{j}^{\ast}$ 라 했으므로, 우리는 정리에서 원하던 등식 $$ \sum_{j=1}^{n} c_{j} x_{j}^{\ast} = \zeta^{\ast} = \sum_{i=1}^{m} b_{i} y_{i}^{\ast} $$ 을 일단 얻었다. $c_{j}^{\ast}$ 가 프라이멀 문제의 최적계수라는 점에서 $c_{j}^{\ast} \le$ 이고, 같은 이유로 $d_{i}^{\ast} \le 0$ 이므로 $$ \begin{align*} \sum_{i=1}^{m} y_{i}^{\ast} a_{ij} \ge c_{j} & \qquad j = 1 , \cdots , n \\ y_{i}^{\ast} \ge 0 & \qquad i = 1 , \cdots , m \end{align*} $$ 즉 $\mathbf{y} = \left( y_{1}^{\ast}, \cdots , y_{m}^{\ast} \right)$ 이 듀얼 문제의 가용해임을 보장할 수 있다.

■

같이보기

선형계획법에서의 쌍대성

최적화를 전공할 게 아니라 한 과목으로 다룬다면 선형계획법은 심플렉스 메소드와 쌍대성 이 두가지만 배우면 모든 걸 다 배운 것이다. 물론 그 둘 뿐이라고해서 딱히 그 과정이 쉽다는 말은 아니다.

심플렉스 메소드가 구체적인 그 방법에 대해 논한다면, 쌍대성은 프라이멀 문제에 대해 듀얼 문제가 존재하고, 그 최적해가 서로 같다는 식의 다분히 이론적인―순수수학적인 논의다. 이는 다음의 쌍대성 정리들로 보장된다.

약한 쌍대성 정리

$$ \sum_{j=1}^{n} c_{j} x_{j}^{\ast} \le \sum_{i=1}^{m} b_{i} y_{i}^{\ast} $$

강한 쌍대성 정리

$$ \sum_{j=1}^{n} c_{j} x_{j}^{\ast} = \sum_{i=1}^{m} b_{i} y_{i}^{\ast} $$