2014/11/08 by Tor G. J. Myklebust, Myklebust, Tor, Levent Tunçel +2 · 1 citation
Computer Science · Engineering · Mathematics · #49M37 #52A41 #65Y20 #90C05 #90C22 #90C25 #90C30 #90C51 #90C60 #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1411.2129
openalex publication_date 2014/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose and analyse primal-dual interior-point algorithms for convex\noptimization problems in conic form. The families of algorithms we analyse are\nso-called short-step algorithms and they match the current best iteration\ncomplexity bounds for primal-dual symmetric interior-point algorithm of\nNesterov and Todd, for symmetric cone programming problems with given\nself-scaled barriers. Our results apply to any self-concordant barrier for any\nconvex cone. We also prove that certain specializations of our algorithms to\nhyperbolic cone programming problems (which lie strictly between symmetric cone\nprogramming and general convex optimization problems in terms of generality)\ncan take advantage of the favourable special structure of hyperbolic barriers.\nWe make new connections to Riemannian geometry, integrals over operator spaces,\nGaussian quadrature, and strengthen the connection of our algorithms to\nquasi-Newton updates and hence first-order methods in general.\n