Optimization Online


Interior-point algorithms for convex optimization based on primal-dual metrics

Tor Myklebust(tmyklebu***at***csclub.uwaterloo.ca)
Levent Tuncel(ltuncel***at***uwaterloo.ca)

Abstract: We propose and analyse primal-dual interior-point algorithms for convex optimization problems in conic form. The families of algorithms we analyse are so-called short-step algorithms and they match the current best iteration complexity bounds for primal-dual symmetric interior-point algorithm of Nesterov and Todd, for symmetric cone programming problems with given self-scaled barriers. Our results apply to any self-concordant barrier for any convex cone. We also prove that certain specializations of our algorithms to hyperbolic cone programming problems (which lie strictly between symmetric cone programming and general convex optimization problems in terms of generality) can take advantage of the favourable special structure of hyperbolic barriers. We make new connections to Riemannian geometry, integrals over operator spaces, Gaussian quadrature, and strengthen the connection of our algorithms to quasi-Newton updates and hence first-order methods in general.

Keywords: primal-dual interior-point methods, convex optimization, variable metric methods, local metric, self-concordant barriers, Hessian metric, polynomial-time complexity

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: manuscript arXiv:1411:2129, November 2014

Download: [PDF]

Entry Submitted: 11/28/2014
Entry Accepted: 11/28/2014
Entry Last Modified: 11/28/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society