next up previous
Next: 予習事項 Up: Newton法に基づく内点法の一般的なアルゴリズム 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}$ (56)

とすると, 探索ベクトル $ (\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}$ (57)

の解となる。

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

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

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

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

内点法(Newton法による解法)

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

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

begin
$ \sigma$を決める
$ \mu := \vec{s}^T\vec{\xi}/(n)$とする
(61)を解いて $ \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$の値を切り換えると, より効率の良いアルゴリズムが構成しうることが知られている。 興味のある読者はたとえば文献[2,5,6]を参照してほしい。

例 4   例3の歪対称問題を用いて, アフィンスケーリング方向と中心化方向の各点における変動を見よう。 まず最初に, 例3の問題(51)において, 中心パスは$ \xi_2=1/2$という直線であり, 強相補解は $ (\xi_1,\xi_2)=(0,1/2)$という点である。 図3に各点におけるアフィンスケーリング方向と中心化方向を示す。 この例ではアフィンスケーリング方向は中心パスと平行になる。 それゆえ, アフィンスケーリング方向のみを用いて解を更新すると 強相補解に到達できない。また, $ \mu=(1/2)\vec{s}^T\vec{\xi}$の 場合の中心化方向は中心パスと垂直となり, これを用いて解を更新すると 目的関数は減少しない。
図 3: 各点における探索ベクトルの方向
\includegraphics{affine-dir0.eps}
(a)アフィンスケーリング方向
\includegraphics{center-dir0.eps}
(b)中心化方向
$ \blacktriangleleft$


next up previous
Next: 予習事項 Up: Newton法に基づく内点法の一般的なアルゴリズム Previous: アフィンスケーリング方向と中心化方向
Shigeru HANBA
平成15年11月16日