next up previous
: ロングステップパス追跡法 : 歪対称問題の数値解法 : アフィンスケーリング方向と中心化方向


ショートステップパス追跡法

ショートステップパス追跡法は, アルゴリズム25において,

$\displaystyle \sigma=1-\theta/\sqrt{n}, \quad \alpha=1$ (75)

とすることによって得られるアルゴリズムである. パラメータ$ \theta$は, たとえば0.4とすればよい (この数値の根拠については定理32で述べる).

アルゴリズム 27 (ショートステップパス追跡法) 精度パラメータ $ \varepsilon$を適当に決め, 中心パス上の初期値 $ \vec{\xi} =\vec{\xi}^0$, $ \vec{s} = \vec{s} (\vec{\xi})$を取る. 続いて, $ \sigma= 1-0.4/\sqrt{n}$ とおき, 以下のループを実行する.
    while 
$ \vec{\xi}^T\vec{s} \geq \varepsilon$ do

$ \mu := \vec{s}^T\vec{\xi}/n$
$ \vec{\xi} :=\vec{\xi} + \vec{\Delta \xi} $
$ \vec{s}:=\vec{s}(\vec{\xi} )$
end
ここに, $ \vec{\Delta \xi}$, $ \vec{\Delta s}$は線形方程式 (73)の解である.

さて, 以下ではショートステップパス追跡法において, 解が中心パスのある近傍を外れることがないということと, $ \mu $が零に収束することを示すのだが, そのためにはいくつか準備が必要である.

まず最初に, ある$ \mu $に対する中心パスの $ {\cal N}_2(\theta)$近傍を,

\begin{displaymath}\begin{split}{\cal N}_2(\theta, \mu)=\{(\vec{\xi},\vec{s}): \...
...vec{s}>\vec{0}, \vec{s}=\vec{M}\vec{\xi}+\vec{q} \} \end{split}\end{displaymath} (76)

と定義する. $ \sigma=1-\theta/\sqrt{n}$としたときの (73)の解 $ \vec{\Delta \xi}$, $ \vec{\Delta s}$に対し,

$\displaystyle \widetilde{\vec{\xi}}=\vec{\xi}+\vec{\Delta \xi}, \quad \widetild...
...c{\Delta s}, \quad \widetilde{\mu}=\widetilde{\vec{\xi}}^T\widetilde{\vec{s}}/n$ (77)

とおく. (73)の第1式と$ \vec{M}$が歪対称行列であることから,

$\displaystyle \vec{\Delta s}^T\vec{\Delta \xi}=0$ (78)

となることに注意する. また, $ \vec{1}^T\vec{1}=n$であり, $ \vec{1}^T(\vec{\xi}\vec{s})=n \mu$である( $ \mu=\vec{\xi}^T\vec{s}/n$に注意).

まず$ \mu $が零に収束することを見よう.

定理 28 ショートステップパス追跡法により, $ \mu $は 指数関数の速さで零に漸近する.

[証明] $ \mu $ $ \widetilde{\mu}$の関係を求めればよい. (77)と(78)より,

$\displaystyle n \widetilde{\mu}= (\vec{\xi}+\vec{\Delta \xi})^T(\vec{s}+\vec{\Delta s}) =n\mu+(\vec{\xi}^T\vec{\Delta s}+\vec{s}^T\vec{\Delta \xi})$ (79)

である. ここで $ \vec{\xi}^T\vec{\Delta s}=\vec{1}^T\vec{\Xi}\vec{\Delta s}$, $ \vec{s}^T\vec{\Delta \xi}=\vec{1}^T\vec{S}\vec{\Delta \xi}$ に注意すると, (73)の第2式から,

$\displaystyle \vec{\xi}^T\vec{\Delta s}+\vec{s}^T\vec{\Delta \xi}= \vec{1}^T (-\vec{s}\vec{\xi}+\sigma \mu \vec{1})=-n \mu+\sigma n \mu$ (80)

となる. (80)を(79)に代入し, 両辺を$ n$で割ると,

$\displaystyle \widetilde{\mu}=\sigma \mu$ (81)

が得られる. (81)に$ \sigma$の値(75)を代入すると,

$\displaystyle \widetilde{\mu}=(1-\theta/\sqrt{n})\mu$ (82)

となる. よって, 第$ k$解目の繰り返しにおける$ \mu $の値を$ \mu_k$, $ \mu $の初期値を$ \mu_0$とすると, $ \mu_k=(1-\theta/\sqrt{n})^k \mu_0$ となる. $ n \geq 1$のときは $ 0 < 1-\theta/\sqrt{n} < 1$だから, $ \mu $は指数関数の速さで零に漸近する. ///

注意 29 $ \mu $の初期値が正であることから, $ \mu $は有限回の繰り返しでは零にならない(つねに正の値を取る). また, アルゴリズムの停止条件は「$ \mu $が指定された値以下になったら終了」であったから, 有限回の繰り返し計算によってアルゴリズムが終了することがわかる.

続いて, $ (\vec{\xi},\vec{s}) \in {\cal N}_2(\theta)$のとき, $ (\widetilde{\vec{\xi}},\widetilde{\vec{s}}) \in {\cal N}_2(\theta)$ となることを見る. このために, いくつか補題を準備する.

補題 30 ベクトル$ \vec{u}$, $ \vec{v}$ $ \vec{u}^T\vec{v} \geq 0$をみたすとき,

$\displaystyle \Vert\vec{u}\vec{v}\Vert \leq 2^{-3/2}\Vert\vec{u}+\vec{v}\Vert^2$ (83)

が成り立つ.

[証明] $ {\cal P}=\{i: u_i v_i \geq 0\}$, $ {\cal N}=\{i: u_i v_i < 0\}$とする.

$\displaystyle \vec{u}^T\vec{v}
=\sum_{i \in {\cal P}}u_i v_i+\sum_{i \in {\cal ...
... \in {\cal P}}\vert u_i v_i\vert-\sum_{i \in {\cal N}}\vert u_i v_i\vert\geq 0
$

より,

$\displaystyle \sum_{i \in {\cal P}}\vert u_i v_i\vert \geq \sum_{i \in {\cal N}}\vert u_i v_i\vert$ (84)

である. 一方,

\begin{displaymath}
\begin{split}
\Vert\vec{u}\vec{v}\Vert
&=\left (\sum_{i \in{...
... N}} \vert u_i v_i \vert \right )^2 \right )^{1/2}
\end{split}\end{displaymath}

であるが, ここで(84)を使い, $ u_i v_i \geq 0$のときには, $ \vert u_i v_i\vert \leq (1/4)(u_i + v_i)^2$であることに注意すると,

\begin{displaymath}
\begin{split}
\Vert\vec{u}\vec{v}\Vert
&\leq \left ( 2\left ...
...ight )
\leq 2^{-3/2}\Vert \vec{u}+\vec{v} \Vert^2
\end{split}\end{displaymath}

となる. ///

補題 31 (77)の $ \widetilde{\vec{\xi}}$, $ \widetilde{\vec{s}}$

$\displaystyle \Vert\widetilde{\vec{\xi}}\widetilde{\vec{s}}-\widetilde{\mu}\vec{1}\Vert \leq \frac{\mu}{\sqrt{2}} \frac{\theta^2}{1-\theta}$ (85)

を満たす.

[証明] (81)より,

\begin{displaymath}
\begin{split}
\widetilde{\xi}_i \widetilde{s}_i-\widetilde{\...
..._i \Delta s_i -\sigma \mu
=\Delta \xi_i \Delta s_i
\end{split}\end{displaymath}

となるから,

$\displaystyle \widetilde{\vec{\xi}}\widetilde{\vec{s}}-\widetilde{\mu}\vec{1}=\vec{\Delta \xi}\vec{\Delta s}$ (86)

である.

続いて, $ \Vert\vec{\Delta \xi}\vec{\Delta s}\Vert$を評価しよう. $ \vec{D}=\vec{\Xi}^{1/2}\vec{S}^{-1/2}$とおくと, $ \vec{\Delta \xi}\vec{\Delta s}
=\left ( \vec{D}^{-1}\vec{\Delta \xi} \right )
\left ( \vec{D}\vec{\Delta s} \right )$ であるが, ここで $ \left ( \vec{D}^{-1}\vec{\Delta \xi} \right )^T\left ( \vec{D}\vec{\Delta s} \right )
=\vec{\Delta \xi}^T\vec{\Delta s}=0
$ となることに注意し, 補題30を使うと,

$\displaystyle \Vert\vec{\Delta \xi}\vec{\Delta s}\Vert \leq 2^{-3/2}\Vert\vec{D}^{-1}\vec{\Delta \xi}+\vec{D}\vec{\Delta s}\Vert^2$ (87)

となる. 一方, (73)の第2式を使うと,

\begin{displaymath}\begin{split}\vec{D}^{-1}\vec{\Delta \xi}+\vec{D}\vec{\Delta ...
...eft ( -\vec{s}\vec{\xi}+\sigma \mu \vec{1} \right ) \end{split}\end{displaymath} (88)

となるから, これを(87)に代入すると,

$\displaystyle \Vert\vec{\Delta \xi}\vec{\Delta s}\Vert \leq 2^{-3/2}\sum_{i} \frac{(-s_i \xi_i+\sigma \mu)^2}{\xi_i s_i}$ (89)

となる. 一方, $ (\vec{\xi},\vec{s}) \in {\cal N}_2(\theta,\mu)$より, 各$ i$に対し, $ \vert\xi_i s_i - \mu\vert \leq \theta \mu$, ゆえに $ -\theta \mu \leq \xi_i s_i - \mu \leq \theta \mu$ であり, したがって $ \xi_i s_i \geq (1-\theta)\mu$である. これを (89)に代入すると,

$\displaystyle \Vert\vec{\Delta \xi}\vec{\Delta s}\Vert \leq \frac{2^{-3/2} \Vert-\vec{s}\vec{\xi}+\sigma \mu \vec{1}\Vert}{(1-\theta)\mu}^2$ (90)

となる. ところで, $ \vec{1}^T(\vec{\xi}\vec{s})=n \mu$, $ \vec{1}^T\vec{1}=n$に注意すると, $ \vec{1}^T(\vec{\xi}\vec{s}-\mu \vec{1})=0$となるから,

\begin{displaymath}
\begin{split}
\Vert\vec{s}\vec{\xi}-\sigma \mu \vec{1}\Vert^...
... \vec{1})\Vert^2+\Vert(1-\sigma) \mu \vec{1}\Vert^2
\end{split}\end{displaymath}

となる. さらに, $ (\vec{\xi},\vec{s}) \in {\cal N}_2(\theta,\mu)$であることを使うと,

$\displaystyle \Vert\vec{s}\vec{\xi}-\sigma \mu \vec{1}\Vert^{2} \leq\theta^2\mu^2+n (1-\sigma)^2 \mu^2$ (91)

が得られる. (91)を(90)に代入すると

$\displaystyle \Vert\vec{\Delta \xi} \vec{\Delta s}\Vert\leq
2^{-3/2}\mu \frac{\theta^2+n(1-\sigma)^2}{1-\theta}
$

が得られる. ここに(75)を代入すると,

$\displaystyle \Vert\vec{\Delta \xi} \vec{\Delta s}\Vert\leq \frac{\mu}{\sqrt{2}} \frac{\theta^2}{1-\theta}$ (92)

となる.

(86)と(92)を合わせて, (85)が得られる. ///

以上の準備のもとで, 次の定理を示そう.

定理 32 $ \theta=0.4$とすると, ショートステップパス追跡法の各ステップにおいて, $ (\vec{\xi},\vec{s}) \in {\cal N}_2(\theta,\mu)$となる.

[証明] 初期値は中心パス上にあるから, 初期値については定理は明らかに成り立つ.

次に, $ \theta=0.4$とすると, $ (\vec{\xi},\vec{s}) \in {\cal N}_2(\theta,\mu)$であれば $ (\widetilde{\vec{\xi}},\widetilde{\vec{s}}) \in {\cal N}_2(\theta,\widetilde{\mu})$であることを見る. このためには, 任意の$ n \geq 1$に対して

$\displaystyle \frac{\mu}{\sqrt{2}} \frac{\theta^2}{1-\theta} \leq (1-\theta/\sqrt{n})\theta \mu$ (93)

が成り立つような$ \theta$を求めればよい. さて, (93)の両辺を $ \theta \mu$で割り, $ n \geq 1$ に注意すると, $ 1-\theta \leq 1-\theta/\sqrt{n}$より,

$\displaystyle \frac{1}{\sqrt{2}}\frac{\theta}{1-\theta} \leq 1-\theta$ (94)

であれば (93)が成り立つことがわかる. そこで, (94)が成り立つための$ \theta$に関する条件を求めよう. (94)は

$\displaystyle \theta^2-\left (2+\frac{1}{\sqrt{2}} \right )\theta + 1 \geq 0$ (95)

と整理できるが, ここで $ 0 < \theta < 1$でなければならないことに注意すると, (95)を満たす$ \theta$の条件は,

\begin{displaymath}\begin{split}0 < \theta \leq \frac{1}{2}\left ( (2+1/\sqrt{2}...
...qrt{2 \sqrt{2}+\frac{1}{2}} \right ) \leq \theta <1 \end{split}\end{displaymath} (96)

となる. (96)を数値的に評価すると,

$\displaystyle 0 < \theta \leq 0.441, \quad 2.266 \leq \theta < 1$ (97)

となる. (97)の第2の不等式は解を持たないから, 結局, $ 0 < \theta \leq 0.441$でなければならない. $ \theta=0.4$は確かにこの条件を満たす.

さて, (93)において, $ 1-\theta/\sqrt{n}=\sigma$, $ \sigma \mu=\widetilde{\mu}$ であることに注意し, 補題31を用いると,

$\displaystyle \Vert\widetilde{\vec{\xi}}\widetilde{\vec{s}}-\widetilde{\mu}\vec{1}\Vert \leq \theta \widetilde{\mu}$ (98)

が成り立つ. また,

\begin{displaymath}
\begin{split}
\widetilde{\vec{s}}&=\vec{s}+\vec{\Delta s}=\...
... \xi})+\vec{q}=\vec{M}\widetilde{\vec{\xi}}+\vec{q}
\end{split}\end{displaymath}

である. さらに, (98)より, $ -\theta \widetilde{\mu} \leq \widetilde{\xi}_i \widetilde{s}_i - \widetilde{\mu} \leq \theta \widetilde{\mu}$ であり, したがって $ (1-\theta )\widetilde{\mu} \leq \widetilde{\xi}_i \widetilde{s}_i$であるが, ここで(81)を用いると, $ \widetilde{\xi}_i \widetilde{s}_i \geq (1-\theta)\sigma \mu >0$となる. よって $ \widetilde{\vec{\xi}}>\vec{0}$, $ \widetilde{\vec{s}}>\vec{0}$である. 以上によって $ (\widetilde{\vec{\xi}},\widetilde{\vec{s}}) \in {\cal N}_2(\theta,\widetilde{\mu})$ であることが示された. ///


next up previous
: ロングステップパス追跡法 : 歪対称問題の数値解法 : アフィンスケーリング方向と中心化方向
Shigeru HANBA 平成25年12月22日