Information Geometry and Interior-Point Algorithms in Semidefinite Programs and Symmetric Cone Programs

Satoshi Kakihara (), Atsumi Ohara () and Takashi Tsuchiya ()
Additional contact information
Satoshi Kakihara: National Graduate Institute for Policy Studies
Atsumi Ohara: University of Fukui
Takashi Tsuchiya: National Graduate Institute for Policy Studies

Journal of Optimization Theory and Applications, 2013, vol. 157, issue 3, No 10, 749-780

Abstract: Abstract We develop an information geometric approach to conic programming. Information geometry is a differential geometric framework specifically tailored to deal with convexity, naturally arising in information science including statistics, machine learning and signal processing etc. First we introduce an information geometric framework of conic programming. Then we focus on semidefinite and symmetric cone programs. Recently, we demonstrated that the number of iterations of Mizuno–Todd–Ye predictor–corrector primal–dual interior-point methods is (asymptotically) expressed with an integral over the central trajectory called “the curvature integral”. The number of iterations of the algorithm is approximated surprisingly well with the integral even for fairly large linear/semidefinite programs with thousands of variables. Here we prove that “the curvature integral” admits a rigorous differential geometric expression based on information geometry. We also obtain an interesting information geometric global theorem on the central trajectory for linear programs. Together with the numerical evidence in the aforementioned work, we claim that “the number of iterations of the interior-point algorithm is expressed as a differential geometric quantity.”

Keywords: Interior-point methods; Iteration complexities; Curvature integral; Semidefinite programs; Symmetric cone programs; Conic programming; Information geometry (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-012-0180-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:157:y:2013:i:3:d:10.1007_s10957-012-0180-9

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-012-0180-9

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().