本発表では，悪条件な半正定値計画問題(SDP)のロバストな解法について議論する。 SDPでは、対応する相補性問題の非線形部分を緩和して得られる問題の解集合が成す中心曲線に沿って、緩和条件が0に近くなる方向に逐次進み、最適解を求める。
このアルゴリズムは主双対内点法と呼ばれ、SDPのサブセットである線形計画問題(LP)ではロバストな数値解法が確立されているが、SDPでは数値的に解くことの困難な問題が多く存在する。
SDP が数値的に困難な理由には、問題の非線形性と丸め誤差の影響が考えられるが、本発表では、LPの場合と同様に中心曲線の曲率の積分がアルゴリズムの反復回数に影響を与えると考え、NT方向とHKM方向についてその数値実験の結果を示す。さらに、今後の研究方針として、LPについて得られた計算複雑度の情報幾何的解釈のSDPへの拡張について触れる。

[1] Todd, M. J.; Toh, K. C.; Tutuncu, R. H. On the Nesterov-Todd direction in semidefinite programming. SIAM J. Optim. 8 (1998), no. 3, pp. 769-796.
[2] R. D. C. Monteiro and T. Tsuchiya: A new iteration-complexity bound for the MTY predictor-corrector algorithm. SIAM Journal on Optimization, Vol. 15 (2004), pp. 319-347.
[3] A. Ohara and T. Tsuchiya: An Information Geometric Approach to Polynomial-time Interior-point Algorithms :Complexity Bound via Curvature Integral. Research Memorandum 1055, The Institute of Statistical Mathematics, (2007).