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^{\frac{5}{2}}), we prove that solving this n-dimensional linear optimization problem requires at least $2^n-1$ iterations.
Citation
AdvOL-Report #2004/20 Advanced Optimization Laboratory, Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada, December 2004.
Article
View How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds.