Local superlinear convergence of polynomial-time interior-point methods for hyperbolicity cone optimization problems
(2016) SIAM Journal on Optimization — Vol. 26, n° 1, p. 139-170 (2016)
Files
Rep2792.pdf
Closed Access - Adobe PDF
- 444.34 KB
Details
- Authors
- 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 negative curvature. We propose a new path-following predictor- corrector scheme, which works 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 conver- gence 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 solu- tion set is approached, our algorithm automatically tightens the neighborhood of the central path proportionally to the current duality gap.
- Affiliations
Citations
Nesterov, Y., & Tuncel, L. (2016). Local superlinear convergence of polynomial-time interior-point methods for hyperbolicity cone optimization problems. SIAM Journal on Optimization, 26(1), 139-170. https://doi.org/10.1137/140998950 (Original work published 2016)