オハラ　アツミ   Atsumi Ohara   小原　敦美    所属   追手門学院大学  理工学部 数理・データサイエンス学科    職種   教授
言語種別	英語
発行・発表の年月	2013
形態種別	論文
査読	査読あり
標題	Information Geometry and Interior Point Algorithms
執筆形態	共著・編著（代表編著を除く）
掲載誌名	Geometric Science of Information (Frank Nielsen and Frederic Barbaresco eds.) Springer Lecture Notes in Computer Science
掲載区分	国外
巻・号・頁	8085,pp.777-784-784
著者・共著者	Satoshi Kakihara,A.Ohara,Takashi Tsuchiya
概要	In this paper, we introduce a geometric theory which relates a geometric structure of convex optimization problems to computational complexity to solve the problems. Specifically, we develop information geometric framework of conic linear optimization problems and show that the iteration complexity of the standard polynomial-time primal-dual predictor-corrector interior-point algorithms to solve symmetric cone programs is written with an information geometric curvature integral of the central path which the algorithm traces. Numerical experiments demonstrate that the number of iterations is quite well explained with the integral even for the large problems with thousands of variables we claim that the iteration-complexity of the primal-dual predictor-corrector path-following algorithm is an information geometric quantity. We also develop a global theorem about the central path for linear programs. © 2013 Springer-Verlag.
DOI	10.1007/978-3-642-40020-9_87
ISSN	0302-9743