Local quadratic convergence of polynomial-time interior-point methods for conic optmization problems
(2009)
Files
coredp2009_72web.pdf
Open Access - Adobe PDF
- 480.79 KB
Details
- Authors
- Abstract
- In this paper, we establish a local quadratic convergence of 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.
- Affiliations
University of Waterloo Department of Combinatorics and Optimization
Citations
Nesterov, Y., & Tuncel, L. (2009). Local quadratic convergence of polynomial-time interior-point methods for conic optmization problems (CORE Discussion Paper 2009/72). https://hdl.handle.net/2078.5/250282