線形計画法における双対性
ビルドアップ
$x_{1} , x_{2} \ge 0$ について、次のような線形計画問題があるとしよう。 $$ \begin{matrix} \text{Maximize} & & 2x_{1} & + & 3x_{2} \\ \text{subject to} & & 4x_{1} & + & 8x_{2} & \le & 12 \\ & & 2x_{1} & + & x_{2} & \le & 3 \\ & & 3x_{1} & + & 2x_{2} & \le & 4 \end{matrix} $$
私たちの目標は、与えられた制約条件の下で目的関数 $\zeta = 2x_{1} + 3x_{2}$ を最大にする最適解 $x_{1}^{\ast}, x_{2}^{\ast}$ を見つけることだ。しかし、式をよく見ると、問題を解かなくても最大値の上限があることが分かる。第一の制約条件から、 $$ 2x_{1} + 3x_{2} \le 4x_{1} + 8x_{2} \le 12 $$ 実際に、$4x_{1} + 8x_{2} \le 12$ の両辺を $2$ で割ると、 $$ 2x_{1} + 3x_{2} \le 2x_{1} + 4x_{2} \le 6 $$ よって、目的関数の値は、どんなに大きくても $6$ を超えないことが分かる。それだけではない。第二の制約条件を考えると、 $$ 2x_{1} + 3x_{2} = {{ 1 } \over { 3 }} \left( 4x_{1} + 8x_{2} + 2x_{1} + x_{2} \right) \le {{ 1 } \over { 3 }} (12 + 3) = 5 $$ のように上限をさらに減らせることもある。つまり、 $$ d_{1} x_{1} + d_{2} x_{2} \le h $$ という不等式がある時に、この $h$ を縮めていくアプローチを考えることができるということだ。目的関数自体がバウンドされているから、この上限を続けて縮めていくうちに、これ以上縮められない、つまり上限の最小値を見つける時が来るが、よく考えると、この上限を縮めること自体が別の最適化問題である。直感的に、元の最大化問題を解くのも、上限の最小化問題を解くのも、同じ結論に到達できるように思える。
特に、$d_{1} x_{1} + d_{2} x_{2} \le h$ の形は「別の何らかの線形計画問題」の制約条件にも見える。そこで、次のようにその「別の何らかの線形計画問題」を定義する。
定義 1
$$ \begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} \le \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix} $$
行列 $A \in \mathbb{R}^{m \times n}$ と $\mathbf{b} \in \mathbb{R}^{m \times 1}$ と $\mathbf{c} \in \mathbb{R}^{n}$ について、線形計画問題が上述のように与えられているとしよう。
- 対応する上限の最小値を見つける次の線形計画問題をデュアル線形計画問題と呼ぶ。 $$ \begin{matrix} \text{Minimize} & \mathbf{b}^{T} \mathbf{y} \\ \text{subject to} & A^{T} \mathbf{y} \ge \mathbf{c} \\ & \mathbf{y} \ge \mathbf{0} \end{matrix} $$
- デュアル線形計画問題に対比される表現として、与えられた元の最大化問題をプライマル線形計画問題と呼ぶ。
説明 2
デュアルとプライマルの解法を視覚的に表すと、上記の通りだ。プライマル問題は下から上に目的関数を最大化し、デュアル問題は上から下へ解の空間を縮小していく。それが正確に一致した時、私たちは疑いなくそれが最適解であると納得できる。
双対性とは？
双対性は数学全般で一般的に現れる概念で、関数解析の双対空間や幾何学的双対グラフなど、対称性と似ているがより高い抽象レベルの性質を総称する。
関連項目
線形計画法における双対性
最適化を専攻しないが一科目として学ぶ場合、線形計画法ではシンプレックス法と双対性この二つを学べば全てを学んだと考えられる。もちろん、それで簡単だというわけではない。
シンプレックス法が具体的な方法について論じるなら、双対性はより理論的―純粋数学的な議論で、プライマル問題に対してデュアル問題が存在し、その最適解が等しいことを述べる。これは次の双対性定理によって保証される。
弱い双対性定理
$$ \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} $$