next up previous
: ショートステップパス追跡法 : 歪対称問題の数値解法 : 歪対称問題の数値解法


アフィンスケーリング方向と中心化方向

前節までの議論により, 線形計画問題を解くことが 歪対称問題の強相補解をひとつ見付けることに帰着されることが示された. 本節では, 強相補解を数値的に求める手法について議論する.

繰り返しになるが, 解くべき問題をあらためて明示しておこう. 解くべき問題は,

(SP)$\displaystyle \quad \min \{ \vec{q}^T \vec{\xi}: \vec{M} \vec{\xi} +\vec{q} \geq \vec{0}, \vec{\xi} \geq \vec{0} \}$ (68)

である. ただし, $ \vec{M}$$ n$次の歪対称行列であり, $ \vec{q} \geq \vec{0}$, $ \vec{\xi}$$ \vec{q}$$ n$次の ベクトルとする. また, 先に述べたように, $ \vec{s} (\vec{\xi} ) = \vec{M} \vec{\xi} + \vec{q}$ とし, これをしばしば $ \vec{s} = \vec{s} (\vec{\xi})$と略記する. また, 求めるべきものは(68)の強相補解であり, 単に(68)の目的関数を最小とするのみの解では不十分である.

本節では, 歪対称問題(SP)は, 第3節で述べた, 主問題と双対問題の双方を内点が既知の問題に埋め込む手順 ((60), (61)に対応する) によって得られているものと仮定する. このような場合は $ \vec{\xi}>\vec{0}$, $ \vec{s} > \vec{0}$かつ $ \vec{\xi} \vec{s} = \vec{1}$を満たす点, すなわち$ \mu=1$に対応する中心パス上の点がすでに得られている. 本節で述べるアルゴリズムはいずれもこの点を初期値として利用する. 問題(SP)の構成法から, 内点が空でない( $ {\cal SP}^{+} \neq \emptyset$) ことは明らかである. よって, 第2節で述べた議論の結果は すべて適用可能である.

2節で述べたように, 中心パスは歪対称問題の 解析的中心に収束する軌道である. 解析的中心は強相補解のひとつであったから, 「目的関数を減少させ, なおかつ中心パスからなるべく離れないように解を動かす」 という戦略で最適解を探索すれば, 数値的に強相補解を求めることが できそうに思える. 実際に上述のような戦略を実行するのが内点法の 一般的なアルゴリズムである.

さて, 解析的中心は, 非線形連立方程式 $ \vec{M}\vec{\xi}-\vec{s}+\vec{q}$, $ \vec{\xi} \vec{s}= \mu \vec{1}$ $ \mu \rightarrow 0$としたときの極限であった. そこで, 現在位置から解析的中心に向かう方向を定めるために, $ \mu=0$とし, 非線形関数

\begin{displaymath}\begin{split}\vec{F}(\vec{\xi},\vec{s})= \begin{bmatrix}\vec{...
...i}-\vec{s}+\vec{q}\ \vec{s}\vec{\xi} \end{bmatrix} \end{split}\end{displaymath} (69)

の零点を求める問題を解くことを考える. 点$ \vec{\xi}$ $ \vec{s}=\vec{M}\vec{\xi}+\vec{q}$が与えられているとき, $ \vec{\xi}^{\prime} =\vec{\xi}+\vec{\Delta \xi}_{a} $および $ \vec{s}^{\prime} =\vec{s}+\vec{\Delta s}_{a} $として $ \vec{F}(\vec{\xi}^{\prime},\vec{s}^{\prime})=\vec{0}$ $ \vec{\Delta \xi}_{a}$ $ \vec{\Delta s}_{a}$について Tailor展開によって近似的に解くと, $ \vec{\Delta \xi}_{a}$ $ \vec{\Delta s}_{a}$は方程式

$\displaystyle \begin{bmatrix}\vec{M} & -\vec{I}\ \vec{S} & \vec{\Xi} \end{bmat...
...}_{a} \end{bmatrix} = \begin{bmatrix}\vec{0} \ -\vec{s}\vec{\xi} \end{bmatrix}$ (70)

の解となる. (70)を解くことによって得られる探索ベクトル $ (\vec{\Delta \xi}_{a}^T,\vec{\Delta s}_{a}^T)^T$をアフィンスケーリング方向と呼ぶ.

アフィンスケーリング方向は目的関数を減少させるには都合が良い. しかし, 制約条件を満たす領域が「曲がって」いるときには, 解をこの方向に動かすと, 解は中心パスから逸脱し, さらに制約条件を満たす領域からも外れてしまう可能性がある. このような不都合を避けるためには, 中心パス上のある点に向かう方向を定め, その方向に解を動かすのがよい. そこで, $ \mu=(1/n)\vec{s}^T\vec{\xi}$とし, この$ \mu $に対応する 中心パス上の点を求める問題を解くことを考える. この問題も, 先と同様に, 関数

\begin{displaymath}\begin{split}\vec{G}(\vec{\xi},\vec{s})= \begin{bmatrix}\vec{...
...vec{q}\ \vec{s}\vec{\xi}-\mu \vec{1} \end{bmatrix} \end{split}\end{displaymath} (71)

の零点を求める問題に帰着される. $ \vec{\xi}^{\prime} =\vec{\xi}+\vec{\Delta \xi}_{c}$, $ \vec{s}^{\prime} =\vec{s}+\vec{\Delta s}_{c}$とし, (71)をTailor展開によって近似的に解くと, $ \vec{\Delta \xi}_{c}$ $ \vec{\Delta s}_{c}$は方程式

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

の解となる. (72)を解くことによって得られる探索ベクトル $ (\vec{\Delta \xi}_{c}^{T},\vec{\Delta s}_{c}^{T})^T$を中心化方向と呼ぶ.

さて, アフィンスケーリング方向が強相補解へ向かう方向で中心化方向 が中心パスへ向かう方向であったことから, アフィンスケーリング方向と 中心化方向の線形結合を取ると, 中心パスからあまり離れずに目的関数を 減少させるという目的が達成されることがわかる. ここで, (71)と(72)を一般化した,

$\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}$ (73)

という式を考えよう. (71)は (73)の$ \sigma$に零を代入したものであり, (72)は (73)の$ \sigma$に1を代入したものである. よって, (73)の$ \sigma$を0以上1以下の値に 設定して解くことでアフィンスケーリング方向と中心化方向の 組み合わせが得られ, $ \sigma$が零に近いほどその方向は アフィンスケーリング方向に近く, 1に近いほど中心化方向に 近くなることがわかる.

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

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

$ \vec{\Delta \xi}$について解いても同じ結果が得られる. 補題5より, $ \vec{\xi}>\vec{0}$, $ \vec{s} > \vec{0}$なら, 行列 $ \vec{S} +\vec{\Xi}\vec{M}$は正則だから, (74)はつねに解を持つ.

内点法のアルゴリズムには

に応じていろいろなバリエーションがあるが, それらはおおむね 以下に述べる一般形の特別な場合になる.

アルゴリズム 25 (内点法(一般形)) 精度パラメータ $ \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$とする
(74)を解いて $ \vec{\Delta \xi}$, $ \vec{\Delta s}$を決める
$ \alpha$を決める
$ \vec{\xi} =\vec{\xi} +\alpha \vec{\Delta \xi} $
$ \vec{s} =\vec{s} +\alpha \vec{\Delta s} $
end

例 2620の問題における, 各点におけるアフィンスケーリング方向と中心化方向を 図4に示す. この例ではアフィンスケーリング方向は中心パスと平行になる. また, $ \mu=(1/2)\vec{s}^T\vec{\xi}$の 場合の中心化方向は中心パスと垂直となり, これを用いて解を更新すると 目的関数は減少しない.
図 4: 各点における探索ベクトルの方向
\includegraphics[scale=.6]{affine-dir0.eps}
(a) アフィンスケーリング方向
\includegraphics[scale=.6]{center-dir0.eps}
(b) 中心化方向

以下では, 上述の一般形に分類されるアルゴリズムの中では比較的単純な, ショートステップパス追跡法とロングステップパス追跡法について述べる.


next up previous
: ショートステップパス追跡法 : 歪対称問題の数値解法 : 歪対称問題の数値解法
Shigeru HANBA 平成25年12月22日