  


A New and Efficient LargeUpdate InteriorPoint Method for Linear Optimization
J Peng (pengjcas.mcmaster.ca) Abstract: Recently, the authors presented a new largeupdate primaldual method for Linear Optimization, whose $O(n^\frac23\,\log\frac{n}{\e})$ iteration bound substantially improved the classical bound for such methods, which is $O\br{n\log\frac{n}{\e}}$. In this paper we present an improved analysis of the new method. The analysis uses some new mathematical tools developed before when we considered a whole family of interiorpoint methods which contains the method considered in this paper. The new analysis yields an $O\br{\sqrt{n}\log n\,\log\frac{n}{\e}}$ iteration bound for largeupdate methods. Since we concentrate on one specific member of the family mentioned before, the analysis significantly simplifies. The new bound further improves the iteration bound for largeupdate methods, and is quite close to the currently best iteration bound known for interiorpoint methods, namely $O\br{\sqrt{n}\,\log\frac{n}{\e}}$. Hence, the existing gap between the iteration bounds for smallupdate and largeupdate methods is substantially narrowed. Keywords: Linear optimization, interiorpoint method, primaldual Newton method, largeupdate method, polynomial complexity Category 1: Linear, Cone and Semidefinite Programming Citation: TU Delft, NL/McMaster University, Hamilton January 2001 Download: [Postscript][PDF] Entry Submitted: 01/31/2001 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  