Title: A new iteration-complexity bound for the MTY predictor-corrector algorithm

In this paper we present a new iteration-complexity bound for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) primal-dual interior-point algorithm for linear programming. The analysis of the paper is based on the important notion of crossover events introduced by Vavasis and Ye. For a standard form linear program min{c^Tx : Ax=b, x ≥ 0} with decision variable x ∈ Rⁿ, we show that the MTY P-C algorithm started from a well-centered interior-feasible solution with duality gap nμ₀ finds an interior-feasible solution with duality gap less than nη in O(n²log(log (μ₀/η)) + n^3.5log(χ^*A + n)) iterations, where χ^*A is a scaling invariant condition number associated with the matrix A. More specifically, χ^*A is the infimum of all the conditions numbers χ_AD, where D varies over the set of positive diagonal matrices. Under the setting of the Turing machine model, our analysis yields an O(n^3.5L_A + n²logL)) iteration-complexity bound for the MTY P-C algorithm to find a primal-dual optimal solution, where L_A and L are the input sizes of the matrix A and the data (A, b, c), respectively. This contrasts well with the classical iteration-complexity bound for the MTY P-C algorithm which depends linearly on L instead of logL.
Joint work with Takashi Tsuchiya.