Complexity analysis and numerical implementation of a short-step primal-dual algorithm for linear complementarity problems

摘要

In this paper we deal with the study of the polynomial complexity and numerical implementation for a short-step primal-dual interior point algorithm for monotone linear complementarity problems LCP. The analysis is based on a new class of search directions used by the author for convex quadratic programming (CQP) [M. Achache, A new primal-dual path-following method for convex quadratic programming, Computational and Applied Mathematics 25 (1) (2006) 97–110]. Here, we show that this algorithm enjoys the best theoretical polynomial complexity namely Onlognϵ, iteration bound. For its numerical performances some strategies are used. Finally, we have tested this algorithm on some monotone linear complementarity problems.