  


How good are interior point methods? KleeMinty cubes tighten iterationcomplexity bounds.
Antoine Deza (dezamcmaster.ca) Abstract: By refining a variant of the KleeMinty example that forces the central path to visit all the vertices of the KleeMinty ncube, we exhibit a nearly worstcase example for pathfollowing interior point methods. Namely, while the theoretical iterationcomplexity upper bound is O(2^{n}n^{\frac{5}{2}}), we prove that solving this ndimensional linear optimization problem requires at least $2^n1$ iterations. Keywords: Linear programming, interior point method, worstcase iterationcomplexity Category 1: Linear, Cone and Semidefinite Programming Category 2: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: AdvOLReport #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  