next up previous
Next: Dikinステップ法の意味 Up: 内点法 Previous: 内点法のアルゴリズム


線形計画問題(SP)の意味

本節では, 第2.4節の 行列$ \vec{M}$などの意味についていくつかの証明を省いた上で述べる。 この節は実験そのものには関係ないので, 興味のない読者は読み飛ばしてよい。

主問題(P)とその双対問題(D)が与えられているものとする。 主問題の制約条件( $ \vec{A}\vec{x}\geq \vec{b}, \vec{x} \geq \vec{0}$)を満たす 点の集合を$ {\cal{P}}$と書き, 双対問題の制約条件 ( $ \vec{A}^T\vec{y}\leq \vec{c}, \vec{y} \geq \vec{0}$)を満たす 点の集合を$ {\cal{D}}$と書く。 $ {\cal{P}}$$ {\cal{D}}$が空集合となることもある。 このような場合には, 主問題や双対問題には解が存在しない。

さて, 適当に取られた $ \vec{x} \in {\cal{P}}$ $ \vec{y}\in {\cal{D}}$に対し, $ \vec{b}^T\vec{y} \leq (\vec{x}^T \vec{A}^T)\vec{y} =
\vec{x}^T (\vec{A}^T\vec{y}) \leq \vec{x}^T \vec{c}$より, $ \vec{b}^T\vec{y}\leq \vec{c}^T\vec{x}$という不等式が 成り立つことがわかる。すなわち, 双対問題の目的関数値は 必ず主問題の目的関数値以下となる。 このことから, ある $ \vec{x}^{\ast} \in {\cal{P}}$ $ \vec{y}^{\ast} \in {\cal{D}}$が等式 $ \vec{b}^T\vec{y}^{\ast}=\vec{c}^T\vec{x}^{\ast}$ を満たせば, $ \vec{x}^{\ast}$は主問題の最適解であり, $ \vec{y}^{\ast}$は双対問題の最適解である ということがわかる。実は, この逆も成り立つ。 すなわち, 主問題と双対問題がそれぞれ有限の最適解 $ \vec{x}^{\ast}$ $ \vec{y}^{\ast}$を 持つとき, 等式 $ \vec{b}^T\vec{y}^{\ast}=\vec{c}^T\vec{x}^{\ast}$ が成り立つということが言える。後半の結果を双対定理という。 双対定理の証明はやや繁雑なのでここでは述べない。

さて, 最適解のための等式 $ \vec{b}^T\vec{y}=\vec{c}^T\vec{x}$ に不等号を追加した不等式

$\displaystyle \vec{b}^T\vec{y}\geq \vec{c}^T\vec{x}$ (43)

を考えよう。 不等式 $ \vec{b}^T\vec{y}\leq \vec{c}^T\vec{x}$はつねに成り立つのだから, これは実質的にもとの等式と変わらない。 (45)の右辺を左辺に移項し, 主問題の制約条件, 双対問題の制約条件の両辺に$ -1$を乗じたものと合わせて整理すると,

\begin{displaymath}
\begin{split}
\vec{A}\vec{x}-\vec{b} &\geq \vec{0} \\
-\v...
...c{0} \\
\vec{b}^T\vec{y}-\vec{c}^T\vec{x} &\geq 0
\end{split}\end{displaymath}

という不等式が得られる。これを行列の形でまとめると,

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

という形になる。この段階ではまだ(46) が解を持つかどうかは明らかでないことに注意しよう。

ここで, (46)の左辺のベクトルの最下段にあらわれた数$ 1$を 変数$ \kappa$で置き変えた不等式

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

を考える。(47)を満たす $ (\vec{y}^T,\vec{x}^T,\kappa)$が 求められていて, かつ$ \kappa >0$であれば, $ (\vec{y}^T/\kappa,\vec{x}^T/\kappa,1)$は(46)を満たす。 すなわち, 新しい変数$ \kappa$を導入することは もとの問題(46)の解を求めることの障害とはならない。 では, 新しい変数$ \kappa$を導入することには何か利点はあるのだろうか。 まず(47)が自明な解 $ \vec{x}=\vec{0}$, $ \vec{y}=\vec{0}$, $ \kappa=0$を持つことに注意する。 ところで, 内点法を用いて問題(47)の解を求めると, 問題(46)に解があるときには$ \kappa$は零以外の値に収束し, 問題(46)に解がないときには$ \kappa$は零に収束することが示せる(証明は略す)。 すなわち, $ \kappa$を(46)の解の存在判定に使うことができる。

さて, (47)の左端の行列は 先に内点法のアルゴリズムで使った (35)と似てはいるが, 同一ではない。 (35)の行列$ \vec{M}$の右端および下段 の要素は(47)にはないものである。これはどのような 経緯で出て来たのだろうか?

実は, 線形計画問題を内点法で解くためには初期値として 制約領域の内点(制約条件から等号を取り除いた不等式を満たす点) が必要になるのだが, 内点を1個定めることはそれほど容易でない。 そのため, 代替策として, 新たに変数を1個追加して, (47)から内点が既知の拡大された問題に変換する。 (35)は(47)にそのような手法を適用した結果 なのである。以下では, この方法について見てゆこう。

初期値 $ \vec{x}^0 > \vec{0}$, $ \vec{y}^0 > \vec{0}$を適当に決め (各成分が0でなければ何でもよい), $ \vec{p}^0=1/\vec{x}^0$, $ \vec{t}^0=1/\vec{y}^0$とおく。パラメータ $ \bar{\vec{b}}$, $ \bar{\vec{c}}$, $ \beta$を(34) によって定義する。また, 行列$ \vec{M}$およびベクトル$ \vec{q}$を (35)によって決め, (36)によって定められた問題(SP)を考える。 すると, 初期値

$\displaystyle \vec{\xi}^0= \begin{bmatrix}\vec{y}^0 \vec{x}^0 1 1 \end{bmatrix}$ (46)

が問題(36)の内点となるのである。これを見ておこう。 $ \vec{\xi}^0>\vec{0}$は定義より明らかだから, $ \vec{M} \vec{\xi}^0 +\vec{q}>\vec{0}$となることを見ればよい。 これは, (34)を使えば,

\begin{displaymath}\begin{split}\vec{M} \vec{\xi}^0 +\vec{q}&= \begin{bmatrix}\v...
...atrix}\vec{t}^0 \vec{p}^0 1 1 \end{bmatrix} \end{split}\end{displaymath} (47)

となることからわかる。


next up previous
Next: Dikinステップ法の意味 Up: 内点法 Previous: 内点法のアルゴリズム
Shigeru HANBA
平成15年11月16日