The Mizuno-Todd-Ye algorithm in a larger neighborhood of the central path

Florian A. Potra

The Mizuno-Todd-Ye predictor--corrector method based on two neighborhoods $\cald(\alpha)\subset\cald(\alphabar)$ of the central path of a monotone homogeneous linear complementarity problem is analyzed, where $\cald(\alpha)$ is composed of all feasible points with $\delta$-proximity to the central path less than or equal to $\alpha$. The largest allowable value for $\alphabar$ is $\approx 1.76$. For a specific choice of $\alpha$ and and $\alphabar$ a lower bound of $\chi_n /\sqrt{n}$ is obtained for the stepsize along the affine-scaling direction, where $\chi_n$ has an asympotic value greater than $1.08$. For $n\ge400$ it is shown that $\chi_n > 1.05$. The algorithm has $O(\sqrt{n}L)$-iteration complexity under general conditions and quadratic convergence under the strict complementarity assumption.

Preprint. Department of Mathematics and Statistics, University of Maryland Baltimore County. November 2000