Local quadratic convergence of polynomial-time interior-point methods for conic optimization problem

Yu. Nesterov(nesterovcore.ucl.ac.be)
L. Tuncel(ltuncelmath.uwaterloo.ca)

Abstract: In this paper, we establish the local quadratic convergence of some polynomial-time interior-point methods for general conic optimization problems. The main structural property used in our analysis is the logarithmic homogeneity of self-concordant barrier functions. We propose new path-following predictor-corrector schemes which work only in the dual space. They 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). It appears that in order to obtain local superlinear convergence, we need to tighten the neighborhood of the central path proportionally to the current duality gap.

Keywords: Conic optimization problem, worst-case complexity analysis, self-concordant barriers, polynomial-time methods, predictor-corrector methods, local quadratic convergence.

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: CORE Discussion Paper 2009/72, Center for Operations Research and Econometrics (CORE), Catholic University of Louvain (UCL), Belgium, November 2009.

Download: [PDF]

Entry Submitted: 11/13/2009
Entry Accepted: 11/13/2009
Entry Last Modified: 11/13/2009

Modify/Update this entry