Tutte seminar - Levent Tunçel

Local Quadratic Convergence of Polynomial-Time Interior-Point Methods for Nonlinear Convex Optimization Problems

Abstract:

We propose new path-following predictor-corrector schemes for solving convex optimization problems in conic form. The main structural property used in our analysis is the logarithmic homogeneity of self-concordant barrier functions. Even though our analysis has primal and dual components, our algorithms work with the dual iterates only, in the dual space. Our algorithms converge globally as the current best polynomial-time interior-point methods. In addition, our algorithms have the local quadratic convergence property under some mild assumptions. The algorithms are based on an easily computable gradient proximity measure, which ensures an automatic transformation of the global linear rate of convergence to the local quadratic one under some mild assumptions. Our step-size procedure for the predictor step is related to the maximum step size (the one that takes us to the boundary). 

This talk is based on joint work with Yu. Nesterov.