Optimization Online


Local superlinear convergence of polynomial-time interior-point methods for hyperbolic cone optimization problems

Yu. Nesterov (nesterov***at***core.ucl.ac.be)
L. Tuncel (ltuncel***at***math.uwaterloo.ca)

Abstract: In this paper, we establish the local superlinear convergence property of some polynomial-time interior-point methods for an important family of conic optimization problems. The main structural property used in our analysis is the logarithmic homogeneity of self-concordant barrier function, which must have {\em negative curvature}. We propose a new path-following predictor-corrector scheme, which work only in the dual space. It is based on an easily computable gradient proximity measure, which ensures an automatic transformation of the global linear rate of convergence to the local superlinear one under some mild assumptions. Our step-size procedure for the predictor step is related to the maximum step size maintaining feasibility. As the optimal solution set is approached, our algorithm automatically tightens 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 superlinear 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 (revised: December 2014).

Download: [PDF]

Entry Submitted: 11/13/2009
Entry Accepted: 11/13/2009
Entry Last Modified: 12/08/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