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.

[POSTSCRIPT] [IP PAGE] [SEARCH AGAIN]