next up previous
: おわりに : 歪対称問題の数値解法 : ロングステップパス追跡法


数値解に含まれる誤差の評価

ここまでの議論で, ショートステップパス追跡法とロングステップパス追跡法において, $ \mu \rightarrow 0$となることは示された. では, $ \mu $が十分小さくなり, 計算が終了したとき, 数値解から計算される主問題と双対問題の解は正確だろうか?

まず最初に注意すべきことは, $ \mu $が零に収束したときに得られる解は 強相補解ではあるが, 解析的中心とは限らないということである. さらに, ショートステップパス追跡法やロングステップパス追跡法 を適用することで得られる解の系列を点列とみたとき, これは強相補解を集積点として持つが, この点列自体は 収束するとは限らないということも要注意である.

主問題と双対問題の解を再構成するために必要なのは 強相補解であって, 解析的中心ではなかった. だから, 上述の点列が解析的中心に収束するとは限らないこと 自体は大きな問題ではない. ただし, 有限回の繰り返し計算の後に 計算を終了したときには, $ \mu $は十分小さくなっていても 零ではないから, 対応する数値解から計算される主問題と双対問題 の解が正しいか否かは問題になりうる.

このようにして計算される解は一定の誤差の範囲で 主問題と双対問題の解に一致することが示せるのだが, この証明は若干繁雑である. 以下でこれついて述べる.

ショートステップパス追跡法とロングステップパス追跡法を 統一的に取り扱うため, まず $ {\cal N}_{2}(\theta,\mu) \subset {\cal N}_{-\infty}(1-\theta,\mu)$ であることに注意する. そこで, $ \vec{s}, \vec{\xi}$ $ \vec{s}^T \vec{\xi}/n = \mu$, $ (\vec{\xi}, \vec{s}) \in {\cal N}_{-\infty}(\gamma,\mu)$を満たし, $ \mu $が十分小さいとき, $ (\vec{\xi},\vec{s})$との距離が$ \mu $のオーダーで押さえられるような 強相補解が存在すれば, 数値解は$ \mu $に対応した誤差の範囲内で正確である ということになる.

以下の議論では, まず上述の条件を満たす強相補解の存在を示した上で, 厳密な最適解と数値的に求められた数値解との誤差を評価する.

さて, 計算終了時の解 $ (\vec{\xi},\vec{s})$に十分小さい強相補解が存在するなら, $ \vec{\xi}$$ \vec{s}$の各成分は零に近いものと一定以上の正の値を取るものに 分かれているはずである. 次の補題で, 実際に上述のようになることを示す.

補題 37 歪対称問題(SP)の $ (\vec{\xi}, \vec{s}) \in {\cal N}_{-\infty}(\gamma,\mu)$, $ \mu=\vec{\xi}^T\vec{s}/n$なる数値解が得られているものとする. また, この問題の解析的中心を $ (\vec{\xi}_{\sharp},\vec{s}_{\sharp})$とし, $ B=\{i: \xi_{\sharp,i} \neq 0\}$, $ N=\{i: s_{\sharp, i} \neq 0\}$とする. このとき, ある正の定数$ K$が存在して, $ i \in B$なら $ \xi_i \geq \gamma/K$かつ $ s_i \leq K \mu$, $ i \in N$なら $ \xi_i \leq K \mu$かつ $ s_i \geq \gamma/K$ となる.

[証明] $ (\vec{\xi}_{\sharp}-\vec{\xi})^T(\vec{s}_{\sharp}-\vec{s})=0$より, $ \vec{\xi}^{T}\vec{s}_{\sharp}+\vec{s}^T\vec{\xi}_{\sharp}=n \mu$である. そこで,

$\displaystyle \frac{1}{K}=\frac{1}{n}\min \left \{ \min\{ \xi_{\sharp,i}:i \in B \}, \min \{s_{\sharp,i}: i \in N\} \right \}
$

とおくと, $ i \in B$のとき, $ \xi_{\sharp,i} s_i \leq \vec{\xi}^{T}\vec{s}_{\sharp}+\vec{s}^T\vec{\xi}_{\sharp}=n \mu $ であり, $ \xi_{\sharp,i} \geq n/K$だから, $ s_i \leq K \mu$となる. また, $ \xi_i s_i \geq \gamma \mu$だったから, $ \xi_i \geq \gamma/K$となる. 同様に, $ i \in N$のとき, $ s_{\sharp,i} \xi_i \leq n \mu$より $ \xi_i \leq K \mu$ であり, $ \xi_i s_i \geq \gamma \mu$から $ s_i \geq \gamma/K$となる. ///

注意 38 解析的中心は歪対称問題を定める行列$ \vec{M}$とベクトル$ \vec{q}$から 一意的に決まる. また, 補題37の定数$ K$は解析的中心から決まる. このため, 定数$ K$は数値解法のアルゴリズムや数値解の値には依存しない.

定理 39 ショートステップパス追跡法あるいはロングステップパス追跡法によって $ \vec{\xi}^T\vec{s}/n = \mu$なる数値解が得られ, $ \mu $が十分小さいとき, ある正の定数$ C$に対し, 歪対称問題のある強相補解 $ (\vec{\zeta},\vec{s}(\zeta))$ が存在し, $ \Vert\vec{\xi}-\vec{\zeta}\Vert \leq C \mu$となる.

[証明] 補題37と同様に, $ (\vec{\xi}_{\sharp},\vec{s}_{\sharp})$を解析的中心とし, $ B=\{i: \xi_{\sharp,i} \neq 0\}$, $ N=\{i: s_{\sharp, i} \neq 0\}$とする. また, $ \vec{\xi}$$ \vec{s}$から$ B$$ N$に対応する添字を抜き出して 作った部分ベクトルをそれぞれ $ \vec{\xi}_{B}$, $ \vec{\xi}_{N}$ $ \vec{s}_{B}$, $ \vec{s}_{N}$ とする. 添字の順番を適当に入れ換えることで,

$\displaystyle \vec{\xi}=[\vec{\xi}_{B}^T,\vec{\xi}_{N}^T]^T, \quad \vec{s}=[\vec{s}_{B}^T,\vec{s}_{N}^T]^T$ (119)

と書ける. さらに, $ \vec{\xi}$$ \vec{s}$の関係式 $ \vec{s}=\vec{M}\vec{\xi}+\vec{q}$を, この添字の並べ換えに対応して,

$\displaystyle \begin{bmatrix}\vec{s}_{B}\ \vec{s}_{N} \end{bmatrix} = \begin{b...
...vec{\xi}_{N} \end{bmatrix} + \begin{bmatrix}\vec{q}_1\ \vec{q}_2 \end{bmatrix}$ (120)

と書き直しておく. 記号が繁雑になるのを避けるため, 補題37の定数$ K$に 対し, $ \varepsilon = K \mu$とおく. このとき, 補題37より, ベクトル $ \vec{s}_{B}$の各成分は $ \varepsilon$以下だったから,

$\displaystyle \vec{q}_3=(1/\varepsilon ) \vec{s}_{B}$ (121)

とおくと, ベクトル$ \vec{q}_3$の各成分の値は1以下になる. 同様に,

$\displaystyle \vec{q}_4=(1/\varepsilon ) \vec{\xi}_{N}$ (122)

とおくと, ベクトル$ \vec{q}_4$の各成分の値は1以下になる. これらを使って(120)の第1式を書き直すと,

$\displaystyle \varepsilon \vec{q}_3 = \vec{M}_1 \vec{\xi}_{B} +\varepsilon \vec{M}_2 \vec{q}_4 +\vec{q}_1$ (123)

となる. (123)を $ \varepsilon$による項とよらない項に分けると,

$\displaystyle \varepsilon \left ( \vec{q}_3 -\vec{M}_2 \vec{q}_4 \right )= \vec{M}_1 \vec{\xi}_{B} +\vec{q}_1$ (124)

が得られる.

以下の議論では, 基底の取り方に依存した繁雑な議論を避けるため, 行列$ \vec{M}_1$とこの行列から定まる線形写像を同一視する. さて, 十分小さい $ \varepsilon$に対して (124)が成り立つためには, ベクトル $ \vec{q}_{1}$$ \vec{M}_1$の像空間に含まれる必要がある. これはなぜかというと, ベクトル$ \vec{q}_1$$ \vec{M}_1$の像空間 $ {\rm Im} \vec{M}_1$ とその直交補空間 $ ({\rm Im} \vec{M}_1)^{\bot}$に対応して $ \vec{q}_1=\vec{q}_{11}+\vec{q}_{12}$, $ \vec{q}_{11} \in {\rm Im} \vec{M}_1$, $ \vec{q}_{12} \in ({\rm Im} \vec{M}_1)^{\bot}$と直和分割したとき, $ \Vert\vec{q}_{12}\Vert \neq \vec{0}$であれば, (124)の左辺のベクトルのノルムは $ \Vert\vec{q}_{12}\Vert$以下にはならないのに対し, (124)の右辺のベクトルのノルムは $ \varepsilon$を小さくすればいくらでも小さくなるからである. ゆえに $ \Vert\vec{q}_{12}\Vert = \vec{0}$, したがって $ \vec{q}_{12}=\vec{0}$であり, それゆえ $ \vec{q}_1 \in {\rm Im} \vec{M}_1$である. 次に, $ \vec{\xi}_B$ $ ({\rm Ker}M_{1})^{\bot}$ $ {\rm Ker}M_{1}$に直和分割し,

$\displaystyle \vec{\xi}_{B}= \vec{\xi}_{B1}+\vec{\xi}_{B2},   \vec{\xi}_{B1} \in ({\rm Ker}M_{1})^{\bot},   \vec{\xi}_{B2} \in {\rm Ker}M_{1}$ (125)

と書く. このとき, $ \vec{M}_1 \vec{\xi}_B = \vec{M}_1 \vec{\xi}_{B1}$である. 一方, $ M_{1}$の定義域を $ ({\rm Ker}M_{1})^{\bot}$, 値域を $ {\rm Im} \vec{M}_1$に制限した写像は正則だから, ある $ \vec{\zeta}_{B1} \in ({\rm Ker}M_{1})^{\bot}$が取れて, $ -\vec{q}_1=\vec{M}_{1} \vec{\zeta}_{B1}$となる. さて, ここで,

$\displaystyle \zeta_{B}=\vec{\zeta}_{B1}+\vec{\xi}_{B2}$ (126)

とおき,

$\displaystyle \vec{\zeta}=[\vec{\zeta}_{B}^T,\vec{0}^T]$ (127)

とする. (126), (127)および(122)より,

\begin{displaymath}\begin{split}\vec{\xi}-\vec{\zeta} = \begin{bmatrix}\vec{\xi}...
...c{\zeta}_{B1}\ \varepsilon \vec{q}_4 \end{bmatrix} \end{split}\end{displaymath} (128)

となることに注意しよう.

以下では, $ \varepsilon$が十分小さいとき, (127)がひとつの強相補解を定め, かつ $ \Vert\vec{\xi}-\vec{\zeta}\Vert$ $ \varepsilon$のオーダーで 押さえられることを示す.

まず最初に, $ \vec{\zeta}$の定義より,

$\displaystyle \begin{bmatrix}\vec{M}_1&\vec{M}_2\ \vec{M}_3&\vec{M}_4 \end{bma...
...bmatrix} = \begin{bmatrix}0\ \vec{M}_3 \vec{\zeta}_{B}+\vec{q}_2 \end{bmatrix}$ (129)

である. (123)の左辺および右辺から (129)の第1式の左辺および右辺を減じ, (121), (125)および(126)を使うと,

$\displaystyle \varepsilon \vec{q}_3 = \vec{M}_1 (\vec{\xi}_{B1}-\vec{\zeta}_{B1}) +\varepsilon \vec{M}_2 \vec{q}_4$ (130)

となる. (130)を $ \varepsilon$に依存する項と そうでない項に分けて整理すると,

$\displaystyle \varepsilon \left ( \vec{q}_3 - \vec{M}_2 \vec{q}_4 \right ) = \vec{M}_1 (\vec{\xi}_{B1}-\vec{\zeta}_{B1})$ (131)

となる. ここで, $ \vec{q}_3$$ \vec{q}_4$の各要素の値は1以下である ことに注意しよう. さらに, $ \vec{\xi}_{B1}-\vec{\zeta}_{B1} \in ({\rm Ker}M_{1})^{\bot}$であり, $ \vec{M}_1$ $ ({\rm Ker}M_{1})^{\bot}$から $ ({\rm Im} \vec{M}_1)$への写像とみなすと この写像は正則であったから, ある正の定数 $ \sigma_{\min}$が取れて,

$\displaystyle \sigma_{\min} \Vert\vec{\xi}_{B1}-\vec{\zeta}_{B1}\Vert \leq \Vert\vec{M}_1 (\vec{\xi}_{B1}-\vec{\zeta}_{B1})\Vert$ (132)

が満たされる. そこで, (131)の両辺のノルムを 取ってから(132)を代入し, 両辺を $ \sigma_{\min}$で割り, さらに

$\displaystyle L=\Vert\vec{q}_3 - \vec{M}_2 \vec{q}_4\Vert$ (133)

とおくと,

$\displaystyle \Vert\vec{\xi}_{B1}-\vec{\zeta}_{B1}\Vert =\Vert\vec{\xi}_{B}-\vec{\zeta}_{B}\Vert \leq \frac{L}{\sigma_{\min}}\varepsilon$ (134)

となる. したがって, $ \Vert\vec{q}_4\Vert \leq \sqrt{n}$に注意すると, (128)より,

$\displaystyle \Vert\vec{\xi}-\vec{\zeta}\Vert \leq \left ( \frac{L}{\sigma_{\min}}+ \sqrt{n} \right )\varepsilon$ (135)

となる.

では, 以上のようにして定められた $ \vec{\zeta}$に対し, $ \vec{s}(\zeta)=\vec{M}\vec{\zeta}+\vec{q}$とすると, $ \varepsilon$(したがって$ \mu $)が十分小さければ, $ (\vec{\zeta},\vec{s}(\vec{\zeta}))$は強相補解になることを確認しよう. 補題37より $ \vec{\xi}_{B}$の各成分は$ \gamma/K$以上だったから, (135)より, このとき $ \vec{\zeta}_{B}$の各成分が零とならないことは明らかである. よって, $ \vec{s}(\zeta)$の添字$ N$に対応する成分が零でないこと が示されれば, $ (\vec{\zeta},\vec{s}(\vec{\zeta}))$が強相補解であることが確認できたことになる. これを見るために, (119)と同様の添字の並べかえにより, $ \vec{s}(\vec{\zeta})=[\vec{s}_{B}^T(\vec{\zeta}),\vec{s}_{N}^T(\vec{\zeta})]^T$ と書くと,

\begin{displaymath}
\begin{split}
\vec{s}_{N}(\vec{\zeta})
&=\vec{M}_3 \vec{\zet...
... (\vec{\zeta}_B-\vec{\xi}_B) - \vec{M}_4\vec{\xi}_N
\end{split}\end{displaymath}

より,

$\displaystyle \vec{s}_{N}(\vec{\zeta})-\vec{s}_N = \vec{M}_3 (\vec{\zeta}_B-\vec{\xi}_B) - \vec{M}_4\vec{\xi}_N$ (136)

が得られる. ここで(122)(134)を使うと,

$\displaystyle \Vert\vec{s}_{N}(\vec{\zeta})-\vec{s}_N\Vert \leq \left ( \Vert\v...
...ert \frac{L}{\sigma_{\min}} + \Vert\vec{M}_4 \Vert\sqrt{n} \right ) \varepsilon$ (137)

となる. すなわち, $ \vec{s}_{N}(\vec{\zeta})$の各成分の対応する$ \vec{s}_N$からの偏差は $ \varepsilon$で押さえられる. 一方, ふたたび補題37より, $ \vec{s}_N$の各成分は$ \gamma/K$以上だったから, $ \varepsilon$(したがって$ \mu $)が十分小さければ $ \vec{s}_{N}(\vec{\zeta})$の各成分は零より大きくなる.

以上によって, $ (\vec{\zeta},\vec{s}(\vec{\zeta}))$が強相補解であることが示された. また, (135)より, $ C=( L/\sigma_{\min}+ \sqrt{n} )K$とおくと,

$\displaystyle \Vert\vec{\xi}-\vec{\zeta}\Vert \leq C \mu$ (138)

となる. ///

定理39より, $ \mu $が十分小さくなるまで計算を続けていれば, もとの問題の最適解と数値解との誤差は$ \mu $のオーダーで押さえられることがわかる.


next up previous
: おわりに : 歪対称問題の数値解法 : ロングステップパス追跡法
Shigeru HANBA 平成25年12月22日