## Klee-Minty cubes and the central path

- Date: 10/25/2007

Tamás Terlaky (McMaster University)

University of Calgary

We consider a family of LO 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-1 sharp turns. This fact suggests

that any feasible path-following IPM will take at least 2^n iterations

to solve this problem. This construction exhibits the worst-case

iteration-complexity of IPMs. In addition, we discuss some implications

for the curvature of the central path.

Joint work with: Antoine Deza, Eissa Nematollahi, Reza Peyghami and Yuriy Zinhenko.

PIMS Distinguished Lecture 2007