強相補性→双対定理の証明

手元にある最適化の教科書で線形計画法の再勉強をしているのだが，いまいち
書いてある証明が読めない部分があったので自分で証明しなおした．

作者: 田村明久,村松正和
出版社/メーカー: 共立出版
発売日: 2002/04/01
メディア: 単行本
購入: 2人クリック: 27回
この商品を含むブログ (8件) を見る

このエントリの目標は強相補性定理から双対定理を導くことだ．

準備

双対問題

線形計画問題 P
$\text{min } c^\top x$
$\text{s.t. } Ax \geq b, x\geq 0$
に対して，次の線形計画問題 D
$\text{max } b^\top y$
$\text{s.t. } A^\top y \leq c, y\geq 0$
を，Pの双対問題と呼ぶ．

弱双対定理

P と D の任意の実行可能解 $x, y$ について，
$c^\top x \geq b^\top y$ ．

（証明）双対問題の定義をみながら， $c$ を $A^\top y$ で抑えて $Ab$ を $x$ で抑える．

双対定理

P と D の一方が最適解をもつならば他方も最適解をもつ．
また P と D の最適解 $x, y$ について，
$c^\top x = b^\top y$ ．

（証明）略．簡単ではない．

相補性定理

P と D の実行可能解 $x, y$ について，下記の2条件は同値

$x, y$ はそれぞれ P, D の最適解である．
$x^\top (c-A^\top y) = 0$ かつ $(Ax-b)^\top y =0$

後者の条件を 相補性 と呼ぶ

（証明）弱双対定理の証明＋双対定理．

強相補性定理

P と D がともに実行可能であれば，下記の性質（強相補性）を満たす最適解が存在する

相補性
$x_j >0 \text{ XOR } (c-A^\top y)_j > 0 \text{ for all } j$
$y_i >0 \text{ XOR } (Ax - b)_i > 0 \text{ for all } i$

（証明）略．簡単ではない．

強相補性→双対定理の証明

ここでは強相補性定理から双対定理を導きたい．この辺りの定理は相互に導けるものが多く，
どこから出発するのが正解というわけではないが，私がすぐにはわからなかった部分がここなので
これをメモしておく．証明のアイディアは最適化法（共立出版，田村＋松村）にあるものと同じだが，
強相補性定理の使いかたが少し異なる．（私は本の証明がよくわからなかった）

次の線形計画問題 SD と，その双対問題 SD' を考える：
(SD)
$\text{min } 0$
$\text{s.t. } \begin{bmatrix} 0 & A & -b \\ -A^\top & 0 & c\\ b^\top & -c^\top & 0 \end{bmatrix} \begin{bmatrix} y \\ x \\ z \end{bmatrix} \geq 0, \begin{bmatrix} y \\ x \\ z \end{bmatrix} \geq 0$ .
(SD')
$\text{max } 0$
$\text{s.t. } \begin{bmatrix} p^\top, q^\top, r \end{bmatrix} \begin{bmatrix} 0 & A & -b \\ -A^\top & 0 & c \\ b^\top & -c^\top & 0 \end{bmatrix} \leq 0, \begin{bmatrix} p^\top, q^\top, r \end{bmatrix} \geq 0$ .

双対問題 SD' は，制約式を転置して不等式に -1 をかけることで (SD'') のように書き換えられる．
(SD'')
$\text{min } 0$
$\text{s.t. } \begin{bmatrix} 0 & A & -b \\ -A^\top & 0 & c\\ b^\top & -c^\top & 0 \end{bmatrix} \begin{bmatrix} p \\ q \\ r \end{bmatrix} \geq 0, \begin{bmatrix} p \\ q \\ r \end{bmatrix} \geq 0$ .

さて，問題 SD と SD'' はともに零ベクトルが実行可能であることから実行可能であり，
強相補性定理から強相補性を満たす SD と SD'' の最適解のペア $(y, x, z), (p,q,r)$ が存在する．
特に強相補性のうち，SD の最後の線形不等式に注目すると：

$r(b^\top y -c^\top x) = 0$
$r>0$ XOR $b^\top y -c^\top x>0$ .

後者の条件に従って場合分けして考える．

$r > 0$ の場合

このとき $b^\top y -c^\top x=0$ である． $(y,x,z)$ は SD の実行可能解であるから，次の不等式を満たす．

$Ax \geq bz$
$A^\top y \leq cz$

$z = 0$ と仮定すると，強相補性より $b^\top p -c^\top q>0$ である．
このとき， $q/r, p/r$ はそれぞれ P， Q の実行可能解であり， $b^\top p/r -c^\top q/r>0$
であるからこれは弱双対性を満たさない． $z=0$ という仮定は矛盾を導くので $z > 0$ である．

$z > 0$ であるので， $x/z, y/z$ は双対ギャップが零の P, D の実行可能解である．

$b^\top y -c^\top x>0$ の場合．

このとき $r = 0$ である．また， $z >0$ とすると $x/z, y/z$ が弱双対定理を満たさない P, Q の実行可能解となってしまうので， $z = 0$ である．

さて， $b^\top y > 0$ か $c^\top x < 0$ の少なくとも一方が成立する．（一般に $u < v \Rightarrow u < 0 \text{ or } v > 0$ ）

$b^\top y > 0$ のとき，P の最適解 $s$ の存在を仮定すると，
$0 < b^\top y \leq s^\top A ^\top y \leq s^\top 0 = 0$
となり，矛盾する．また， D の最適解 $t$ の存在を仮定すると，
$t + y$ も実行可能であることから， $t$ の最適解より， $b^\top y \leq 0$ でなければならない．
（さもなければ， $t+ y$ が最適解より良い解になってしまう．）
したがって， $0 < b^\top y \leq 0$ となり，矛盾する．

$c^\top x < 0$ のとき，D の最適解 $t$ の存在を仮定すると，
$0 > c^\top x \geq t^\top A x \geq 0 x = 0$ となり矛盾．
また P の最適解 $s$ の存在を仮定すると， $s + x$ も実行可能解であり，
$s$ の最適性から $c^\top x \geq 0$ が言える．したがって，
$0 > c^\top x \geq 0$ となり，矛盾．