Optimization Online


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

Antoine Deza (deza***at***mcmaster.ca)
Eissa Nematollahi (nematoe***at***mcmaster.ca)
Tamas Terlaky (terlaky***at***mcmaster.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society