4 ステップサイズ

主双対内点法を多項式時間内で収束させるには、 中心パス$\mathcal{P}$の何らかの意味での近傍内を探索する必要がある。 しかし、経験上、 $\mbox{\boldmath$X$}$や $\mbox{\boldmath$Z$}$が正定値であるという条件さえ守れば、 主双対内点法は最適解に収束することが分かっている。 そのため、以下のようにしてステップサイズを定めると実用的である。

まず、 $(\mbox{\boldmath$X$},\mbox{\boldmath$y$},\mbox{\boldmath$Z$}) + \alpha (\mbox{$... ...h$Z$}}) \in \mbox{${\cal S}$}^n_{+}\times \Re^m \times \mbox{${\cal S}$}^n_{+}$ を満たすような最大のステップサイズ$\alpha$を計算する。 すなわち、その値を$\alpha_{\max}$とすると、

$$\alpha_{\max} = \max \left\{ \alpha \ge 0 ~\vert~ (\mbox{\... ...S}$}^n_{+}\times \Re^m \times \mbox{${\cal S}$}^n_{+} \right\}$$

である。 $\alpha_{\max}$の値を得るためには、 $\mbox{\boldmath$X$}$の部分と $\mbox{\boldmath$Z$}$の部分に分けて考えるとよい。 今、 $\mbox{\boldmath$X$}+ \alpha \mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}$が半正定値領域に留まるような最大の$\alpha$ （$\alpha_{p}$と呼ぶ）について考えよう。 以下では、 $\lambda_{\min}(\mbox{\boldmath$A$})$ を行列 $\mbox{\boldmath$A$}$の最小固有値の 意味で使う。すると、

$$\begin{array}{l} \mbox{\boldmath$X$}+ \alpha \mbox{$d$\hspac... ...\boldmath$X$}}\mbox{\boldmath$X$}^{-1/2}) \ge 0 \\ \end{array}$$

が成り立つので、求めたい$\alpha_{p}$は

$$\alpha_{p} = \left\{ \begin{array}{ll} \displaystyle \frac{... ...th$X$}^{-1/2}) \ge 0 \mathrm{の場合}~ ) \\ \end{array}\right.$$

となる。 同様のことは、双対問題の変数 $\mbox{\boldmath$Z$}$についても成り立ち、 $\mbox{\boldmath$Z$}+ \alpha \mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}}$が半正定値領域に留まる最大の$\alpha_{d}$は、

$$\alpha_{d} = \left\{ \begin{array}{ll} \displaystyle \frac{... ...th$Z$}^{-1/2}) \ge 0 \mathrm{の場合}~ ) \\ \end{array}\right.$$

で求められる。このとき、$\alpha_{\max}$が

$$\alpha_{\max} = \min\{ \alpha_{p},~ \alpha_{d} \}$$

となるのは明らかであろう。 主双対内点法のステップサイズ$\alpha$は、 $\alpha_{\max}$の$0.9$倍程度に設定するとよい。 ただし、ステップサイズを余り大きく取り過ぎると、 主双対内点法の収束に支障をきたす場合がある。 そのため、$1$以上ならば強制的に$1$にしておく必要がある。 すなわち、

$$\alpha = \min \{~ 1,~ 0.9 \alpha_{\max} ~\}$$

で、計算されるステップサイズ$\alpha$を採用すれば良い。