An Improved Convergence Condition of the MMS Iteration Method for Horizontal LCP of H₊-Matrices

Abstract

In this paper, inspired by the previous work in (Appl. Math. Comput., 369 (2020) 124890), we focus on the convergence condition of the modulus-based matrix splitting (MMS) iteration method for solving the horizontal linear complementarity problem (HLCP) with $H_{+}$-matrices. An improved convergence condition of the MMS iteration method is given to improve the range of its applications, in a way which is better than that in the above published article.

1. Introduction

As is known, the horizontal linear complementarity problem, for the given matrices $A,B\in {\mathbb{R}}^{n\times n}$, is to find that two vectors $z,w\in {\mathbb{R}}^n$ satisfy

$$Az=Bw+q\ge 0,z\ge 0,w\ge 0\mathrm{and}{z}^{T}w=0,$$

(1)

where $q\in {\mathbb{R}}^n$ is given, which is often abbreviated as HLCP. If $A=I$ in (1), the HLCP (1) is no other than the classical linear complementarity problem (LCP) in [1], where I denotes the identity matrix. This implies that the HLCP (1) is a general form of the LCP.

The HLCP (1), used as a useful tool, often arises in a diverse range of fields, including transportation science, telecommunication systems, structural mechanics, mechanical and electrical engineering, and so on, see [2,3,4,5,6,7]. In the past several years, some efficient algorithms have been designed to solve the HLCP (1), such as the interior point method [8], the neural network [9], and so on. Particularly, in [10], the modulus-based matrix splitting (MMS) iteration method in [11] was adopted to solve the HLCP (1). In addition, the partial motivation of the present paper is from complex systems with matrix formulation, see [12,13,14] for more details.

Recently, Zheng and Vong [15] further discussed the MMS method, as described below.

The MMS method [10,15]. Let $\mathrm{\Omega }$ be a positive diagonal matrix and $r>0$, and let $A=M_A-N_A$ and $B=M_B-N_B$ be the splitting of matrices A and B, respectively. Assume that $(z^{\left(0\right)},w^{\left(0\right)})$ is an arbitrary initial vector. For $k=0,1,2,\dots$ until the iteration sequence $(z^{\left(k\right)},w^{\left(k\right)})$ converges, compute $(z^{(k+1)},w^{(k+1)})$ by

$$z^{(k+1)}=\frac{1}{r}\left(\right|x^{(k+1)}|+x^{(k+1)}),w^{(k+1)}=\frac{1}{r}\mathrm{\Omega }\left(\right|x^{(k+1)}|-x^{(k+1)}),$$

(2)

where $x^{(k+1)}$ is obtained by

$$(M_A+M_B\mathrm{\Omega })x^{(k+1)}=(N_A+N_B\mathrm{\Omega })x^{\left(k\right)}+(B\mathrm{\Omega }-A)\left|x^{\left(k\right)}\right|+rq.$$

(3)

For the later discussion, some preliminaries are gone over. For a square matrix $A=\left(a_{ij}\right)\in {\mathbb{R}}^{n\times n}$, $\left|A\right|=\left(\right|a_{ij}\left|\right)$, and $\langle A\rangle =\left(\langle a_{ij}\rangle \right)$, where $\langle a_{ii}\rangle =\left|a_{ii}\right|$ and $\langle a_{ij}\rangle =-\left|a_{ij}\right|$ for $i\ne j$. A matrix $A=\left(a_{ij}\right)\in {\mathbb{R}}^{n\times n}$ is called a non-singular M-matrix if $A^{-1}\ge 0$ and $a_{ij}\le 0$ for $i\ne j$; an H-matrix if its comparison matrix $\langle A\rangle$ is a non-singular M-matrix; an $H_{+}$-matrix if it is an H-matrix with positive diagonals; and a strictly diagonally dominant (s.d.d.) matrix if $|a_{ii}|>{\sum }_{j\ne i}\left|a_{ij}\right|,i=1,2,\dots ,n$. In addition, $A\ge (>)B$ with $A,B\in {\mathbb{R}}^{n\times n}$, means $a_{ij}\ge (>)b_{ij}$ for $i,j=1,2,\dots ,n$.

For the MMS method with $H_{+}$-matrix, two new convergence conditions are obtained in [15], which are weaker than the corresponding convergence conditions in [10]. One of these is given below.

Theorem 1

([15]). Assume that $A,B\in {\mathbb{R}}^{n\times n}$ are two $H_{+}$-matrices and $\mathrm{\Omega }=diag\left({\omega }_{jj}\right)\in {\mathbb{R}}^{n\times n}$ with ${\omega }_{jj}>0,i,2,\dots ,n$,

$$|b_{ij}|{\omega }_{jj}\le \left|a_{ij}\right|(i\ne j)andsign\left(b_{ij}\right)=sign\left(a_{ij}\right),b_{ij}\ne 0.$$

Let $A=M_A-N_A$ be an H-splitting of A, $B=M_B-N_B$ be an H-compatible splitting of B, and $M_A+M_B\mathrm{\Omega }$ be an $H_{+}$-matrix. Then the MMS method is convergent, provided one of the following conditions holds:

(a) $\mathrm{\Omega }\ge D_A{D}_B^{-1}$;

(b) $\mathrm{\Omega }<D_A{D}_B^{-1}$,

$$D_B^{-1}(D_A-\frac{1}{2}{D}^{-1}(\langle A\rangle +\langle M_A\rangle -|N_A\left|\right)D)e<\mathrm{\Omega }e<D_A{D}_B^{-1}e$$

(4)

with $\mathrm{\Omega }=k{D}^{-1}{D}_1$ and $k<\parallel D_A{D}_B^{-1}{D}_1^{-1}{D\parallel }_{\infty }$, where $e={(1,1,\dots ,1)}^T$, D and $D_1$ are positive diagonal matrices such that $(\langle M_A\rangle -|N_A\left|\right)D$ and $(\langle M_B\rangle -|N_B\left|\right)D_1$ are two strictly diagonally dominant (s.d.d.) matrices.

At present, the difficulty in Theorem 1 is to check the condition (4). Besides that, the condition (4) of Theorem 1 is limited by the parameter k. That is to say, if the choice of k is improper, then we cannot use the condition (4) of Theorem 1 to guarantee the convergence of the MMS method. To overcome this drawback, the purpose of this paper is to provide an improved convergence condition of the MMS method, for solving the HLCP of $H_{+}$-matrices, to improve the range of its applications, in a way which is better than that in Theorem 1 [15].

2. An Improved Convergence Condition

In fact, by investigating condition (b) of Theorem 1, we know that the left inequality in (4) may have a flaw. Particularly, when the choice of k is improper, we cannot use condition (b) of Theorem 1 to guarantee the convergence of the MMS method. For instance, we consider two matrices

$$A=\left(\begin{array}{cc}6& 2\\ 2& 6\end{array}\right),B=\left(\begin{array}{cc}6& 1\\ 3& 6\end{array}\right).$$

To make A and B satisfy the convergence conditions of Theorem 1, we take

$$M_A=\left(\begin{array}{cc}6& 0\\ 3.5& 6\end{array}\right),N_A=\left(\begin{array}{cc}0& -2\\ 1.5& 0\end{array}\right),M_B=\left(\begin{array}{cc}6& 0\\ 0& 6\end{array}\right),N_B=\left(\begin{array}{cc}0& -1\\ -3& 0\end{array}\right).$$

By the simple computations,

$$\langle M_A\rangle -|N_A|=\left(\begin{array}{cc}6& -2\\ -5& 6\end{array}\right),(\langle M_A\rangle -|N_A{\left|\right)}^{-1}=\frac{1}{26}\left(\begin{array}{cc}6& 2\\ 5& 6\end{array}\right)\ge 0.$$

Hence, $\langle M_A\rangle -\left|N_A\right|$ is a non-singular M-matrix, so that $A=M_A-N_A$ is an H-splitting. On the other hand, $\langle B\rangle =\langle M_B\rangle -\left|N_B\right|$, so that $B=M_B-N_B$ is an H-compatible splitting.

For convenience, we take $D=D_1=I$, where I denotes the identity matrix. By simple calculations, we have

$$\begin{array}{c}\hfill D_B^{-1}(D_A-\frac{1}{2}{D}^{-1}(\langle A\rangle +\langle M_A\rangle -|N_A\left|\right)D)e=\left(\begin{array}{c}\frac{1}{3}\\ \frac{3.5}{6}\end{array}\right)\end{array}$$

and

$$\mathrm{\Omega }=k{D}^{-1}{D}_1=k\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right),andk<{\parallel D_A{D}_B^{-1}{D}_1^{-1}D\parallel }_{\infty }=1.$$

Further, we have

$$\mathrm{\Omega }e=k\left(\begin{array}{c}1\\ 1\end{array}\right).$$

Obviously, when $k\le 1/3$, we naturally do not get that

$$\left(\begin{array}{c}\frac{1}{3}\\ \frac{3.5}{6}\end{array}\right)<k\left(\begin{array}{c}1\\ 1\end{array}\right).$$

This implies that condition (b) of Theorem 1 may be invalid when we use condition (b) of Theorem 1 to judge the convergence of the MMS method for solving the HLCP. To overcome this disadvantage, we obtain an improved convergence condition for the MMS method, see Theorem 2, whose proof is similar to the proof of Theorem 2.5 in [15].

Theorem 2.

Assume that $A,B\in {\mathbb{R}}^{n\times n}$ are two $H_{+}$-matrices, and $\mathrm{\Omega }=diag\left({\omega }_{jj}\right)\in {\mathbb{R}}^{n\times n}$ with ${\omega }_{jj}>0,i,2,\dots ,n$,

$$|b_{ij}|{\omega }_{jj}\le \left|a_{ij}\right|(i\ne j)andsign\left(b_{ij}\right)=sign\left(a_{ij}\right),b_{ij}\ne 0.$$

Let $A=M_A-N_A$ be an H-splitting of A, $B=M_B-N_B$ be an H-compatible splitting of B, and $M_A+M_B\mathrm{\Omega }$ be an $H_{+}$-matrix. Then the MMS method is convergent, provided one of the following conditions holds:

(a) $\mathrm{\Omega }\ge D_A{D}_B^{-1}$;

(b) when $\mathrm{\Omega }<D_A{D}_B^{-1}$,

$$D_B^{-1}(D_A-\frac{1}{2}{D}^{-1}(\langle A\rangle +\langle M_A\rangle -|N_A\left|\right)D)e<\mathrm{\Omega }e<D_A{D}_B^{-1}e,$$

(5)

where D is a positive diagonal matrix, such that $\langle M_A+M_B\mathrm{\Omega }\rangle D$ is an s.d.d. matrix.

Proof. 

For Case (a), see the proof of Theorem 2.5 in [15].

For Case (b), by simple calculations, we have

$$\langle M_B\mathrm{\Omega }\rangle -|N_B\mathrm{\Omega }|=\langle M_B\rangle \mathrm{\Omega }-|N_B|\mathrm{\Omega }=\langle B\rangle \mathrm{\Omega },|B\mathrm{\Omega }-A|=\left|A\right|-\left|B\right|\mathrm{\Omega }\ge 0.$$

(6)

Making use of Equation (6), based on the proof of Theorem 2.5 in [15], we have

$$\begin{array}{cc}\hfill |x^{(k+1)}-x^{*}|\le & {\langle M_A+M_B\mathrm{\Omega }\rangle }^{-1}\left(\right|N_A+N_B\mathrm{\Omega }|+|B\mathrm{\Omega }-A\left|\right)|x^{\left(k\right)}-x^{*}|\hfill \\ \hfill =& {\langle M_A+M_B\mathrm{\Omega }\rangle }^{-1}\left(\right|N_A+N_B\mathrm{\Omega }|+|A|-|B\left|\mathrm{\Omega }\right)|x^{\left(k\right)}-x^{*}|\hfill \\ \hfill \le & {\langle M_A+M_B\mathrm{\Omega }\rangle }^{-1}\left(\right|N_A|+|N_B|\mathrm{\Omega }+|A|-|B\left|\mathrm{\Omega }\right)|x^{\left(k\right)}-x^{*}|\hfill \\ \hfill =& \widehat{W}|x^{\left(k\right)}-x^{*}|,\hfill \end{array}$$

where

$$\widehat{W}={\widehat{S}}^{-1}\widehat{T},\widehat{S}=\langle M_A+M_B\mathrm{\Omega }\rangle \mathrm{and}\widehat{T}=|N_A|+|N_B|\mathrm{\Omega }+|A|-|B|\mathrm{\Omega }.$$

Since $M_A+M_B\mathrm{\Omega }$ is an $H_{+}$-matrix, it follows that $\widehat{S}=\langle M_A+M_B\mathrm{\Omega }\rangle$ is a non-singular M-matrix, and the existence of such a matrix D (see [16], p. 137) satisfies

$$\widehat{S}De=\langle M_A+M_B\mathrm{\Omega }\rangle De>0.$$

From the left inequality in (5), we have

$$(2D_B\mathrm{\Omega }+\langle M_A\rangle -|N_A|-|A\left|\right)De>0.$$

(7)

Further, based on the inequality (7), we have

$$\begin{array}{cc}\hfill (\widehat{S}-\widehat{T})De& =(\langle M_A+M_B\mathrm{\Omega }\rangle -|N_A|-|N_B|\mathrm{\Omega }-|A|+|B\left|\mathrm{\Omega }\right)De\hfill \\ \hfill & \ge (\langle M_A\rangle +\langle M_B\rangle \mathrm{\Omega }-|N_A|-|N_B|\mathrm{\Omega }-|A|+|B\left|\mathrm{\Omega }\right)De\hfill \\ \hfill & =(\langle M_A\rangle -|N_A|-|A|+\langle M_B\rangle \mathrm{\Omega }-|N_B|\mathrm{\Omega }+|B\left|\mathrm{\Omega }\right)De\hfill \\ \hfill & =(\langle M_A\rangle -|N_A|-|A|+\langle B\rangle \mathrm{\Omega }+|B\left|\mathrm{\Omega }\right)De\hfill \\ \hfill & =(\langle M_A\rangle -|N_A|-|A|+2D_B\mathrm{\Omega })De\hfill \\ \hfill & >0.\hfill \end{array}$$

Thus, based on Lemma 2.3 in [15], we have

$$\begin{array}{cc}\hfill \rho \left(\widehat{W}\right)=& \rho \left(D^{-1}\widehat{W}D\right)\hfill \\ \hfill \le & \parallel D^{-1}\widehat{W}{D\parallel }_{\infty }\hfill \\ \hfill =& \parallel \left(\langle M_A+M_B\mathrm{\Omega }\rangle \right){D)}^{-1}\left(\right|N_A|+|N_B{|\mathrm{\Omega }+|A|-|B\left|\mathrm{\Omega }\right)D\parallel }_{\infty }\hfill \\ \hfill \le & \underset{1\le i\le n}{max}\frac{\left(\right(|N_A|+|N_B{|\mathrm{\Omega }+|A|-|B\left|\mathrm{\Omega }\right)De)}_i}{{\left(\langle M_A+M_B\mathrm{\Omega }\rangle De\right)}_i}\hfill \\ \hfill <& 1.\hfill \end{array}$$

The proof of Theorem 2 is completed. □

Comparing Theorem 2 with Theorem 1, the advantage of the former is that condition (b) of Theorem 2 is not limited by the parameter k of the latter. Besides that, we do not need to find two positive diagonal matrices D and $D_1$, such that $(\langle M_A\rangle -|N_A\left|\right)D$ and $(\langle M_B\rangle -|N_B\left|\right)D_1$ are, respectively, s.d.d. matrices, we just find one positive diagonal matrix D, such that $\langle M_A+M_B\mathrm{\Omega }\rangle D$ is an s.d.d. matrix.

Incidentally, there exists a simple approach to obtain a positive diagonal matrix D in Theorem 2: first, solving the system $\overline{A}x=e$ gives the positive vector x, where $\overline{A}=\langle M_A+M_B\mathrm{\Omega }\rangle$; secondly, we take $D=diag\left({\overline{A}}^{-1}e\right)$, which can make $\langle M_A+M_B\mathrm{\Omega }\rangle D$ an s.d.d. matrix.

In addition, if the $H_{+}$-matrix $M_A+M_B\mathrm{\Omega }$ itself is an s.d.d. matrix, then we can take $D=I$ in Theorem 2. In this case, we can obtain the following corollary.

Corollary 1.

Assume that $A,B\in {\mathbb{R}}^{n\times n}$ are two $H_{+}$-matrices, and $\mathrm{\Omega }=diag\left({\omega }_{jj}\right)\in {\mathbb{R}}^{n\times n}$ with ${\omega }_{jj}>0,i,2,\dots ,n$,

$$|b_{ij}|{\omega }_{jj}\le \left|a_{ij}\right|(i\ne j)andsign\left(b_{ij}\right)=sign\left(a_{ij}\right),b_{ij}\ne 0.$$

Let $A=M_A-N_A$ be an H-splitting of A, $B=M_B-N_B$ be an H-compatible splitting of B, and the $H_{+}$-matrix $M_A+M_B\mathrm{\Omega }$ be an s.d.d. matrix. Then, the MMS method is convergent, provided one of the following conditions holds:

(a) $\mathrm{\Omega }\ge D_A{D}_B^{-1}$;

(b) when $\mathrm{\Omega }<D_A{D}_B^{-1}$,

$$D_B^{-1}(D_A-\frac{1}{2}(\langle A\rangle +\langle M_A\rangle -|N_A\left|\right))e<\mathrm{\Omega }e<D_A{D}_B^{-1}e.$$

3. Numerical Experiments

In this section, we consider a simple example to illustrate our theoretical results in Theorem 2. All the computations are performed in MATLAB R2016B.

Example 1.

Consider the HLCP $(A,B,q)$, in which $A=\overline{A}+\mu I$, $B=\overline{B}+\nu I$, where $\overline{A}=blktridiag(-I,S,-I)\in {\mathbb{R}}^{n\times n}$, $\overline{B}=I\otimes S\in {\mathbb{R}}^{n\times n}$, $S=tridiag(-1,4,-1)\in {\mathbb{R}}^{m\times m}$, and μ, ν are real parameters. Let $q=A{z}^{*}-B{w}^{*}$, with

$$z^{*}={(0,1,0,1\dots ,0,1,\dots )}^T\in {\mathbb{R}}^n,w^{*}={(1,0,1,0\dots ,1,0,\dots )}^T\in {\mathbb{R}}^n.$$

In our calculations, we take $\mu =4$ and $\nu =0$ for A and B in Example 1, $x^{\left(0\right)}={(2,2,\dots ,2)}^T\in {\mathbb{R}}^n$ is used for the initial vector. The modulus-based Jacobi (NMJ) method and Gauss–Seidel (NMGS) method, with $r=2$, are adopted. The NMJ and NMGS methods are stopped once the number of iterations is larger than 500 or the norm of residual vectors (RES) is less than ${10}^{-6}$, where

$$\mathrm{RES}:=\parallel A{z}^k-B{w}^k{-q\parallel }_2.$$

Here, we consider two cases of Theorem 2. When $\mathrm{\Omega }\ge D_A{D}_B^{-1}$, we take $\mathrm{\Omega }=2I$ for the NMJ method and the NMGS method. In this case,

Table 1. Numerical results for $\mathrm{\Omega }=2I$.

	m	100	200	300
NMJ	IT	30	31	32
	CPU	0.0381	0.2120	0.4114
	RES	6.35 × 10${}^{-7}$	6.61 × 10${}^{-7}$	5.02 × 10${}^{-7}$
NMGS	IT	19	20	20
	CPU	0.0314	0.0952	0.2488
	RES	6.86 × 10${}^{-7}$	4.79 × 10${}^{-7}$	7.30 × 10${}^{-7}$

is obtained. When $\mathrm{\Omega }<D_A{D}_B^{-1}$, we take $D=I$, and obtain that $I<\mathrm{\Omega }<2I$ and $\langle M_A+M_B\mathrm{\Omega }\rangle D$ is an s.d.d. matrix. In this case, we take $\mathrm{\Omega }=1.5I$ and $\mathrm{\Omega }=1.2I$ for the NMJ and NMGS methods, and obtain

Table 2. Numerical results for $\mathrm{\Omega }=1.5I$.

	m	100	200	300
NMJ	IT	29	30	31
	CPU	0.0379	0.1553	0.3976
	RES	9.71 × 10${}^{-7}$	9.05 × 10${}^{-7}$	6.65 × 10${}^{-7}$
NMGS	IT	18	19	19
	CPU	0.0243	0.0931	0.2300
	RES	6.01 × 10${}^{-7}$	4.00 × 10${}^{-7}$	6.11 × 10${}^{-7}$

and

Table 3. Numerical results for $\mathrm{\Omega }=1.2I$.

	m	100	200	300
NMJ	IT	39	39	40
	CPU	0.0474	0.1930	0.5127
	RES	6.78 × 10${}^{-7}$	9.78 × 10${}^{-7}$	8.12 × 10${}^{-7}$
NMGS	IT	20	20	21
	CPU	0.0283	0.1109	0.2595
	RES	4.76 × 10${}^{-7}$	8.47 × 10${}^{-7}$	4.59 × 10${}^{-7}$

.

The numerical results in Table 1, Table 2 and Table 3 not only further confirm that the MMS method is feasible and effective, but also show that the convergence condition in Theorem 2 is reasonable.

4. Conclusions

In this paper, the modulus-based matrix splitting (MMS) iteration method for solving the horizontal linear complementarity problem (HLCP) with $H_{+}$-matrices, has been further considered. The main aim of this paper is to present an improved convergence condition of the MMS iteration method, to enlarge the range of its applications, in a way which is better than previous work [15].