Elfoutayeni, Youssef; Khaladi, Mohamed A new interior point method for linear complementarity problem. (English) Zbl 1263.90099 Appl. Math. Sci., Ruse 4, No. 65-68, 3289-3306 (2010). Summary: For a given \(n\)-vector \(q\) and a real square matrix \(M \in \mathbb R^{n\times n}\), the linear complementarity problem denoted by \(LCP(M,q)\), is that of finding a nonnegative vector \(z \in \mathbb R^n\) such that \(z^T(Mz+q)=0\) and \(Mz+q\geq 0\). In this paper, we suppose that the matrix \(M\) must be symmetric and positive definite and the set \[ S=\{z \in \mathbb R^n | z > 0 \text{ and } Mz+q > 0\}; \] named interior points set of the \(LCP(M,q)\) must be nonempty. The aim of this paper is to show that the \(LCP(M,q)\) is completely equivalent to a convex quadratic programming problem \((CQPP)\) under linear constraints. To solve the second problem, we propose an iterative method of interior points which converge in polynomial time to the exact solution; this convergence requires at most \(o(n^{0,5}L)\) iterations, where \(n\) is the number of the variables and \(L\) is the length of a binary coding of the input; furthermore, the algorithm does not exceed \(o(n^{3,5}L)\) arithmetic operations until its convergence, and in the end, we close our paper with some numerical examples which illustrate our theoretical results. Cited in 3 Documents MSC: 90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) 90C51 Interior-point methods Keywords:linear complementarity problem; convex quadratic programming with equilibrium constraints; matrix symmetric and positive definite; interior point algorithm Y PDFBibTeX XMLCite \textit{Y. Elfoutayeni} and \textit{M. Khaladi}, Appl. Math. Sci., Ruse 4, No. 65--68, 3289--3306 (2010; Zbl 1263.90099) Full Text: Link