📂最適化理論

線形計画法における強い双対性定理の証明

定理

$$\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}$$