next up previous
: 歪対称問題の数値解法 : 内点法 : 歪対称問題


双対定理

基準形 で記述された最適化問題

(P)$\displaystyle \quad \min \left \{ \vec{c}^T \vec{x} : \vec{A} \vec{x} \geq \vec{b}, \vec{x} \geq \vec{0} \right \}$ (52)

を考える. ただし, $ \vec{A} \in \mathbb{R}^{m \times n}$であり, その他のベクトルは適合する次元を持つものとする.

問題(P)の双対問題は,

(D)$\displaystyle \quad \max \left \{ \vec{b}^T\vec{y}: \vec{A}^T\vec{y} \leq \vec{c}, \vec{y} \geq \vec{0} \right \}$ (53)

によって定義される.

双対問題は, 一見すると, 主問題から恣意的に作成された無意味な問題に見えるかもしれない. しかし, 実際には, 主問題と双対問題には密接な関係がある. 本節では, 以下で, その関係について見てゆく.

まず弱双対定理と呼ばれる事実を述べる.

定理 21 (弱双対定理) 主問題$ \vec{x}$$ \vec{y}$をそれぞれ主問題(P)と双対問題(D)の制約条件を満たすベクトルとする. このとき,

$\displaystyle \vec{c}^T \vec{x} -\vec{b}^T\vec{y} \geq 0.$ (54)

が成り立つ.

[証明] $ \vec{y}^T\vec{b} \leq \vec{y}^T\vec{A} \vec{x} \leq \vec{c}^T \vec{x} $. ///

系 22 主問題(P)と双対問題(D)の制約条件を満たすベクトル $ \vec{x}^{\ast}$, $ \vec{y}^{\ast}$ $ \vec{c}^T \vec{x}^{\ast}=\vec{b}^T \vec{y}^{\ast}$を満たすならば, $ \vec{x}^{\ast}$は主問題(P)の最適解であり, $ \vec{y}^{\ast}$は双対問題(D)の最適解である.

[証明] $ \vec{x}$$ \vec{y}$をそれぞれ主問題(P)と双対問題(D)の制約条件を満たすベクトルとする. このとき, 定理21より, $ \vec{b}^T\vec{y} \leq \vec{c}^T\vec{x}^{\ast}=\vec{b}^T\vec{y}^{\ast}$, $ \vec{c}^T \vec{x} \geq \vec{b}^T\vec{y}^{\ast}=\vec{c}^T\vec{x}^{\ast}$となる. ゆえに, $ \vec{x}^{\ast}$は主問題(P)の最適解であり, $ \vec{y}^{\ast}$は双対問題(D)の最適解である. ///

実は, 主問題(P)が有限の最適解を持つときには必ず双対問題(D)も有限の最適解を持ち, 逆に双対問題(D)が有限の最適解を持つときには必ず主問題(P)も有限の最適解を持つ. この事実は, 双対定理と呼ばれる.

この節では, 最終的に双対定理を証明することを目標とするのだが, そのためにはかなりの準備が必要である.

まず, 主問題と双対問題を同時に解くことを考えよう. このためには, $ \vec{x} \geq \vec{0}$, $ \vec{y} \geq \vec{0}$の条件の下で,

$\displaystyle \vec{A} \vec{x} - \vec{b} \geq \vec{0},   -\vec{A}^T \vec{y} + \vec{c} \geq \vec{0},   \vec{b}^T \vec{y}- \vec{c}^T \vec{x} = 0,  $ (55)

を連立させて解けばよい. ただし, この段階では, 実際に(55)が解を持つか否かは明らかではない.

ところで, (55)は, 第3式の等号を不等号で置き換えた連立不等式

$\displaystyle \vec{A} \vec{x} - \vec{b} \geq \vec{0},   -\vec{A}^T \vec{y} + \vec{c} \geq \vec{0},   \vec{b}^T \vec{y}- \vec{c}^T \vec{x} \geq 0$ (56)

と等価である. この理由を説明しよう. (55)の解が(56)を満たすことは明らかである. 逆に, (56)の解$ \vec{x}$, $ \vec{y}$が与えられているものとする. すると, 定理21より, $ \vec{b}^T\vec{y}-\vec{c}^T \vec{x} \leq 0$かつ $ \vec{b}^T\vec{y}-\vec{c}^T \vec{x} \geq 0$となるから, したがって $ \vec{b}^T \vec{y}- \vec{c}^T \vec{x} = 0$となる.

ここで, (56)を行列の形で書き直すと,

$\displaystyle \begin{bmatrix}0 & \vec{A} & -\vec{b} \ -\vec{A}^T & 0 & \vec{c}...
...\vec{0}\ \vec{0}\ 0 \end{bmatrix}, \vec{x} \geq \vec{0}, \vec{y} \geq \vec{0}$ (57)

となる.

ところで, (57)は必ずしも解を持つとは限らない. そこで, これを必ず解を持つ形に書き換えることを考える. そのために, (57)にあらわれたベクトル $ [\vec{y}^T,\vec{x}^T,1]$の最後の定数1を変数$ \kappa$で置き換えた,

$\displaystyle \begin{bmatrix}0 & \vec{A} & -\vec{b} \ -\vec{A}^T & 0 & \vec{c}...
...\ \kappa \end{bmatrix} \geq \begin{bmatrix}\vec{0}\ \vec{0}\ 0 \end{bmatrix}$ (58)

という問題を考える. 問題(58)は $ \vec{x}=\vec{0}$, $ \vec{y}=\vec{0}$, $ \kappa=0$という自明な解を持つ. よって, 解の存在性について心配する必要はなくなる. また, $ \kappa \neq 0$なる(58)の解がひとつ見付かった場合, そこから(57)の解を復元することができる. これはなぜかというと, (58)の両辺を$ \kappa$で割ると($ \kappa>0$の場合はこれが可能である),

$\displaystyle \begin{bmatrix}
0 & \vec{A} & -\vec{b} \\
-\vec{A}^T & 0 & \ve...
...ix},
\frac{\vec{x}}{\kappa}\geq \vec{0}, \frac{\vec{y}}{\kappa} \geq \vec{0}
$

となり, これは(57)そのものであるからである.

さて, 以下では第2節の議論を援用して (58)の解について調べてゆきたいのであるが, ここで更に問題が生じる. それは, (58)の 制約条件を等号抜きで満たす点(内点)が存在するかどうかが 明らかでない, ということである. この問題を回避するため, (58)を内点が必ず存在する問題に書き換えることを考える.

$ \vec{x}^0 > \vec{0}$, $ \vec{y}^0 > \vec{0}$を決める. これは正であればどのように取っても構わない. 次に, $ \vec{p}^0=1/\vec{x}^0$, $ \vec{t}^0=1/\vec{y}^0$とおく. パラメータ $ \bar{\vec{b}}$, $ \bar{\vec{c}}$, $ \beta$

\begin{displaymath}\begin{split}&\bar{\vec{b}} = \vec{t}^0+\vec{b} -\vec{A} \vec...
... &\beta = 1-\vec{b}^T\vec{y}^0 +\vec{c}^T \vec{x}^0 \end{split}\end{displaymath} (59)

と定義する. 続いて, 行列$ \vec{M}$およびベクトル$ \vec{q}$

$\displaystyle \vec{M}= \begin{bmatrix}\vec{0}& \vec{A} & -\vec{b}&\bar{\vec{b}}...
...matrix}\begin{array}{c} \vec{0}\ \vec{0}\ 0\ n+m+2 \end{array} \end{bmatrix}$ (60)

と定義し, 次の問題を考える.

$\displaystyle \min \left \{ \vec{q}^T \vec{\xi}: \vec{M} \vec{\xi} + \vec{q} \geq \vec{0}, \vec{\xi} \geq \vec{0} \right \}$ (61)

ここに, $ \vec{\xi}=[\vec{y}^T, \vec{x}^T, \kappa, \theta]^T$$ n+m+2$ 次元のベクトルである.

$ \vec{\xi}$の初期値を

$\displaystyle \vec{\xi}^0:= [\vec{y}^0, \vec{x}^0, 1, 1]^T$ (62)

とおくと, $ \vec{\xi}^0$は問題(61)の内点となる. これを示そう.

$\displaystyle \vec{M} \vec{\xi}^0 +\vec{q}= \left [ \begin{array}{c} \vec{A}\ve...
...ta \ -\bar{b}^T\vec{y}^0-\bar{c}^T\vec{x}^0-\beta+(n+m+2) \end{array} \right ]$ (63)

であるが, $ \bar{b}$, $ \bar{c}$および $ \bar{\beta}$の定義により,

\begin{displaymath}\begin{array}{rcl} \vec{A}\vec{x}^0-b+\bar{b} &=&\vec{t}^0\ ...
...\ \vec{b}^T\vec{y}^0-\vec{c}^T\vec{x}^0 +\beta&=&1 \end{array}\end{displaymath} (64)

である. 最後に,

\begin{displaymath}\begin{array}{l} -\bar{b}^T\vec{y}^0-\bar{c}^T\vec{x}^0-\beta...
...T\vec{y}^0 -\vec{c}^T\vec{x}^0 + n+m+2 \ \quad = 1 \end{array}\end{displaymath} (65)

により, 所望の結果が得られる.

以上によって, 主問題と双対問題を解くことが 内点を持つ歪対称問題を解くことに帰着されたことになる.

さて, (61)を利用して, 本節の目標であった双対定理を示そう.

定理 23 主問題(P)および双対問題(D)に対し, 次の1, 2 のいずれかが成り立つ.
  1. 主問題(P), 双対問題(D)は最適解 $ \vec{x}^{\ast}$, $ \vec{y}^{\ast}$を持ち, $ \vec{b}^T\vec{y}^{\ast}=\vec{c}^T\vec{x}^{\ast}$となる.
  2. 主問題(P), 双対問題(D)のいずれか, あるいは両方とも解を持たない.

[証明] (61)が自明な解 $ \vec{\xi}=\vec{0}$を持ち, 目的関数の最適値が0であることと, 定理17により(61)が強相補解を持つこと を利用する. (61)の強相補解を $ [\bar{\vec{y}}^T,\bar{\vec{x}}^T,\bar{\kappa},\bar{\theta}]$ とする. 目的関数の最適値が0であることから, $ \bar{\theta}=0$である. よって, (61) の制約条件は

$\displaystyle \begin{bmatrix}0 & \vec{A} & -\vec{b} \ -\vec{A}^T & 0 & \vec{c}...
...r{\kappa} \end{bmatrix} \geq \begin{bmatrix}\vec{0}\ \vec{0}\ 0 \end{bmatrix}$ (66)

に帰着される. 主問題と双対問題に解があるか否かは $ \bar{\kappa}$の値に依存する.

$ \bar{\kappa}>0$のとき: この場合, (66)の両辺を $ \bar{\kappa}$で割ることにより, 主問題(P)と双対問題(D)の解が復元される. すなわち, 主問題(P)と双対問題(D)はともに有限の最適解を持つ.

$ \bar{\kappa}=0$のとき: $ \bar{\kappa}=0$を(66)に 代入すると $ \vec{A} \bar{\vec{x}} \geq \vec{0}$, $ \vec{A}^T \bar{\vec{y}}\leq \vec{0}$が成り立つが, さらに, 強相補解の性質から,

$\displaystyle \begin{bmatrix}\bar{\vec{y}}\ \bar{\vec{x}}\ 0 \end{bmatrix} + ...
...\vec{x}}\ 0 \end{bmatrix} > \begin{bmatrix}\vec{0}\ \vec{0}\ 0 \end{bmatrix}$ (67)

となる. このとき, もし $ \vec{b}^T \bar{\vec{y}} \leq 0$かつ $ \vec{c}^T \bar{\vec{x}} \geq 0$であれば, $ \vec{c}^T \bar{\vec{x}} -\vec{b}^T \bar{\vec{y}} \geq 0$となり, これは(67)の第3式と矛盾する. したがって, $ \vec{b}^T \bar{\vec{y}}>0$ $ \vec{c}^T \bar{\vec{x}} < 0$の少なくとも一方が成り立つ.

まず $ \vec{b}^T \bar{\vec{y}}>0$の場合を考える. このとき, 主問題(P)は解を持たず, 双対問題(D)は有限の最適解を持たない. これを示そう. まず, 主問題(P)は解を持たない ことを背理法によって示す. 主問題(P)が解$ \vec{x}$を持ったとすると, $ \vec{x} \geq \vec{0}$, $ \vec{A}^T \bar{\vec{y}}\leq \vec{0}$より,

$\displaystyle 0 \geq \vec{x}^T(\vec{A}^T \bar{\vec{y}})
=(\vec{A} \vec{x})^T \bar{\vec{y}} \geq \vec{b}^T \bar{\vec{y}} >0
$

であり, $ 0 > 0$となって矛盾である. したがって主問題(P)は解を持たない. 続いて, 双対問題(D)が解を持つときには有限の最適解が存在しないことを示す. $ \vec{y}$が双対問題(D)のひとつの解とする. このとき, $ \vec{A}^T \bar{\vec{y}}\leq \vec{0}$より, 任意の正数$ \alpha$に対し, $ \vec{y}+\alpha \bar{\vec{y}}$も 双対問題(D)の解である. さて, 解 $ \vec{y}+\alpha \bar{\vec{y}}$に対する目的関数の 値は $ \vec{b}^T(\vec{y}+\alpha \bar{\vec{y}})$であるが, $ \vec{b}^T \bar{\vec{y}}>0$より, これは 任意の大きい値を取りうる. したがって, この場合, 双対問題(D)は有限の最適値を持たない.

続いて, $ \vec{c}^T \bar{\vec{x}} < 0$の場合を考える. このとき, 双対問題(D)は解を持たず, 主問題(P)は有限の最適解を持たない. これを示そう. まず双対問題(D)は解を持たないことを背理法によって示す. 双対問題(D)が解$ \vec{y}$を持ったとすると, $ \vec{y} \geq \vec{0}$, $ \vec{A} \bar{\vec{x}} \geq \vec{0}$より,

$\displaystyle 0 \leq \vec{y}^T(\vec{A} \bar{\vec{x}})=(\vec{A}^T\vec{y})^T\bar{\vec{x}} \leq \vec{c}^T\bar{\vec{x}} <0
$

より, $ 0<0$となって矛盾である. よって双対問題(D)は解を持たない. 続いて, 主問題(P)に解があれば有限の最適解は存在しないことを見る. $ \vec{x}$を主問題(P)のひつつの解とする. このとき, $ \vec{A} \bar{\vec{x}} \geq \vec{0}$より, 任意の正数$ \alpha>0$に対し, $ \vec{x}+\alpha \bar{\vec{x}}$も主問題(P)の解である. この解に対応する目的関数の値は $ \vec{c}^T(\vec{x}+\alpha \bar{\vec{x}})$であるが, $ \vec{c}^T \bar{\vec{x}} < 0$より, 目的関数が任意の小さい値を取りうることがわかる. したがって, この場合, 主問題(P)は有限の最適解を持たない.

以上をまとめると,

という3種類の状況しかありえないことがわかる. これらをまとめて, 定理の結論が得られる. ///

定理23の証明から直ちに次の結論が導かれる.

系 24 $ (\bar{\vec{y}},\bar{\vec{x}},\bar{\kappa},0)$を (61)の強相補解とする. このとき, $ \bar{\kappa} \neq 0$であれば, $ \bar{\vec{x}}/\bar{\kappa}$ は主問題(P)の最適解であり, $ \bar{\vec{y}}/\bar{\kappa}$は 双対問題(D)の最適解である. $ \bar{\kappa}=0$のときには, 主問題(P)および双対問題(D)は ともに有限の最適解を持たない.

24より, 与えられた線形計画問題(主問題)を 解くことは, 問題(61)の強相補解をひとつ見つける 問題に帰着されたことになる. では, どのようにして強相補解を数値的 に求めたらよいのであろうか. この方法について議論することが 次節の主題である.


next up previous
: 歪対称問題の数値解法 : 内点法 : 歪対称問題
Shigeru HANBA 平成25年12月22日