  


Central path curvature and iterationcomplexity for redundant KleeMinty cubes
Antoine Deza (dezamcmaster.ca) Abstract: We consider a family of linear optimization problems over the ndimensional KleeMinty cube and show that the central path may visit all of its vertices in the same order as simplex methods do. This is achieved by carefully adding an exponential number of redundant constraints that forces the central path to take at least 2^n2 sharp turns. This fact suggests that any feasible pathfollowing interiorpoint method will take at least O(2^n) iterations to solve this problem, while in practice typically only a few iterations, e.g., 50, suffices to obtain a high quality solution. Thus, the construction potentially exhibits the worstcase iterationcomplexity known to date which almost matches the theoretical iterationcomplexity bound for this type of methods. In addition, this construction gives a counterexample to a conjecture that the total central path curvature is O(n). Keywords: linear programming, central path, interiorpoint methods, total curvature Category 1: Linear, Cone and Semidefinite Programming Category 2: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: AdvOLReport #2006/03 Advanced Optimization Laboratory, McMaster University, Hamilton, Ontario, Canada, March 2006. Download: [PDF] Entry Submitted: 08/22/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  