×

A new interior point method for linear complementarity problem. (English) Zbl 1263.90099

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.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C51 Interior-point methods
PDFBibTeX XMLCite
Full Text: Link