-

 

 

 




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

 

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