How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds

• 成果类型: Article
• 署名作者: Deza, Antoine; Nematollahi, Eissa; Terlaky, Tamas
• 署名单位: McMaster University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-006-0044-x
• 发表日期: 2008
• 页码: 1-14
• 关键词: algorithms

摘要

By refining a variant of the Klee-Minty example that forces the central path to visit all the vertices of the Klee-Minty n-cube, we exhibit a nearly worst-case example for path-following interior point methods. Namely, while the theoretical iteration-complexity upper bound is O(2(n) n(5/2)), we prove that solving this n-dimensional linear optimization problem requires at least 2(n)-1 iterations.