On the Convergence Rate of Newton Interior-Point Methods in the Absence of Strict Complementarity

In the absence of strict complementarity, Monteiro and Wright proved that the convergence rate for a class of Newton interior-point methods for linear complementarity problems is at best linear. They also established an upper bound of ¼ for the Q1 factor of the duality gap sequence when the steplengths converge to one. In the current paper, we prove that the Q1 factor of the duality gap sequence is exactly ¼. In addition, the convergence of the Tapia indicators is also discussed