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

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

0.00 Avg rating0 Votes
Article ID: iaor20132839
Volume: 157
Issue: 3
Start Page Number: 749
End Page Number: 780
Publication Date: Jun 2013
Journal: Journal of Optimization Theory and Applications
Authors: , ,
Keywords: information
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.’

Reviews

Required fields are marked *. Your email address will not be published.