Short-step methods are not strongly polynomial-time
成果类型：
Article
署名作者：
Zong, Manru; Lee, Yin Tat; Yue, Man-Chung
署名单位：
University of Hong Kong; University of Washington; University of Washington Seattle
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-023-02002-x
发表日期：
2024
页码：
733-746
关键词：
摘要：
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 l(2)-neighbourhood, any short-step interior-point method is not strongly polynomial-time.