primal-dual newton method

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 … Read more