Tutte seminar - Levent Tuncel

Foundations of Primal-Dual Symmetric Interior-Point Methods for Convex Optimization

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 the general convex optimization setting.

This talk is based on joint work with Tor Myklebust.