A New and Efficient Large-Update Interior-Point Method for Linear Optimization

Jiming Peng , Cornelis Roos, Tam´as , Terlaky , Recently, in [10], the authors presented a new large-update primal-dual method for Linear Optimization, whose O(n 2 3 log n ) iteration bound substantially improved the classical bound for such methods, which is O n log n . In this paper we present an improved analysis of the new method. The analysis uses some new mathematical tools, partially developed in [11], where we consider a whole family of interior-point methods which contains the method considered in this paper. The new analysis yields an O p n log n log n iteration bound for large-update methods. Since we concentrate on one specic member of the family considered in [11], the analysis is signicantly simpler than in [11]. The new bound further improves the iteration bound for large-update methods, and is quite close to the currently best iteration bound known for interior-point methods, namely O p n log n . Hence, the existing gap between the iteration bounds for small-update and large-update methods in substantially narrowd