##
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

Contact: potra@math.umbc.edu