No. 856

Title:

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

Author(s):

Renato D. C. Monteiro (School of Industrial and Systems Engineering, Georgia Institute of Technology);
Takashi, Tsuchiya (The Institute of Statistical Mathematics)

Key words:

Interior-point algorithms, primal-dual algorithms, path-following,@central path, layered steps, condition number, polynomial complexity,@crossover events, scale-invariance, predictor-corrector,@affine scaling, strongly polynomial, linear programming.

Abstract:

In this paper we present a new iteration-complexity bound for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) primal-dualinterior-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{cTx : Ax=b, x † 0}$ with decision variable $x \in \Re^n$, we show that the MTY P-C algorithm started from a well-centered interior-feasible solution with duality gap $n \mu_0$ finds an interior-feasible solution with duality gap less than $n \eta$ in ${\cal O}( n^2 \log ( \log (\mu_0/\eta)) + n^{3.5}\log(\chistarA + n) )$ iterations, where $\chistarA$ is a scaling invariant condition number associated with the matrix $A$. More specifically, $\chistarA$ is the infimum of all the conditions numbers ${\bar \chi}_{AD}$, where $D$ varies over the set of positive diagonal matrices. Under the setting of the Turing machine model, our analysis yields an ${\cal O}(n^{3.5}L_A + n^2 \log 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.