# An Efficient Class of Modulus-Based Matrix Splitting Methods for Nonlinear Complementarity Problems

Authors: Shui-Lian Xie; Hong-Ru Xu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

In this paper, we present an efficient method for finding a numerical solution for nonlinear complementarity problems (NCPs). We first reformulate an NCP as an equivalent system of fixed-point equations and then present a modulus-based matrix splitting iteration method. We prove the convergence of the proposed method with theorems with the relevant conditions. Our preliminary numerical results show that the method is feasible and effective.


---

## Body

## 1. Introduction

In this paper, we consider the following nonlinear complementarity problem with a nonlinear source term, namely, finding au∈Rn such that(1)u≥0,v=Fu≥0,uTv=0,where the function Fu has the form of Au+Φu+q, A=aij∈Rn×n is a given large, sparse, and real matrix, q is a given vector, Φ:Rn⟶Rn is a given diagonal differentiable mapping, that is, the ith component Φi of Φ is a function of the ith variable ui only(2)Φi=Φiui,i=1,2,…,n.Clearly, ifΦ is a linear function, problem (1) reduces to a linear complementarity problem (LCP).Nonlinear complementarity problem (NCP) has many applications in nonlinear compressed sensing, signal processing, communications, DNA microarrays, and so on [1–7]. For example, the nonlinear compressed sensing theory has been widely applied in asteroseimology for significant detection. The polynomial structure has been employed in many applications cases, such as quadratic measurements in sparse signal recovery and nonlinear compressed sensing with polynomial measurements. In this regard, under some constraint qualifications, the original problem turns out to finding the sparsest solutions to a special NCP. NCP can also be derived from discrete simulations of the Bratu obstacle problem and free boundary problems with nonlinear source terms. This problem has received much attention during the past two decades and has been studied extensively with applicable numerical methods to obtain an approximated solution. There are different kinds of numerical methods that have been developed, including the classical linearized projected relaxation method [8], multilevel method [9], domain decomposition method [10, 11], penalty method [12–14], and semismooth Newton method [15]. Most of those methods need to solve the linear complementarity subproblems; see [16–19] for several typical iteration methods.It is well known that the matrix splitting method is a very important and effective method for computing systems of linear equations. Many authors have extended this kind of method for LCP. Bai [20] presented a unified framework for the construction of modulus-based matrix splitting iteration methods. Since then, many scholars have developed various kinds of modulus-based matrix splitting iteration methods; see, for example, [21–23] for LCP and [24, 25] for NCP. Recently, Wu and Li [26] proposed a class of new modulus-based matrix splitting methods for LCP. This kind of method is different from previously published works. The new modulus-based matrix splitting iteration methods provide a new general framework for solving the LCP. Numerical experiments show that the new modulus-based matrix splitting iteration method for LCP is feasible and competitive when compared with other well-known modulus-based matrix splitting iteration methods. Motivated by the ongoing work in this field, in this paper, we extend the new modulus-based matrix splitting method for a kind of NCP and establish its convergence through theorems.The remainder of this paper is structured as follows. In Section2, we present some relevant preliminary information and the modulus-based matrix splitting iteration method. We establish the convergence theorems of the method under suitable conditions in Section 3. In Section 4, we present numerical results to show the efficiency of the proposed method.


## 2. Modulus-Based Matrix Splitting Iteration Method

We briefly introduce some definitions and lemmas that will be used in the paper. Most of them can be found in [20, 25, 27, 28].Given two matricesA=aij, B=bij∈Rn×n, we call A≥BA>B if aij≥bijaij>bij holds for all 1≤i≤n, 1≤j≤n. If aij≥0 for all 1≤i≤n, 1≤j≤n, A is called a nonnegative matrix, denoted by A≥O. A denotes the nonnegative matrix with entries aij.LetA be a real n×n matrix. Its comparison matrix A=aij∈Rn×n, where(3)aij=aij,i=j−aijx,i≠ji,j=1,2,…,n.The matrixA is called a Z−matrix if its off-diagonal entries are all nonpositive; A is called an M−matrix if A is a Z−matrix and A−1≥O; A is called an H−matrix if its comparison matrix A is an M−matrix; A is called an H+−matrix if it is an H−matrix with positive diagonal entries; if A is an M−matrix, Ω is a positive diagonal matrix, and then A≤B≤Ω implies that B is an M− matrix. We use ρA to represent the spectral radius of the square matrix A∈Rn×n.GivenA=M−N, if M is a nonsingular matrix, then A=M−N is called a splitting of the matrix A; for the splitting A=M−N, if M−N is an M−matrix, the splitting is called a H−splitting.Lemma 1 (see [27]).
LetA=aij∈Rn×n with aij≥0. If there exists u∈Rn with u>0 such that Au<u, then ρA<1.Lemma 2 (see [28]).
LetA∈Rn×n be an M−matrix and B∈Rn×n be a Z− matrix with A≤B. Then, B is an M−matrix.Lemma 3 (see [28]).
LetA∈Rn×n be an H−matrix, D^ be the diagonal part of the matrix A, and A=D^−B. Then, matrices A and D^ are nonsingular, A−1≤A−1 and ρ|D^|−1|B|<1.Lemma 4 (see [26]).
LetA=M−N be an H−splitting of the matrix A, where A is an H+−matrix. Then, M−N≤D^−B, where D^=diagA and A=D^−B.To obtain a new equivalence system of fixed-point equations of the NCP, we need the following lemma:Lemma 5 (see [26]).
Leta,b∈R. Then,(4)a≥0,b≥0,ab=0,if and only if(5)a+b=a−b.This result carries immediately over to the vectors inRn.Based on Lemma5, we have the following theorem:Theorem 1.
LetΩ be a positive diagonal matrix. Then, NCP (1.1) is equal to(6)Ω+Au=A−Ωu+Φu+q−q−Φu.Proof.
Obviously, NCP (1.1) is equal to(7)v=Au+Φu+q≥0,Ωu≥0,ΩuTv=0,where Ω is a positive diagonal matrix. Here, we take a=Au+Φu+q and b=Ωu for Lemma 5 and get(8)Ω+Au=A−Ωu+Φu+q−q−Φu.
The proof is completed.
We takeA=M−N as a matrix splitting of matrix A∈Rn×n; then, from (6), we have(9)Ω+Mu=Nu+A−Ωu+Φu+q−q−Φu.
This new equivalent expression (9) is different from the one in the previous work in [24, 25]. These methods have similarities but they do not belong to each other. Based on (9), we can present the following modulus-based matrix splitting iteration method for solving (1).Method 1 (modulus-based matrix splitting iteration method).
LetA=M−N be a splitting of the matrix A∈Rn×n and M+Ω be a nonsingular matrix, where Ω is a positive diagonal matrix. Given an initial vector u0∈Rn, for k=0,1,2,⋯ until the iteration sequence ukk=0∞⊂Rn is convergent, compute uk+1∈Rn by(10)Ω+Muk+1=Nuk+A−Ωuk+Φuk+q−q−Φuk.
Method1 provides a general framework of the modulus-based matrix splitting iteration method for solving the NCP. Based on the matrix splitting technique, some new modulus-based relaxation methods are obtained. For example, we express matrix A as(11)A=D^−L−U,where D^=diagA and −L and −U are the strictly lower and upper triangular matrices of A, respectively. Then,(i)
WhenM=A, Ω=I, N=0, from Method 1, we have(12)I+Auk+1=A−Iuk+Φuk+q−q−Φuk,which is called a modulus iteration (MI) method.(ii)
WhenM=1/αD^−βL, N=1/α1−αD^+α−βL+αU, from Method 1, we have(13)αΩ+D^−βLuk+1=1−αD^+α−βL+αUuk+αA−Ωuk+Φuk+q−q−Φuk,which is called the modulus-based AOR (MAOR) iteration method. Clearly, the MAOR method becomes the new modulus-based successive overrelaxation, Gauss–Seidel, and Jacobi method whenα,β is equal to α,α, (1, 1), and (1, 0), respectively.


## 3. Convergence Theory

In this section, we discuss the convergence of Method1 under suitable conditions.Theorem 2.
LetΩ be an n×n positive diagonal matrix, A=M−N be a splitting of a matrix A∈Rn×n, with M+Ω being a nonsingular matrix. Suppose that there exist positive constants di such that di≥dΦiui/dui≥0, i=1,2,…,n, for all u∈Rn. Let D be a diagonal matrix, and the diagonal elements are di, i=1,2,…,n. Let(14)T=Ω+M−1N+A−Ω+2D.IfρT<1, then the iteration sequence ukk=0+∞⊂Rn generated by Method 1 converges to the solution u⋆ of NCP (1.1).Proof.
Letu⋆ be the solution for the NCP (1.1). Then, from (6), we obtain(15)Ω+Mu⋆=Nu⋆+A−Ωu⋆+Φu⋆+q−q−Φu⋆.
Based on (10) and (15), noting that Ω+M is nonsingular, we have(16)uk+1−u⋆=M+Ω−1Nuk−u⋆+Φu⋆−Φuk+A−Ωuk+Φuk+q−A−Ωu⋆+Φu⋆+q.
This indicates that(17)uk+1−u⋆=M+Ω−1Nuk−u⋆+Φu⋆−Φuk+A−Ωuk+Φuk+q−A−Ωu⋆+Φu⋆+q≤M+Ω−1Nuk−u⋆+M+Ω−1⋅Φu⋆−Φuk+M+Ω−1⋅A−Ωuk+Φuk+q−A−Ωu⋆+Φu⋆+q≤M+Ω−1N⋅uk−u⋆+M+Ω−1Duk−u⋆+M+Ω−1A−Ω+Duk−u⋆=M+Ω−1N+A−Ω+2Duk−u⋆.
It is clear that whenρT<1, the iteration sequence ukk=0+∞⊂Rn generated by Method 1 converges to the solution u⋆ of NCP (1.1). This completes the proof.
Similar to the proof of Theorem2, using ⋅2 for (3.2), we have the following theorem.Theorem 3.
LetΩ be an n×n positive diagonal matrix, let A=M−N be a splitting of a matrix A∈Rn×n, with M+Ω being a nonsingular matrix. Suppose that there exist positive constants di such that di≥dΦiui/dui≥0, i=1,2,…,n, for all u∈Rn. Let D be a diagonal matrix, and the diagonal elements are di, i=1,2,…,n. Let(18)T^=Ω+M−12N2+A−Ω2+2D2.IfρT^<1, then the iteration sequence ukk=0+∞⊂Rn generated by Method 1 converges to the solution u⋆ of the NCP (1.1).Theorem 4.
LetA=M−N be an H− splitting of the matrix A, where A is an H+−matrix. Let the diagonal matrix Ω≥D^, where D^=diagA. Suppose there exist positive constants di such that di≥dΦiui/dui≥0, i=1,2,…,n, for all u∈Rn. Let D be a diagonal matrix, and the diagonal elements are di, i=1,2,…,n. Let T=Ω+M−1N+A−Ω+2D. If M−N−D is an M−matrix, then the iteration sequence ukk=0+∞⊂Rn generated by Method 1 converges to the solution u⋆ of the NCP (1.1).Proof.
SinceA=M−N is an H−splitting and(19)M−N≤M.
MatrixM is an M−matrix from Lemma Method 2. Noting that Ω≥D^, by Lemma 3, we can see Ω+M is an H+−matrix and(20)M+Ω−1≤M+Ω−1.
Moreover, we have(21)T≤M+Ω−1N+A−Ω+2D=M+Ω−1M+Ω−M−Ω+N+A−Ω+2D≤M+Ω−1M+Ω−M−Ω+N+D^−Ω+B+2D=I−M+Ω−1M+Ω−M−Ω−D^−Ω−B−2D=I−M+Ω−1M−N+D^−B−2D≤I−2M+Ω−1M−N−D,where the last inequality holds by Lemma 4. Since M−N−D is an M−matrix, there exists a positive vector u such that(22)M−N−Du>0.
Hence,(23)Tu≤I−2M+Ω−1M−N−Du<u.
We haveρT<1 by Lemma 1, and the iteration sequence ukk=0+∞⊂Rn generated by Method 1 converges to the solution of NCP (1.1). This completes the proof.


## 4. Numerical Experiments

In this section, we test the effectiveness of the proposed method on two problems. We implemented our methods in MATLAB and ran the code on a PC with a 3.4 GHz CPU and 8GB RAM. We tested the proposed method in Section2 and compared their performance with Method 4.1 proposed in [24].Method 2.
LetA=M−N be a splitting of the matrix A∈Rn×n, Ω be an n×n nonnegative diagonal matrix, and h be a positive number. Given x0∈Rn, for k=0,1,2,⋯, compute xk+1∈Rn by solving the linear system:(24)Ω+Mxk+1=Nxk+Ω−Axk−2hq+Φh2xk+xkand set(25)uk+1=h2xk+1+xk+1.
The iteration terminates when the sequencexkk=0∞⊂Rn is convergent.
In all the experiments, we chose the sameΩ and h in Method 2 as in [24], that is, Ω=I and h=1.
We considered the following two problems:Problem 1.
Consider (1.1), letFu=Au+Φu+q, where(26)A=H−I−IH⋱⋱⋱−I−IHwithH=4−1−14⋱⋱⋱−1−14,A is an n×n matrix, H and I are t×t matrices with n=t2, Φiui=ui/1+ui and a diagonal mapping Φu=Φiui and q=1−1,1,−1,…T.Problem 2.
Consider (1.1), letFu=Au+Φu+q, where(27)A=H−0.5I−1.5IH⋱⋱⋱−0.5I−1.5IHwithH=4−0.5−1.54⋱⋱⋱−0.5−1.54,A is an n×n matrix, H and I are t×t matrices with n=t2, and Φiui=arc tanui and a diagonal mapping Φu=Φiui, and q=1,−1,1,−1,…T.
For the above problems, the initial points of all the methods were set tou0=1,0,1,0,…T. Define Res ≔minuk,Fuk2 and the stopping criterion for all the methods are set to Res <10−6. We can obtain many matrix splitting iteration methods from Methods 1 and 2 using different splittings of A. In our experiments, we consider two splittings of matrix A=M−N:(i)
LetM=A,N=0 and denote the method corresponding to Method 1 as NMI and the method corresponding to Method 2 as MI, respectively.(ii)
LetM=1/aD^−L and N=1/α−1D^+U, where D^,−L,−U are the diagonal, the strictly lower triangle, and the strictly upper triangle of the matrix A, respectively, and α is a relaxation parameter. Denote the methods corresponding to Method 1 as NMSORα and Method 2 as MSORα, respectively.
We first test the effect of the choice of matrixΩ in Method 1 on Problem 1. We let Ω=I,2I,3I,4I,5I and fix the dimension of the problem n=400. The results are listed in Tables 1 and 2. The column of the table has the following meaning.
Table1 is the numerical result for NMI, and Table 2 is the numerical result for NMSORα with fixed α=0.6. As we can see from the tables, Ω has a great influence on the behaviour of the proposed method. In the following experiments, we fix Ω=4I. We compared our Method 1 with Method 2 proposed in [24]. The results are listed in Tables 3–6. “—” means the method failed to find the solution. From the tables, we can see that our method outperforms the method proposed in [24] regardless of the number of iterations or the CPU elapsed time. In these two examples, NMI seems to be competitive with NMSOR with the best parameters. In addition, as we can see from Tables 4 and 6, methods NMI and NMSOR may be independent of the dimensions.Table 1
Numerical results of NMI for Problem1 with different Ω.
Ω=IΩ=2IΩ=3IΩ=4IΩ=5ICPU3.2541.1280.8020.5220.644Iter8729211317Res8.8 485e−77.1 188e−75.6 296e−79.7 839e−74.8 359e−7Table 2
Numerical results of NMSOR for Problem1 with different Ω.
Ω=IΩ=2IΩ=3IΩ=4IΩ=5ICPU1.8120.9130.8040.7790.965Iter5025222126Res8.8 387e−79.0 549e−78.2 116e−76.6 182e−79.1 418e−7Table 3
Numerical results for Problem1 using Method 2.
nMIMSOR0.2MSOR0.4MSOR0.6MSOR0.8MSOR1.0100CPU0.10.1210.0540.0360.0560.37Iter86121604164447Res9.7 893e−79.5 296e−78.8 894e−79.3 262e−79.5 452e−79.6 319e−7400CPU3.354.7782.3191.6163.029—Iter87127624381—Res8.9 383e−79.9 707e−79.0 364e−77.7 447e−78.7 010e−7—900CPU34.02250.73224.37516.62334.383—Iter87131634389—Res9.3 875e−79.5 828e−79.4 402e−79.5 916e−78.6 957e−7—1600CPU188.867288.017136.85194.189192.049—Iter87134644490—Res9.8 162e−79.123e−79.1 586e−78.382e−78.8 297e−7—Table 4
Numerical results for Problem1 using Method 1.
nNMINMSOR0.2NMSOR0.4NMSOR0.6NMSOR0.8NMSOR1.0NMSOR1.2NMSOR1.4100CPU0.0270.0740.0270.0170.0120.0140.0170.021Iter1364312015162026Res4.2 714e−79.3 221e−77.4 581e−75.5 552e−73.3 274e−73.5 144e−78.1 510e−75.387e−7400CPU0.4942.5221.1950.7670.5780.5760.7880.943Iter1369332116162126Res9.7 839e−78.2 406e−78.7 411e−76.6 182e−73.2 473e−75.2 506e−75.832e−79.8 892e−7900CPU5.74726.62812.6438.1895.9565.9527.82410.072Iter1571342216162127Res2.0 204e−78.2 307e−78.4 129e−74.0 343e−74.6 232e−76.3 577e−76.9 295e−76.3 989e−71600CPU30.761145.85470.69244.51732.51632.53742.45654.465Iter1572352216162127Res2.6 947e−78.9 048e−76.624e−75.7 269e−75.7 292e−77.2 981e−77.8 753e−77.2 316e−7Table 5
Numerical results for Problem2 using Method 2.
nMIMSOR0.2MSOR0.4MSOR0.6MSOR0.8MSOR1.0100CPU0.6850.1290.0550.0380.058—Iter700121634467—Res9.8 494e−79.2 832e−78.5 078e−78.9 841e−78.9 822e−7—400CPU29.4964.7352.4241.6822.538—Iter699126654568—Res9.9 211e−79.5 234e−78.3 278e−79.6 855e−79.4 709e−7—900CPU275.01450.97626.22518.2526.826—Iter699129664668—Res9.9 235e−79.6 376e−78.47e−79.0 547e−79.4 944e−7—1600CPU1516.268279.358140.491100.07145.021—Iter699131664768—Res9.9 258e−79.895e−79.793e−79.9 849e−79.5 129e−7—Table 6
Numerical results for Problem2 using Method 1.
nNMINMSOR0.2NMSOR0.4NMSOR0.6NMSOR0.8NMSOR1.0NMSOR1.2NMSOR1.4100CPU0.0120.0560.0210.0140.0130.0120.0170.021Iter1552251612141924Res4.1 947e−79.3 799e−79.2 101e−78.1 471e−79.399e−77.3 949e−76.1 808e−79.2 176e−7400CPU0.5952.02109420.6120.4690.5420.6840.9Iter1555261713151925Res9.384e−79.0 552e−79.849e−76.0 963e−75.9 889e−74.7 898e−77.7 494e−76.3 067e−7900CPU6.41522.2710.6816.7285.1475.9137.5229.904Iter1656271713151925Res2.1 765e−79.86e−77.0 764e−78.6 029e−78.7 608e−76.264e−78.22 794e−76.9 569e−71600CPU34.508115.09854.53436.32728.29130.26138.41750.468Iter1657271814151925Res3.7 312e−79.2 141e−78.9 017e−73.6 077e−74.843e−77.4 934e−79.7 891e−77.5 518e−7


## 5. Conclusions

In this paper, we have presented an efficient class of modulus-based matrix splitting methods for NCPs, which are based on an implicit system of fixed-point equations. A number of sufficient conditions to guarantee the convergence of the novel iteration method are presented. The proposed method is easy to implement, and in each iteration, there is no need to solve the nonlinear equations or linear complementarity subproblems; hence, the calculation cost is small. The comparisons of the numerical results show the computational efficiency of the proposed method. There are still many studies that need to be done. For example, we can investigate the two-step modulus-based matrix splitting method, that is, in each iteration, the method implements a forward sweep followed by a backward sweep. We can expect the two-step method to achieve a higher computing efficiency. Moreover, we can apply this new method to other complementarity problems, such as the implicit complementarity problems, and discuss its convergence (Table5).



---

*Source: 9030547-2021-12-28.xml*