Primal central paths and Riemannian distances for convex sets (Q1029546): Difference between revisions

The main goal of the paper is to show that in the case of a bounded set endowed with a \(\nu\)-self-concordant barrier, the primal central paths are \(O(\nu^{1/4})\)-geodesic. In order to prove it, different lower bounds on the Riemannian length of a segment of a central path in terms of variation of the value of corresponding self-concordant function and the logarithm of the variation of the path parameter are established. This result is applied to different problem instances: finding a minimum of self-concordant function, feasibility problem and the standard minimization problem. The presence of ``the unpleasant factor'' \(O(\sqrt{\nu}/\ln\nu)\) in the ratio of the length of the central path and the corresponding Riemannian distance is due to the unboundedness of the basic feasible set. If the basic feasible set is bounded, then this ratio reduces to at most of the order \(O(\nu^{1/4})\).