内点法の探索方向計算に Krylov 空間 の反復解法を利用した論文

Optimization Online のサマリーをチェックしていたところ、内点法の探索方向計算に Krylov 空間の反復解法を利用した論文が出てきていた。

Implementation of Interior-point Methods for LP based on Krylov Subspace Iterative Solvers with Inner-iteration Preconditioning
http://www.optimization-online.org/DB_HTML/2016/04/5421.html

基本的には、「数値計算分野でできた解法を内点法計算に組み込んだ」というあたりがメインのアイデアになっている。

面白いのは、条件数が悪くても解ける、というところ。内点法だと反復が進むと条件数が著しく悪くなるが、この手法だと 10^80 といった条件数でも計算ができている。

また、SDPT3 などとも比較をしている。

もう少し詳しく知りたいところとしては、

• AA^T の構造をどれだけ上手く活用して反復計算をしているか？（たとえば、AA^T = M-N の分解にどう利用できているのだろう？これが分かると、もっとうまい活用法がわかる？）
• 数値実験で SDPT3 などを呼ぶ際に CVX を用いているが、これのオーバーヘッドはどれくらいだろう？SDPの場合は、CVX での変換が効率的でない場合があって、CVX で変換した場合と手動で SeDuMi フォーマットに変換した場合では10倍以上の計算時間の差があったりする。ただ、LP の場合は、それほどの大きな差は出てこないことも考えられるので、このあたりを把握できると CVX がどういうときに使い勝手がいいのか、など把握できそう。

といったあたり。