Complexity analysis and numerical implementation of a short-step primal-dual algorithm for linear complementarity problems |
| |
Authors: | Mohamed Achache |
| |
Institution: | Laboratoire de Mathématiques Fondamentales et Numériques, Université Ferhat Abbas de Sétif, Algeria |
| |
Abstract: | 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 , iteration bound. For its numerical performances some strategies are used. Finally, we have tested this algorithm on some monotone linear complementarity problems. |
| |
Keywords: | Linear complementarity problems Interior point methods Primal-dual algorithms Polynomial complexity Numerical implementation |
本文献已被 ScienceDirect 等数据库收录! |
|