Short-step Methods Are Not Strongly Polynomial-Time

MaRDI QIDQ6387760zbMATH OpenFDO

Authors Manru Zong, Yin Tat Lee, Man-Chung Yue

Publication date 8 January 2022

Abstract: 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 $el{l}_2$-neighbourhood, any short-step interior-point method is not strongly polynomial-time.

This page was built for publication: Short-step Methods Are Not Strongly Polynomial-Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6387760)