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

Antoine Deza (dezamcmaster.ca)
Eissa Nematollahi (nematoemcmaster.ca)
Tamas Terlaky (terlakymcmaster.ca)

Abstract: 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.

Keywords: Linear programming, interior point method, worst-case iteration-complexity

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: AdvOL-Report #2004/20 Advanced Optimization Laboratory, Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada, December 2004.

Download: [Postscript][PDF]

Entry Submitted: 12/31/2004
Entry Accepted: 12/31/2004
Entry Last Modified: 02/05/2006

Modify/Update this entry