We consider a family of linear optimization problems over the n-dimensional Klee-Minty cube and show that the central path may visit all of its vertices in the same order as simplex methods do. This is achieved by carefully adding an exponential number of redundant constraints that forces the central path to take at least 2^n-2 sharp turns. This fact suggests that any feasible path-following interior-point method will take at least O(2^n) iterations to solve this problem, while in practice typically only a few iterations, e.g., 50, suffices to obtain a high quality solution. Thus, the construction potentially exhibits the worst-case iteration-complexity known to date which almost matches the theoretical iteration-complexity bound for this type of methods. In addition, this construction gives a counterexample to a conjecture that the total central path curvature is O(n).
Citation
AdvOL-Report #2006/03 Advanced Optimization Laboratory, McMaster University, Hamilton, Ontario, Canada, March 2006.
Article
View Central path curvature and iteration-complexity for redundant Klee-Minty cubes