Abstract:

This paper presents a class of path-following interior point algorithms for the monotone linear complementarity problems based on wide neighborhoods and the new directions with a parameter \theta. When the parameter \theta=1, the new direction is exactly the classical Newton direction. The algorithms have O(nL) iteration complexity when the parameter \theta is independent of the dimension n, which coincides with the best known iteration complexity for the classical wide neighborhood algorithms. When \theta=\sqrt{n/\beta\tau}, the algorithm has O(\sqrt{n}L) iteration complexity, the best iteration complexity obtained so far by any interior point method for solving linear complementarity problems, where \beta and \tau are neighborhood parameters. To our knowledge this is the first time that a class of interior point algorithms including the classical wide neighborhood path-following algorithm is proposed and analyzed.

Key words: linear complementarity problem, interior-point method, path-following algorithm, wide neighborhood, polynomial complexity