An interior-point method (IPM) is a convex programming method which widely attracts many areas of research and development. This is because it exhibits theoretical certificates of polynomial complexities, wider class of applications, and superior computational capabilities in real world situations. In its early stage of development, it has been only concerned with linear programming (LP), but later it has been extended to larger class of problems such as semidefinite programming (SDP), second-order cone programming (SOCP), symmetric cone programs, etc. Simultaneously, a various types of algorithms has been developed; they are roughly classified based on the following three independent criteria: i) primal/dual algorithms or primal-dual algorithms, ii)path-following methods, potential reduction methods, or affine-scaling methods, iii) feasible methods or infeasible methods. On top of these subjects, complexity analysis has always been a central theme in IPMs, in fact polynomial complexity and its improvement are always in debate.

In this thesis, we first discuss iteration complexities of Mizuno-Todd-Ye predictor-corrector (MTY-PC) algorithm in view of the "curvature" of the central path, a well-defined trajectory in the feasible solutions, in case of SDP and symmetric cone programs. MTY-PC algorithm is a path-following primal-dual algorithm which traces the central path inside its neighborhood toward Newton direction at a predictor step and toward a central direction at a corrector step in alternative shift to reach an optimum solution. The derivation of iteration complexities is based on the intuitive idea that path-following algorithms trace the straight parts of the central path faster than remaining curved parts. Our analysis is an asymptotic one with letting the opening of the neighborhood zero.

Second, we discuss the relationship of iteration complexities between path-following primal/dual algorithms and MTY-PC algorithm in view of information geometric framework recently developed by Ohara and Tsuchiya. Primal/dual algorithms are a general framework, established by Nesterov and Nemirovski, to deal with a conic linear programs including SDP and symmetric cone programs, and solve problems only in primal or dual feasible regions. Using information geometric framework, we can consider both a primal problem and a dual problem in the same space through Legendre transformation, Under this setting, we prove the Pythagorean relationships between them in case of SDP and symmetric cone programs based on the fact that a certain projection of the "curvature" of MTY-PC algorithm is the one of a primal algorithm and its orthogonal projection is the one of dual algorithm.

Lastly, we conduct reasonably large-scale numerical experiments in LP and SDP, so as to investigate the validity of the analyses of iteration complexities in MTY-PC algorithms for real problems. In spite of an asymptotic treatment of analysis by nature, numerical experiments strongly suggest our claim hold for practically large opening of the neighborhood.

最適化の分野では、近年、凸2次計画問題、半正定値計画問題、対称錐計画問題等の新しいクラスの凸最適化問題が、内点法によって実用的レベルで解けることが明らかとなり、様々な分野において重要な道具立てとなりつつある。一方、情報幾何学は、1980年代に統計学に始まり、機械学習、信号処理など情報数理の諸分野を横断的に捉える統一的な枠組みとして注目されてきた。本論文は、半正定値計画問題や対称錐計画問題に対して、その主要な解法である曲線追跡型主双対内点法の計算複雑度を中心曲線とよばれる曲線上の積分によって表現し、その表現と問題の情報幾何学的構造との関係を明らかにし、さらには、この表現の有効性を大規模数値実験により示したものである。

本論文は「Computational Complexities of Interior-Point Methods in Symmetric Cone Programs and Their Information Geometric Analyses (対称錐計画問題に対する内点法の計算複雑度と情報幾何学的解析)」と題し全9章からなる。第5章、第7章、第8章が論文提出者独自の貢献である。

第1章「Introduction」(序論)では、現代凸最適化と主双対内点法、そして情報幾何学を概観し、本論文の内容の要約を与えている。

第2章「Conic Linear Programs」(錐線形計画問題)では、錐線形計画問題の定義が与えられ、線形計画問題、半正定値計画問題、対称錐計画問題がその特殊例となることが紹介されている。さらに双対定理についても述べられている。

第3章「Euclid Jordan Algebra and Symmetric Cones」(ユークリッド的ジョルダン代数と対称錐)では、対称錐とその代数的表現であるユークリッド的ジョルダン代数が紹介されている。ユークリッド的ジョルダン代数は、対称錐計画問題に対する主双対内点法の理論を展開する上で不可欠なものである。

第4章「Interior-Point Algorithms」(内点法)では、凸最適化問題に対する曲線追跡型内点法の一般理論である自己整合的障壁関数の理論、そして線形計画問題、半正定値計画問題、対称錐計画問題に対する主要な解法である曲線追跡型主双対内点法が紹介される。これらの内点法は、中心曲線と呼ばれる実行可能領域の内部を通る曲線を近似的に追跡して最適解を求めるものであり、多項式時間アルゴリズムであることが知られている。

第5章「Curvature Integrals and Iteration Complexities in Semidefinite Programming and Symmetric Cone Programs」(半正定値計画問題と対称錐計画問題における曲率積分と反復回数)においては、半正定値計画問題や対称錐計画問題に対する曲線追跡型主双対内点法の反復回数が中心曲線上の曲率を積分した量によって漸近的に表現できることを示している。

第6章「Information Geometric Framework of Interior-Point Algorithms」(内点法の情報幾何学的枠組み)では、内点法の情報幾何学的枠組みが紹介される。曲線追跡型主内点法、曲線追跡型双対内点法の反復回数は、それぞれに対応する中心曲線上の埋め込み曲率に関する情報幾何学的積分によって表現される。

第7章「Curvature Integrals and Pythagorean Relationships」(曲率積分とピタゴラス関係)では、第5章で得られた中心曲線上の曲率を第6章で導入された埋め込み曲率を用いて表現し、半正定値計画問題、対称錐計画問題に対する曲線追跡型主双対内点法の反復回数が情報幾何学的な量を用いて表現できることが示されている。(主双対内点法に対する中心曲線上の曲率の2乗)=(主内点法に対する中心曲線上の埋め込み曲率の2乗)+(双対内点法に対する中心曲線上の埋め込み曲率の2乗)という非常に興味深いピタゴラス関係が成立することが示され、この関係を用いて上記の事実が証明されている。

第8章「Numerical Experiments in Linear Programming and Semidefinite Programming」(線形計画問題と半正定値計画問題に関する数値実験)では、線形計画問題、半正定値計画問題の標準的問題集(NETLIB, SDPLIB) から規模の大きな問題を選び、曲線追跡型主双対内点法の実際の反復回数と曲率積分に基づく評価を調べ、両者が非常によく一致することを示している。

第9章「Conclusions」(結論)では本論文で得られた結果を総括している。

以上を要するに、本論文は、凸最適化問題の重要なクラスである半正定値計画問題と対称錐計画問題に対して、その主要な解法である曲線追跡型主双対内点法の反復回数を中心曲線上の曲率積分を用いて評価し、さらに曲率積分が情報幾何学的量として表現できることを示し、大規模問題についての数値計算によりその評価が極めて有効であることを示したものである。最適化アルゴリズムの計算複雑度と情報幾何学という離れた分野を結び付け興味深い結果を得ている点、理論と実際の数値計算の両面についてバランスよく目配りがされている点などは十分に評価することができる。よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。