3 探索方向

SDP問題の主双対内点法では、探索方向パラメータ $\mu$ を選び下記の条件を満たす 中心パス上の点 $(\mbox{\boldmath$X$},\mbox{\boldmath$y$},\mbox{\boldmath$Z$})$ をターゲットとし、そのNewton方向に 進む。

$$\left. \begin{array}{cll} & \mbox{\boldmath$A$}_{i} \bullet... ...{\boldmath$Z$}= \mu \mbox{\boldmath$I$}. \end{array}\right\}$$ (5)

一般に、 $\mbox{\boldmath$X$}\mbox{\boldmath$Z$}$ は対称行列でなく、 系(5)は $\mbox{${\cal S}$}^n \times \Re^m \times \mbox{${\cal S}$}^n$ か ら $\Re^m \times \mbox{${\cal S}$}^n \times \Re^{n \times n}$ への写像となるため、 直接 Newton 法を適用できない。 このため、現在までに様々な探索方向 $(\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}},\mbox{$d$\hspace{-0.11em}\mbox{\boldmath$y$}},\mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}})$ が提案されてきた。 本論文では、まず MZ 方向族[7]について述べ、 その特殊な場合として、理論的あるいは実用上有用な探索方向として知られている HRVW/KSH/M 方向[4,5,6] や NT 方向[8] あるいは AHO方向[1]について述べる。

MZ方向族[7]：

任意の正則行列 $\mbox{\boldmath$P$}\in \Re^{n \times n}$ に対し、 $\mbox{\boldmath$H$}_{p}:\Re^{n \times n} \rightarrow \mbox{${\cal S}$}^{n}$ を以下のように定義する。

$$\mbox{\boldmath$H$}_{P}(\mbox{\boldmath$A$}) = \frac{\mbox{... ...dmath$P$}\mbox{\boldmath$A$}\mbox{\boldmath$P$}^{-1})^{T}}{2}.$$

行列 $\mbox{\boldmath$P$}$ はスケーリング行列の役目をし、 $\mbox{\boldmath$H$}_{P}(\mbox{\boldmath$A$})$ は スケーリングされた行列 $\mbox{\boldmath$P$}^{-1}\mbox{\boldmath$A$}\mbox{\boldmath$P$}$ の対称化に相当する。 このとき、 $\mbox{\boldmath$H$}_{P}(\mbox{\boldmath$A$})$ は $\mbox{\boldmath$A$}$ に対する線形操作であることを注意しておく。

系 (5) の $\mbox{\boldmath$X$}\mbox{\boldmath$Z$}= \mu \mbox{\boldmath$I$}$ を $\mbox{\boldmath$H$}_{P}(\mbox{\boldmath$X$}\mbox{\boldmath$Z$}) = \mbox{\boldmath$H$}_{P}(\mu \mbox{\boldmath$I$})$ に 置き換えると以下の新しい系を得る。

$$\left. \begin{array}{ll} \mbox{\boldmath$A$}_{i} \bullet \m... ...math$H$}_{P}(\mu \mbox{\boldmath$I$}) . \end{array} \right\}$$ (6)

この系にNewton法を適用すると、探索方向 $(\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}},\mbox{$d$\hspace{-0.11em}\mbox{\boldmath$y$}},\mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}})$ は 以下の線形方程式系の解となる。

$$\left. \begin{array}{ll} \mbox{\boldmath$A$}_{i} \bullet \m... ...\boldmath$H$}_{P}(\mbox{\boldmath$R$}_c). \end{array}\right\}$$ (7)

ただし、 $[\mbox{\boldmath$r$}_p]_{i}= b_{i} - \mbox{\boldmath$A$}_{i} \bullet \mbox{\boldmath$X$}$, $\mbox{\boldmath$R$}_d = \mbox{\boldmath$A$}_0 - \sum_{i=1}^{m} \mbox{\boldmath$A$}_{i}y_{i} - \mbox{\boldmath$Z$}$, $\mbox{\boldmath$R$}_c = \mu \mbox{\boldmath$I$}- \mbox{\boldmath$X$}\mbox{\boldmath$Z$}$ である。 1つ目の等式が主問題の実行可能性、2つ目の等式が双対問題の 実行可能性、3つ目の等式が相補性に対応している。 この線形方程式系(7)は、対称化Kronecker積を使って 書き直すことができる。

$$\left. \begin{array}{ll} \mbox{\boldmath$A$}_{i} \bullet \m... ...ath$X$}^{-1} \mbox{\boldmath$R$}_c). & \\ \end{array}\right\}$$ (8)

ここで、 $\mbox{\boldmath$X$}^{-1} \mbox{\boldmath$R$}_c (= \mu \mbox{\boldmath$X$}^{-1} - \mbox{\boldmath$Z$})$ は対称行列となることに注意する。 なお、任意の行列 $\mbox{\boldmath$A$},\mbox{\boldmath$B$}\in \Re^{n \times n}$の 対称化 Kronecker 積 $\mbox{\boldmath$A$}\odot\mbox{\boldmath$B$}$は、 任意の対称行列 $\mbox{\boldmath$X$}\in \mbox{${\cal S}$}^{n}$に対し、 $(\mbox{\boldmath$A$}\odot\mbox{\boldmath$B$})\mbox{\boldmath$X$}= (\mbox{\boldm... ...ldmath$A$}^T + \mbox{\boldmath$A$}\mbox{\boldmath$X$}\mbox{\boldmath$B$}^T) / 2$を満たす 写像として定義される。 よって、対称化 Kronecker 積 $\mbox{\boldmath$A$}\odot\mbox{\boldmath$B$}$は、 $\mbox{${\cal S}$}^{n} \to \mbox{${\cal S}$}^{n}$となる写像である。 対称化Kronecker積の諸性質については[11]等を参照されたい。 この線形方程式系(8)は、 $\mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}}$と $\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}$を掃き出すことにより、 以下の次元の小さな線形方程式系に帰着させることができる。

$$\left. \begin{array}{lll} \mbox{\boldmath$B$}\mbox{$d$\hspac... ...$d$\hspace{-0.16em}\mbox{\boldmath$Z$}}). \end{array}\right\}$$ (9)

ただし、

$$\begin{array}{lll} B_{ij} & = & \mbox{\boldmath$A$}_i \bulle... ...- \mbox{\boldmath$R$}_d) ~~~~~ (i = 1,2,\ldots,m). \end{array}$$

である。 この方程式系の一般的な解法については[]を参照されたい。 以下では、正則行列 $\mbox{\boldmath$P$}$に特定の行列を代入することによって、 HRVW/KSH/M方向, NT方向, AHO方向の3つの探索方向を導くことにする。

HRVW/KSH/M 方向[4,5,6]：

これは、 MZ 方向族の $\mbox{\boldmath$P$}$ として $\mbox{\boldmath$Z$}^{1/2}$ を採る場合に相当する。 このとき、HRVW/KSH/M 方向 $(\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}},\mbox{$d$\hspace{-0.11em}\mbox{\boldmath$y$}},\mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}})$ は以下のようにして求めることができる。

$$\left. \begin{array}{llll} \mbox{\boldmath$B$}\mbox{$d$\hsp... ...{-0.21em}\mbox{\boldmath$X$}}}^T)/2.\\ \end{array} \right\}$$ (10)

ただし、

$$\begin{array}{lll} B_{ij} = \mbox{\boldmath$A$}_i \bullet \m... ...x{\boldmath$Z$}^{-1} ~~~~~ (i = 1,2,\ldots,m). \\ \end{array}$$

つまり、まず行列 $\mbox{\boldmath$B$}$ の各要素を計算し、その行列を係数行列とする 線形方程式系を解くことにより $\mbox{$d$\hspace{-0.11em}\mbox{\boldmath$y$}}$ を計算する。 その後、 $\mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}}$、 $\widehat{\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}}$、 $\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}$ を順次計算する。 この場合、線形方程式系の 係数行列 $\mbox{\boldmath$B$}$が正定値行列になっていることを付け加えておく。

NT方向[8]：

行列 $\mbox{\boldmath$W$}$ を

$$\mbox{\boldmath$W$}= \mbox{\boldmath$X$}^{1/2}(\mbox{\boldma... ...X$}\mbox{\boldmath$Z$}^{1/2})^{1/2}\mbox{\boldmath$Z$}^{-1/2},$$

と定義すると、NT方向はMZ方向族の $\mbox{\boldmath$P$}$ として $\mbox{\boldmath$W$}^{-1/2}$ を採る場合に相当する。 このとき、NT方向 $(\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}},\mbox{$d$\hspace{-0.11em}\mbox{\boldmath$y$}},\mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}})$ は以下のようにして求めることができる。

$$\left. \begin{array}{llll} \mbox{\boldmath$B$}\mbox{$d$\hsp... ...{-0.21em}\mbox{\boldmath$X$}}}^T)/2.\\ \end{array} \right\}$$ (11)

ただし、

$$\begin{array}{llll} B_{ij} = \mbox{\boldmath$A$}_i \bullet \... ...$}_d) \mbox{\boldmath$W$}~~~~~ (i = 1,2,\ldots,m). \end{array}$$

行列 $\mbox{\boldmath$W$}$ を求めた後は、NT方向の計算方法はHRVW/KSH/M方向の計算方法 と同様である。 よって、HRVW/KSH/M方向とNT方向の計算量やメモリ使用量は あまり変わらない場合が多い。 また、この係数行列 $\mbox{\boldmath$B$}$も正定値行列となっている。

AHO 方向[1]：

これは、MZ 方向族の $\mbox{\boldmath$P$}$ として $\mbox{\boldmath$I$}$ を採る場合に相当する。 このとき、AHO 方向 $(\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}},\mbox{$d$\hspace{-0.11em}\mbox{\boldmath$y$}},\mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}})$ は以下のようにして求めることができる。

$$\left. \begin{array}{llll} \mbox{\boldmath$B$}\mbox{$d$\hsp... ...d$\hspace{-0.16em}\mbox{\boldmath$Z$}}). \end{array} \right\}$$ (12)

ただし、

$$\begin{array}{lll} B_{ij} = \mbox{\boldmath$A$}_i \bullet (\... ...x{\boldmath$R$}_d) \ ~~~~~ (i = 1,2,\ldots,m). \\ \end{array}$$

HRVW/KSH/M方向やNT方向の計算と同様に、 まず行列 $\mbox{\boldmath$B$}$ の各要素を計算し、その行列を係数行列とする 線形方程式系を解くことにより $\mbox{$d$\hspace{-0.11em}\mbox{\boldmath$y$}}$ を計算する。 その後、 $\mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}}$、 $\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}$ を順次計算する。 しかし、係数行列の各要素の計算あるいは $\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}$の計算の中に $(\mbox{\boldmath$Z$}\odot \mbox{\boldmath$I$})^{-1}$ の項がある。 このため、Lyapunov方程式 を解く必要があるが、 この方程式を解くことは計算量の点でそれほど容易ではない。 よって、実用的な計算にはAHO方向は余り利用されない。 なおAHO方向の場合、線形方程式系の係数行列 $\mbox{\boldmath$B$}$は 対称行列とならないことに注意する。