本発表では、情報幾何に基づいた主内点法(双対内点法)と主双対内点法の計算量の評価と関係式を、線形計画問題（LP）と半正定値計画問題（SDP）について示す。我々は、情報幾何の概念を用いて、近傍の大きさを無限小としたときの評価を行い、これらのアルゴリズムの計算複雑度についてピタゴラスの関係が成立することを示した。本研究は近傍の大きさについての漸近的な解析であるが、netlibの問題のついての数値実験から実用的に十分大きな近傍についても関係式が成立することを示した。

[1] R. D. C. Monteiro and T. Tsuchiya. A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms. Math. Program., 115(1, Ser. A):105-149, 2008.
[2] A. Ohara, 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, December 2007.