zbMATH — the first resource for mathematics

Convergence of interior point algorithms for the monotone linear complementarity problem. (English) Zbl 0846.90109
Summary: The literature on interior point algorithms shows impressive results related to the speed of convergence of the objective values, but very little is known about the convergence of the iterate sequences. This paper studies the horizontal linear complementarity problem, and derives general convergence properties for algorithms based on Newton iterations. This problem provides a simple and general framework for most existing primal-dual interior point methods. The conclusion is that most of the published algorithms of this kind generate convergent sequences. In many cases (whenever the convergence is not too fast in a certain sense), the sequences converge to the analytic center of the optimal face.

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
49M15 Newton-type methods
65K05 Numerical mathematical programming methods
Full Text: DOI