next up previous
: 数値解に含まれる誤差の評価 : 歪対称問題の数値解法 : ショートステップパス追跡法


ロングステップパス追跡法

ロングステップパス追跡法では, ショートステップパス追跡法と異なり, ステップ幅は可変である. また, 解が束縛されるべき中心パスの近傍を ショートステップパス追跡法より大きく取る. 以下がそのアルゴリズムである.

アルゴリズム 33 (ロングステップパス追跡法) 精度パラメータ $ \varepsilon$を適当に決める. 定数$ \gamma$, $ \sigma_{\min}$, $ \sigma_{\max}$ $ 0 < \gamma < 1$, $ 0 < \sigma_{\min}< \sigma_{\max} <1$となる ように定めた上で, 以下のループを実行する.
    while 
$ \vec{\xi}^T\vec{s} \geq \varepsilon$ do

$ \mu := \vec{s}^T\vec{\xi}/n$
$ \sigma \in [\sigma_{\min},\sigma_{\max}]$を定める
$ \max \{ \alpha: (\vec{\xi}_{\alpha},\vec{s}_{\alpha}) \in {\cal N}_{-\infty} (\gamma,\mu), 0 \leq \alpha \leq 1 \}$を解く
$ \vec{\xi} :=\vec{\xi} +\alpha \vec{\Delta \xi} $
$ \vec{s}:=\vec{s}(\vec{\xi} )$
end
ここに, $ \vec{\Delta \xi}$, $ \vec{\Delta s}$は線形方程式 (73)の解である.

アルゴリズム33において$ \alpha$の最大値を求めるには2分探索などを利用すればよい.

以下では, ロングステップパス追跡法において, 解が中心パスのある近傍を外れることがないということと, $ \mu $が零に収束することを見る. このために, ある$ \gamma$に対する中心パスの $ {\cal N}_{-\infty}(\gamma)$近傍を,

\begin{displaymath}\begin{split}{\cal N}_{-\infty}(\gamma, \mu)=\{\vec{\xi},\vec...
...vec{s}>\vec{0}, \vec{s}=\vec{M}\vec{\xi}+\vec{q} \} \end{split}\end{displaymath} (99)

により定義する. 続いて, 以下の補題を準備する.

補題 34 ロングステップパス追跡法の各ステップにおいて,

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

が成り立つ.

[証明] $ \vec{\Delta \xi}^T\vec{\Delta s}=0$より, 補題30が適用可能であり, (87)および(88)を使うと,

\begin{displaymath}\begin{split}\Vert\vec{\Delta \xi}\vec{\Delta s}\Vert \leq 2^...
...2 \mu ^2 \sum _{i=1}^n \frac{1}{\xi_i s_i} \right ) \end{split}\end{displaymath} (101)

となる. ここで $ \vec{\xi}^T\vec{s}=n \mu$, $ \xi_i s_i \geq \gamma \mu$, $ 0<\sigma<1$, $ 0 < \gamma < 1$に注意すると, (101)は

$\displaystyle \begin{split}
\Vert\vec{\Delta \xi}\vec{\Delta s}\Vert
&\leq
...
...ht )\\
&\leq
2^{-3/2} n \mu \left ( 1+\frac{1}{\gamma}\right )
\end{split}$

となる. これは証明すべき不等式であった. ///

続いて,

$\displaystyle \vec{\xi}_{\alpha}=\vec{\xi}+\alpha \vec{\Delta \xi}, \quad \vec{...
...\alpha \vec{\Delta s}, \quad \mu_\alpha =\vec{\xi}_{\alpha}^T\vec{s}_{\alpha}/n$ (102)

とおく. 定義より, $ \vec{s}_{\alpha}=\vec{M}(\vec{\xi}_{\alpha}+\vec{q})$である.

定理 35 ロングステップパス追跡法の各ステップにおいて,

$\displaystyle \alpha> 2^{3/2} (\sigma/n) \gamma (1-\gamma)/(1+\gamma)$ (103)

となる. また, 繰り返し計算によって $ \mu $は零に漸近し, その速さは指数関数で上から押さえられる.

[証明] 証明をいくつかのステップに分ける.

$ \mu_{\alpha} =(1-\alpha(1-\sigma))\mu$となること: $ \vec{\Delta \xi}^T\vec{\Delta s}=0$だから,

$\displaystyle n \mu_{\alpha}=n \mu + \alpha (\vec{\Delta \xi}^T \vec{s}+\vec{\Delta s}^T \vec{\xi})$ (104)

である. 一方,

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

であり, $ \vec{1}^T(\vec{s}\vec{\xi})=n \mu$, $ \vec{1}^T\vec{1}=n$である. これらを(104)に代入して全体を$ n$で割ると,

$\displaystyle \mu_{\alpha}=\left ( 1 - \alpha (1 -\sigma ) \right ) \mu$ (105)

となる.

$ \alpha$の値が(103)を満たすこと: パラメータ$ \alpha$ $ 0 < \alpha \leq 1$かつ $ (\vec{\xi}_{\alpha},\vec{s}_{\alpha}) \in {\cal N}_{-\infty} (\gamma,\mu)$を満たす範囲で 最大化されている. ところで,

$\displaystyle g(\gamma)=\gamma (1-\gamma)/(1+\gamma)$ (106)

を区間$ [0,1]$における$ \gamma$の関数と見ると, これは $ \gamma=\sqrt{2}-1$において最大値 $ (\sqrt{2}-1)(2-\sqrt{2})/\sqrt{2}$を取る(図5).
図 5: 関数$ g(\gamma )$の形状
\includegraphics{g_gamma.eps}
また, このとき, $ 2^{3/2}\gamma (1-\gamma)/(1+\gamma)=(\sqrt{2}-1)(2-\sqrt{2}) \simeq 0.485$である. したがって, $ n \geq 1$であれば,

$\displaystyle 2^{3/2}(\sigma/n)\gamma (1-\gamma)/(1+\gamma) < 1$ (107)

である. よって,

$\displaystyle \alpha \leq 2^{3/2}(\sigma/n)\gamma (1-\gamma)/(1+\gamma)
$

なら $ (\vec{\xi}_{\alpha},\vec{s}_{\alpha}) \in {\cal N}_{-\infty} (\gamma,\mu)$ となることが言えれば, (103)が示される. これを見よう.

\begin{displaymath}\begin{split}\vec{\xi}_{\alpha} \vec{s}_{\alpha} &=(\vec{\xi}...
...vec{1}) + \alpha^2 \vec{\Delta \xi}\vec{\Delta s}\ \end{split}\end{displaymath} (108)

である. 一方, 補題34より,

$\displaystyle \vec{\Delta \xi}\vec{\Delta s} \geq - \Vert\vec{\Delta \xi}\vec{\Delta s}\xi\Vert\vec{1} \geq - 2^{-3/2} (1+1/\gamma ) n \mu \vec{1}$ (109)

が得られる. (109)を(108)に代入し, $ \vec{\xi}\vec{s} \geq \gamma \mu \vec{1}$に注意すると,

$\displaystyle \vec{\xi}_{\alpha} \vec{s}_{\alpha}
\geq
\left ( (1-\alpha) \ga...
... - \alpha^2 2^{-3/2} \left ( 1+\frac{1}{\gamma} \right) n \mu \right ) \vec{1}
$

となる. よって, (105)を使うと, $ \vec{\xi}_{\alpha} \vec{s}_{\alpha} \geq \gamma \mu_{\alpha} \vec{1}$であるためには,

\begin{displaymath}\begin{split}&\left ( 1 - \alpha (1 -\sigma ) \right ) \gamma...
...-3/2} \left ( 1+\frac{1}{\gamma} \right) n \right ) \end{split}\end{displaymath} (110)

であればよい. (110)を整理すると,

$\displaystyle \alpha^2 2^{-3/2} \left ( 1+\frac{1}{\gamma} \right) n \leq
\alpha \sigma (1-\gamma),
$

すなわち

$\displaystyle \alpha\leq 2^{3/2} \frac{\sigma}{n} \gamma \frac{1-\gamma}{1+\gamma}$ (111)

が得られる.

$ \mu $が零に漸近すること: $ \alpha$は最大化問題

$\displaystyle \max \{ \alpha: (\vec{\xi}_{\alpha},\vec{s}_{\alpha}) \in {\cal N}_{-\infty}(\gamma,\mu), 0 \leq \alpha \leq 1 \}$ (112)

の解であり, (111)を満たす$ \alpha$は(112)の制約条件を満たすから,

$\displaystyle \alpha \geq 2^{3/2} \frac{\sigma}{n} \gamma \frac{1-\gamma}{1+\gamma}$ (113)

としてよい. (113)を(105)に代入すると,

$\displaystyle \mu_{\alpha} \leq \left ( 1- 2^{3/2}\frac{(1-\sigma)\sigma}{n} \gamma \frac{1-\gamma}{1+\gamma} \right ) \mu$ (114)

が得られる. ところで, 関数 $ h(\sigma)=\sigma(1-\sigma)$ は上に凸だから, 区間 $ [\sigma_{\min},\sigma_{\max}]$における $ h$の最小値$ y_{\min}$

$\displaystyle h_{\min}=\min \left \{\sigma_{\min}(1-\sigma_{\min}), \sigma_{\max}(1-\sigma_{\max}) \right \}
$

により定まる. また, $ h_{\min} > 0$である. したがって,

$\displaystyle \delta = 2^{3/2}h_{\min} \gamma \frac{1-\gamma}{1+\gamma}
$

とおくと, $ \delta > 0$であり,

$\displaystyle \mu_{\alpha} \leq \left ( 1-\frac{\delta}{n} \right )\mu$ (115)

$ \mu_{\alpha} > 0$, $ \mu>0$であり, (115)は各ステップで成り立つから, $ \mu $の初期値を$ \mu(0)$, $ k$回目の繰り返し計算における$ \mu $の値を$ \mu(k)$とすると,

$\displaystyle \mu(k) \leq (1-\delta/n)^k \mu(0)$ (116)

となる. したがって$ \mu $は零に漸近する. また, (116)より, 収束の速さが指数関数で押さえられることがわかる. ///

例 3620の問題の $ {\cal N}_2(\theta,\mu)$近傍と $ {\cal N}_{-\infty}(\gamma,\mu)$を求めておこう. $ \mu =\vec{s}^T\vec{\xi}/2= \xi_1/2$であることに注意する.

まず, $ (\vec{\xi},\vec{s}) \in {\cal N}_2(\theta,\mu)$かつ $ \vec{s}^T\vec{\xi}/2=\mu$を満たす点を求めよう. であれば, $ \xi_1= 2 \mu$であり, かつ

$\displaystyle \left \Vert
\begin{bmatrix}
\xi_1(1-\xi_2)-\mu\\
\xi_1\xi_2-\...
...u \xi_2-\mu
\end{bmatrix} \right \Vert
=
\sqrt{2}\mu \vert 2 \xi_2-1\vert
$

だから, $ \Vert\vec{s}\vec{\xi} -\mu \vec{1}\Vert \leq \theta \mu$なる条件は,

$\displaystyle -\theta/\sqrt{2} \leq 2 \xi_2 -1 \leq \theta/\sqrt{2}
$

と等価である. ここから, $ (\vec{\xi},\vec{s}) \in {\cal N}_2(\theta,\mu)$かつ $ \vec{s}^T\vec{\xi}/2=\mu$であれば, $ \vec{\xi}$

$\displaystyle \xi_1 = 2 \mu,   \frac{1}{2}(1-\theta/\sqrt{2}) \leq \xi_2 \leq \frac{1}{2}(1+\theta/\sqrt{2})$ (117)

なる範囲に含まれることがわかる.

次に, $ (\vec{\xi}, \vec{s}) \in {\cal N}_{-\infty}(\gamma,\mu)$かつ $ \vec{s}^T\vec{\xi}/2=\mu$を満たす点を求めよう. 先と同様に, $ \vec{s}^T\vec{\xi}/2=\mu$より, $ \xi_1= 2 \mu$である. また, $ \xi_1(1-\xi_2)=2 \mu (1-\xi_2) \geq \gamma \mu$ から $ \xi_2 \leq 1-\gamma/2$が導かれ, さらに $ \xi_1 \xi_2 = 2 \mu \xi_2 \geq \gamma \mu$より $ \xi_2 \geq \gamma/2$が導かれる. よって, $ (\vec{\xi}, \vec{s}) \in {\cal N}_{-\infty}(\theta,\mu)$かつ $ \vec{s}^T\vec{\xi}/2=\mu$であれば, $ \vec{\xi}$

$\displaystyle \xi_1=2 \mu,   \gamma/2 \leq \xi_2 \leq 1-\gamma/2$ (118)

なる範囲に含まれることがわかる.

6に, $ \theta=0.4$, $ \gamma=0.6$としたときの 各$ \mu $に対する $ {\cal N}_{2}(0.4,\mu)$, $ {\cal N}_{-\infty}(0.6,\mu)$と 集合 $ \{ (\vec{\xi},\vec{s}): \vec{s}^T\vec{\xi}/2=\mu \}$の交わりを示す. これらはいずれも中心パスを含む右に開いた矩形領域であり, $ {\cal N}_{2}(0.4,\mu) \subset {\cal N}_{-\infty}(0.6,\mu)$である.

注意すべきことは, $ \mu $が零に漸近しても, この領域の$ \xi_2$方向の 幅が狭まらないことである. ショートステップパス追跡法や ロングステップパス追跡法によって保証されるのは, これらのアルゴリズムが生成した$ \vec{\xi}$の列 $ (\vec{\xi}(k))_{k \in \mathbb{N}}$がこの領域内に あることと, $ \mu $が単調に減少することだけである. 点列 $ (\vec{\xi}(k))_{k \in \mathbb{N}}$は解析的中心に収束するわけではないし, そもそも収束するかどうかも明らかでない. ただし, この点列が集積点として強相補解を持つことは保証される.

図 6: $ {\cal N}_2$近傍と $ {\cal N}_{-\infty }$近傍
\includegraphics[scale=1]{nbh.eps}


next up previous
: 数値解に含まれる誤差の評価 : 歪対称問題の数値解法 : ショートステップパス追跡法
Shigeru HANBA 平成25年12月22日