zbMATH — the first resource for mathematics

On the convergence rate of Newton interior-point methods in the absence of strict complementarity. (English) Zbl 0862.90120
Summary: In the absence of strict complementarity, R. D. C. Monteiro and S. J. Wright [Comput. Optim. Appl. 3, No. 2, 131-155 (1994; Zbl 0801.90110)] 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. 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.

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
Full Text: DOI
[1] A.S. El-Bakry, ”On the role of indicators in identifying zero variables in linear programming,” Ph.D. Thesis, Department of Mathematical Sciences, Rice University, Houston, Texas 77251, 1991.
[2] A.S. El-Bakry, R.A. Tapia, and Y. Zhang, ”A study of indicators for identifying zero variables in interior-po methods,” SIAM Review, vol. 36, pp. 45–72, 1994. · Zbl 0801.65056 · doi:10.1137/1036003
[3] A.J. Goldman and A.W. Tucker, ”Theory of linear programming,” in H.W. Kuhn and A.W. Tucker (Eds.), Linear Inequalities and Related Systems, Princeton University Press, 1956, pp. 53–97. · Zbl 0072.37601
[4] O. Güler and Y. Ye, ”Convergence behavior of some interior-point algorithms,” Math. Programming, Series A, vol. 60, pp. 215–228, 1993. · Zbl 0803.90087 · doi:10.1007/BF01580610
[5] W. Hock and K. Schittkowski, Test Examples for Nonlinear Programming Codes, Springer-Verlag, New York, 1981. · Zbl 0452.90038
[6] S. Mizuno, ”A superlinearly convergent infeasible interior-point algorithm for geometric LCPs without a strictly complementary solution,” Technical Report 878, School of Operations Research and Industrial Engineering, Cornell University, 1994. · Zbl 0857.90126
[7] R.C. Monteiro and S. Wright, ”Local convergence of interior-point algorithms for degenerate monotone LCP problems,” Computational Optimization and Applications, vol. 3, pp. 131–155, 1994. · Zbl 0801.90110 · doi:10.1007/BF01300971
[8] J.M. Ortega and W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970. · Zbl 0241.65046
[9] F.A. Potra and R. Sheng, ”A superlinearly convergent infeasible interior-point algorithm for degenerate LCP,” Technical Report 66, Department of Mathematics, Iowa University, Iowa 52242, 1995. · Zbl 0907.90261
[10] Y. Zhang, R.A. Tapia, and J.E. Dennis, ”On the superlinear and quadratic convergence of primal-dual interiorpoint linear programming algorithms,” SIAM J. on Optimization, vol. 2, pp. 304–324, 1992. · Zbl 0763.90066 · doi:10.1137/0802015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.