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

چکیده:

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.

کد مقاله = 1002