Key points are not available for this paper at this time.
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 mincTx: Ax = b, x 0 with decision variable x ⁿ, e 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 (T (₀/) +n^3. 5 ({^*A}) ) iterations, where T (t) \n² (t), t\ for all t > 0 and {^*A} is a scaling invariant condition number associated with the matrix A. More specifically, {^*A} is the infimum of all the conditions numbers ₀₃, 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. 5LA+ \n² L, L\) iteration-complexity bound for the MTY P-C algorithm to find a primal-dual optimal solution, where LA 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 log L.
Monteiro et al. (Sat,) studied this question.