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

The Mizuno-Todd-Ye predictor-corrector method based on two neighborhoods D(alpha) subset of D((α) over bar) of the central path of a monotone homogeneous linear complementarity problem is analyzed. where D(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 (α) over bar is approximate to1.76. For a specific choice of alpha and (α) over bar lower bound of chi(n)/rootn is obtained for the stepsize along the affine-scaling direction, where chi(n) has an asymptotic value greater than 1.08. For n greater than or equal to 400 it is shown that chi(n) > 1.05. The algorithm has O(rootnL)-iteration complexity under general conditions and quadratic convergence under the strict complementarity assumption. (C) 2002 Elsevier Science B.V. All rights reserved.