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

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 2n−1 iterations.