next up previous
Next: 実験 Up: 内点法のアルゴリズムの一般形 Previous: アフィンスケーリング方向と中心化方向


アルゴリズムの一般形

アフィンスケーリング方向は目的関数を減少させる方向, 中心化方向は中心パスに向かう方向であった。 Newton法型の内点法のアルゴリズムでは, アフィンスケーリング方向と中心化方向の線形結合 を使って解を更新してゆく。

$ \sigma$を0以上1以下の定数とし, 探索ベクトルを

$\displaystyle \begin{bmatrix}\vec{\Delta \xi} \\ \vec{\Delta s} \end{bmatrix} =...
... \sigma \begin{bmatrix}\vec{\Delta \xi}_{c} \\ \vec{\Delta s}_{c} \end{bmatrix}$ (84)

とすると, 探索ベクトル $ (\vec{\Delta \xi}^{T},\vec{\Delta s}^{T})^T$

$\displaystyle \begin{bmatrix}\vec{M} & -\vec{I}\\ \vec{S} & \vec{\Xi} \end{bmat...
... = \begin{bmatrix}\vec{0} \\ -\vec{s}\vec{\xi}+\sigma \mu \vec{1} \end{bmatrix}$ (85)

の解となる。

なお, (78)は $ \vec{\Delta \xi}$ $ \vec{\Delta s}$に 関する線形方程式であるが, (78)の上半分は $ \vec{\Delta s}$について解けて $ \vec{\Delta s}=\vec{M} \vec{\Delta \xi}$となるので, 実際にはこれを(78)の下半分に代入した

$\displaystyle \begin{pmatrix}\vec{S} +\vec{\Xi}\vec{M} \end{pmatrix} \vec{\Delta \xi} = -\vec{s}\vec{\xi}+\sigma \mu \vec{1}$ (86)

$ \vec{\Delta \xi}$について解けばよい。

(78)の解 $ (\vec{\Delta \xi}^{T},\vec{\Delta s}^{T})^T$を探索ベクトルとして 利用する内点法のアルゴリズムの一般形は, 以下に述べるようなものである。

\fbox{内点法(一般形)}

(初期化)
精度パラメータ $ \varepsilon$を適当に決める。 また, $ \vec{\xi} :=\vec{\xi}^0$, $ \vec{s}:=\vec{s}(\vec{\xi} )$とする。
(ループ)
以下のプログラムを実行する。

        while 
$ \vec{\xi}^T\vec{s} \geq \varepsilon$ do

$ \sigma$を決める
$ \mu := \vec{s}^T\vec{\xi}/(n)$とする
(79)を解いて $ \vec{\Delta \xi}$, $ \vec{\Delta s}$を決める
$ \alpha$を決める
$ \vec{\xi} :=\vec{\xi} +\alpha \vec{\Delta \xi} $
$ \vec{s} :=\vec{s} +\alpha \vec{\Delta s} $
end

2.4.1節で述べたショートステップ パス追跡法は, 上記のアルゴリズムにおいて $ \alpha=1$, $ \sigma=1-0.4/\sqrt{\mathop {\rm dim}\vec{\xi}}$ と固定した特別な場合である。大規模な問題では, このように$ \sigma$を決めると, 探索ベクトルが中心化方向とほぼ一致してしまうため, ショートステップパス追跡法は極めて低速になる。

ループ内の各ステップでパラメータ$ \alpha$$ \sigma$の値を切り換えると, より効率の良いアルゴリズムが構成しうることが知られている。 興味のある読者はたとえば文献[3,6,7]を参照してほしい。

例 3   2変数の歪対称問題

\begin{displaymath}\begin{split}&\min \left \{ \begin{bmatrix}1 \\ 0\end{bmatrix...
...} \geq \begin{bmatrix}0 \\ 0\end{bmatrix} \right \} \end{split}\end{displaymath} (87)

を考える。

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

この問題において, 各点でアフィンスケーリング方向と中心化方向がどのように なるかを見よう。 この問題における中心パスは$ \xi_2=1/2$という直線であり, 強相補解は $ (\xi_1,\xi_2)=(0,1/2)$という点である。 図3に各点におけるアフィンスケーリング方向と中心化方向を示す。 この例ではアフィンスケーリング方向は中心パスと平行になる。 それゆえ, アフィンスケーリング方向のみを用いて解を更新すると 強相補解に到達できない。また, $ \mu=(1/2)\vec{s}^T\vec{\xi}$の 場合の中心化方向は中心パスと垂直となり, これを用いて解を更新すると 目的関数は減少しない。

図 3: 各点における探索ベクトルの方向
\includegraphics[scale=1]{affine-dir0.eps}
(a)アフィンスケーリング方向
\includegraphics[scale=1]{center-dir0.eps}
(b)中心化方向


next up previous
Next: 実験 Up: 内点法のアルゴリズムの一般形 Previous: アフィンスケーリング方向と中心化方向
Shigeru HANBA
平成16年3月19日