On the Convergence Rate of Newton Interior-Point Methods
in the Absence of Strict Complementarity
A. S. El-Bakry, R. A. Tapia and Y. Zhang
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 $1/4$ for the $Q_1$-factor of the duality gap sequence when the
steplengths converge to one. In the current paper, we prove that the
$Q_1$ factor of the duality gap sequence is exactly $1/4$. In addition,
the convergence of the Tapia indicators is also discussed.
Technical Report, revised May, 1995.