IJPAM: Volume 28, No. 1 (2006)

AN ITERATIVE ALGORITHM FOR THE LINEAR
COMPLEMENTARITY PROBLEM WITH AN $H$-MATRIX

Lei Li$^1$, Yushi Sato$^2$
$^{1,2}$Faculty of Engineering
Hosei University
Koganei, Tokyo, 184-8584, JAPAN
$^1$e-mail: lilei@k.hosei.ac.jp


Abstract.It is well known that the linear complementarity problem LCP($A$, $q$) which consists of finding a vector $z\in R^n$ such that

\begin{displaymath}Az+q\ge 0, \quad z\ge 0, \quad z^T(Az+q)=0,\end{displaymath}

where $A\in R^{n\times n}$ and $q\in R^n$ are a given real matrix and a real vector, respectively. We have proposed an $O(n^3)$ direct recursive algorithm when $A$ is an $M$-matrix [#!1!#]. In [#!2!#], a block version of the algorithm was considered. Many numerical examples are showing that the block version takes fewer number of the arithmetic operations than the non-block version. In this paper, we propose a kind of splitting algorithms for solving LCP($A$, $q$), where $A$ is an $H$-matrix. The main idea of the algorithm is to devide the $H$-matrix into an $M$-matrix and a nonnegative matrix, and to solve an LCP with the $M$-matrix as subproblems. Some numerical examples are shown.

Received: April 15, 2006

AMS Subject Classification: 90C33

Key Words and Phrases: linear complementarity problem, $H$-matrix, iterative algorithm

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2006
Volume: 28
Issue: 1