Short-step Methods Are Not Strongly Polynomial-Time
Not on the map. Why?
Abstract (arXiv)
Short-step methods are an important class of algorithms for solving convex constrained optimization problems. In this short paper, we show that under very mild assumptions on the self-concordant barrier and the width of the ℓ2-neighbourhood, any short-step interior-point method is not strongly polynomial-time.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). First posted on arXiv 8 Jan 2022.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2022: 1; 2023: 1; 2024: 1.
3 papers.
- 2023On the Sample Complexity of Imitation Learning for Smoothed Model Predictive Controlcited by 3
- 2022Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexitycited by 0
- 2024Improved Sample Complexity of Imitation Learning for Barrier Model Predictive Controlcited by 0
- 2024Improved Sample Complexity of Imitation Learning for Barrier Model Predictive Control1 Oct 2024
- 2023On the Sample Complexity of Imitation Learning for Smoothed Model Predictive Control2 Jun 2023
- 2022Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity7 Aug 2022