next up previous
Next: Newton法に基づく内点法の一般的なアルゴリズム Up: 内点法 Previous: 線形計画問題(SP)の意味


Dikinステップ法の意味

続いて, 繰り返し計算で用いられる探索ベクトル $ \hbox{\boldmath{$\Delta\xi$}}$を求める式(39)の意味を簡単に説明しておく。

$ \vec{s}(\vec{\xi})=\vec{M}\vec{\xi}+\vec{q}>\vec{0}$, $ \vec{\xi} > \vec{0}$ を満たす$ \vec{\xi}$が与えられているものとする。記法の簡単のために, $ \vec{s}(\vec{\xi})$$ \vec{s}$と略記する。 さて, $ \vec{M}$は歪対象行列だから, $ \vec{\xi}^T\vec{M}\vec{\xi}=0$となる ix) 。 ゆえに, 目的関数の値 $ \vec{q}^T\vec{\xi}$

$\displaystyle \vec{q}^T\vec{\xi}= \vec{\xi}^T\vec{s}
$

とも書ける x) 。 さて, $ \vec{\xi}$ $ \vec{\xi}+ \vec{\Delta \xi}$に変更し,

$\displaystyle \vec{\Delta s} = \vec{s}(\vec{\xi}+\vec{\Delta \xi})-\vec{s}(\vec{\xi})
$

とおくと, 目的関数の値は

$\displaystyle (\vec{\xi}+\vec{\Delta \xi})^T(\vec{s}+\vec{\Delta s})-\vec{\xi}^T\vec{s}
=\vec{\xi}^T\vec{\Delta s}+ \vec{\Delta \xi}^T\vec{ s}
$

だけ変動するxi) 。そこで, 単純に考えると, $ \vec{\xi}^T\vec{\Delta s}+ \vec{\Delta \xi}^T\vec{ s}$が 最も減少する方向に $ \vec{\Delta \xi}$を取れば良さそうに思える。 しかし, これは必ずしも望ましくない。解が制約条件を満たす領域の 境界に近付きすぎると計算効率が落ちることがあるのだが, 上述の $ \vec{\Delta \xi}$の取り方ではこの問題が考慮されていないからである。 そこで, 新たに

$\displaystyle \left \Vert \frac{\vec{\Delta \xi}}{\vec{\xi}}+\frac{\vec{\Delta s}}{\vec{s}}\right \Vert \leq 1$ (48)

という制約条件を課し, (50)を満たす領域(この領域をDikin楕円体と呼ぶ) の中から $ \vec{\xi}^T\vec{\Delta s}+ \vec{\Delta \xi}^T\vec{ s}$を最小化する $ \vec{\Delta \xi}$を求めたものが(39)である。 (50)の制約条件の形から, $ \vec{\xi}$あるいは$ \vec{s}$の 成分のうち値が0に近いものについては, 対応する $ \vec{\Delta \xi}$あるいは $ \vec{\Delta s}$の成分の値はあまり大きく取れず, 結果として$ \vec{\xi}$あるいは$ \vec{s}$が0に近付くことが抑制される。 この方法は, $ \vec{\xi}$$ \vec{s}$の大きさに応じて重みを付けた, 最急降下法の一種と考えられる。

ここで, ごく簡単な歪対称問題について, 制約領域の各点でDikin楕円体がどのような形になるかを 見ておこう。ただし, ここで取り扱うのは2変数の人工的な 歪対称問題であり, 主問題(P)と双対問題(D)から決まる歪対称問題ではない。 これは, 主問題(P)および双対問題(D)が決まる歪対称問題は最低でも4変数となり, 2次元のグラフではDikin楕円体をうまく書き表せないからである。

例 3   2変数の歪対称問題

\begin{multline}
\min \left \{
\begin{bmatrix}1  0\end{bmatrix}^T
\begin{bm...
...end{bmatrix} \geq \begin{bmatrix}0  0\end{bmatrix} \right \}
\end{multline}

を考える。

(51)の制約条件は, $ 0 \leq \xi_1$, $ 0 \leq \xi_2 \leq 1$ と書き直される。目的関数は$ \xi_1$なので, $ \xi_1=0$を満たす任意の点で目的関数は最小となる。

2に(51)の制約条件を満たす 領域の各点におけるDikin楕円体の形を示す。

図 2: 2変数の歪対称問題に対するDikin楕円体
\includegraphics{dikin.eps}
制約条件を満たす領域は図中の網のかかった領域である。 この図から, 境界に近付くにつれDikin楕円体が潰れてゆくことがわかる。


next up previous
Next: Newton法に基づく内点法の一般的なアルゴリズム Up: 内点法 Previous: 線形計画問題(SP)の意味
Shigeru HANBA
平成15年11月16日