Abstract

In the theory of modern interior-point algorithms, approaches that treat primal and the dual problems in a symmetric way have led to some of the deepest theoretical results as well as some of the most successful software in that area.

I will present some mathematical foundations for the design and analysis of primal-dual symmetric algorithms for convex optimization problems. These foundations make the generalization of such methods from linear and semidefinite optimization settings to general convex optimization setting possible. I will conclude with a complexity analysis which applies to a wide range of primal-dual interior-point algorithms. Our bound on the number of iterations extends the current best iteration complexity bounds from the special cases of linear and semidefinite optimization to hyperbolic cone programming as well as to the general convex optimization setting. There will be connections to Quasi-Newton methods and Riemannian geometry, among others.

This talk is based on joint work with Tor Myklebust.

Video Recording