しっかり学ぶ数理最適化の演習解説ー2.7：相補性定理と、その応用

　線形計画法において、主問題とその双対問題が実質的に等しい値を持つことが強双対定理により要請される。では、値ではなく最適解同士にはどういう関係があるのだろうか？以下の相補性定理がそれに対するアンサーとなる。

・相補性定理

以下、 $A \in R^{m \times n}, \boldsymbol{b} \in R^{m}, \boldsymbol{c} \in R^{n}, \boldsymbol{x} \in R^{n}, \boldsymbol{y} \in R^{m}$ とし、 $n \gt m$ かつ $A$ の全ての行ベクトルが一次独立であるとする。

主問題を

$max_{\boldsymbol{x}} \ \ \boldsymbol{c}^{T} \boldsymbol{x} \ \ s.t.\ A \boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{0}$

とし、その双対問題を

$min_{\boldsymbol{y}} \ \ \boldsymbol{b}^{T} \boldsymbol{y} \ \ s.t.\ A^{T} \boldsymbol{y} \geq \boldsymbol{c}$

とする。このとき、それぞれの実行可能解 $\boldsymbol{x},\boldsymbol{y}$ がともに最適解であるための必要十分条件は、

$x_j (\sum^m_{i=1} a_{ij} y_i -c_j)=0, \ \ j=1,...,n$

が成り立つことである。この条件を相補性条件と呼ぶ。

・応用事例として　

　これを用いて問題を解いてみよう(自己流の解き方のため間違っていたらご容赦ください)。例えば、「しっかり学ぶ数理最適化」の演習2.7は下記のような問題である。

$max_{\boldsymbol{x}} \ \ \boldsymbol{c}^{T} \boldsymbol{x} \ \ s.t.\ \boldsymbol{a}^{T} \boldsymbol{x}=b, \boldsymbol{x} \geq \boldsymbol{0}$

ただし、 $\boldsymbol{a}, \boldsymbol{c} \geq \boldsymbol{0}, b \gt 0$ とする。

　まず $n=1$ の場合は、明らかに $x_1=b/a_1$ が最適解で、値 $b_1 c_1/a_1$ をとる。

　次に、 $n \gt 1$ の場合を考える。まず相補性定理が使えるかを吟味する。行列 $A$ はベクトル $\boldsymbol{a}=(a_1,a_2,..,a_n)$ となり一行のみの行列となるので、明らかに一次独立となる。また、制約の数も $m=1$ なので $n \gt m$ を満たしているため、相補性定理が適用できる。

　演習2.7の主問題は制約が1つのみであるため双対問題の方が解きやすいはずである。双対問題は

$min_{\boldsymbol{y}} \ \ by \ \ s.t.\ y \boldsymbol{a} \geq \boldsymbol{c}$

であり、制約条件を整理すると $y \geq max_j c_j/a_j$ となるため、この問題の最適解は $y=max_j\ c_j/a_j$ で、値 $b \cdot max_j \ c_j/a_j$ をとる。

相補性定理により、主問題の実行可能解 $\boldsymbol{x}$ が最適解であることは、すべての $j$ に対して $x_j (y -c_j/a_j)=0$ が成り立つことと同値である。今、 $y=max_j \ c_j/a_j$ であるため、 $c_j / a_j$ を最大化する $j$ の集合を $J$ で定義すると、相補性条件は

$x_j=0 \ (j \notin J)$

と等価になる。従って、これを満たし、かつ実行可能となるため制約 $\boldsymbol{a}^T\boldsymbol{x} =b$ を満たすような解が最適解となる。

以上より、主問題の最適解は $x_j=0 \ (j \notin J)$ かつ ${\displaystyle　 \sum_{j \in J} a_j x_j =b}$ なる任意の解 $\boldsymbol{x}$ であって、このとき値 $b \cdot max_j \ c_j/a_j$ をとる( $n=1$ の結果もこれに含めることができる)。