Recently, the authors presented a new large-update primal-dual 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 interior-point 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 large-update 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 large-update methods, and is quite close to the currently best iteration bound known for interior-point methods, namely $O\br{\sqrt{n}\,\log\frac{n}{\e}}$. Hence, the existing gap between the iteration bounds for small-update and large-update methods is substantially narrowed.
Citation
TU Delft, NL/McMaster University, Hamilton January 2001