- | ||||
|
![]()
|
How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds.
Antoine Deza (deza 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 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 | |
![]() |