なぜ主双対内点法の反復回数は２０回程度なのか

主双対内点法の反復回数は、理論的にはO(sqrt(n) log (eplison)) となっている。
ところが、n >= 10000 で epsilon = 10^{-8} でも、SDPA などのソフトウェアの場合、たいていは 20 回程度、多くても 50 回程度で終わる。

なぜか。

理由は簡単で、理論的な解析が効く前に閾値に到達してしまうことにある。


たとえば、ステップ長がすべての反復で 0.5 以上できたとすると、一回の反復で実行可能性は２分の１以下になる。
そこで、(1/2)^k = 10^{-8} を k について解くと、閾値 10^{-8}を実行可能性が下回るまでの反復回数が分かるが、これが 26.5754 回なのである。

反復ではロングステップとショートステップがあって、ショートステップの方が理論的には少ない反復数であるとされているのに、実際に計算するとロングステップの方が速いのも、閾値からの影響が大きい。


コンピュータソフトウェアの場合、double など有限桁数で計算しているため、無限桁数で仮想している理論的な解析で高速なものが実際の計算でも高速とは限らない。



今日の作業内容：証明の続き 2h
今日のランチ：らく 焼き魚定食
明日の予測作業時間：4h