Chubanov の方法を凸結合したら面白そうね、って話

この前の RAMP で線形計画問題などを含む Chubanov の方法についての話があって、とても勉強になった。Chubanov の方法が流行っている、というのは既に聞いていたが、自分では勉強していなかったので、いい機会でもあった。

個人的な印象としては、
「漠然と想像していたよりも内点法に似通っている」
というところ。
基本的には、錐の中心へとスケーリングする、という計算方法がKarmarkar の内点法に近い印象になっているのではないかと思う。

対称錐の場合、homogeneous の性質が効くため、錐の中心とすべての実行可能内点は同じとみなすことができるので、Karmarkar の内点法で生成される内点の点列以外にも内点の点列が作れる、ということである。

単純に考えると、Karmarkar の内点法の生成する点列と Chubanov の内点法の生成する点列で凸結合を取れば、それら２つの方法を統合した計算手法が作れるんだろうなぁ、って思う。
そうすると、最初の反復では計算効率の良い Karmarkar 法を使って、解の近くに近づいたら Chubanov 法に切り替えて固有値計算をうまくやる、とかできるかとは思う。