Primal central paths and Riemannian distances for convex sets (Q1029546)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Primal central paths and Riemannian distances for convex sets |
scientific article |
Statements
Primal central paths and Riemannian distances for convex sets (English)
0 references
13 July 2009
0 references
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})\).
0 references
Riemannian geometry
0 references
convex optimization
0 references
structural optimization
0 references
interior-point methods
0 references
path-following methods
0 references
self-concordant functions
0 references
polynomial-time methods
0 references