# A Fast Algorithm for Solving a Class of the Linear Complementarity Problem in a Finite Number of Steps

Authors: Yamna Achik; Asmaa Idmbarek; Hajar Nafia; Imane Agmour; Youssef El foutayeni
Journal: Abstract and Applied Analysis
 (2020)

---

## Abstract

The linear complementarity problem is receiving a lot of attention and has been studied extensively. Recently, El foutayeni et al. have contributed many works that aim to solve this mysterious problem. However, many results exist and give good approximations of the linear complementarity problem solutions. The major drawback of many existing methods resides in the fact that, for large systems, they require a large number of operations during each iteration; also, they consume large amounts of memory and computation time. This is the reason which drives us to create an algorithm with a finite number of steps to solve this kind of problem with a reduced number of iterations compared to existing methods. In addition, we consider a new class of matrices called the E-matrix.


---

## Body

## 1. Introduction

In the last decades, the complementarity problem has played a very important role in several domains. It has been the focus of many researchers and scientists. As an example, we can cite the works of Cottle [1, 2] published between 1964 and 1966. Note that the above problem appears in older works without reporting the name of complementarity problems. In particular, we mention the work of Du Val [3] and Ingleton [4]. Let f be a function defined in ℝn to ℝn. A complementarity problem (CP) associated with the function f consists to find a vector z∈ℝn such as z≥0,fz≥0, and zTfz=0. If the function f is affine, it is presented in form fz=Mz+q, where q is a vector of ℝn and M is a square matrix of order n. Then, we have a linear complementarity problem denoted by LCPM,q. The origin of the name complementarity comes from the fact that if z∈ℝ+n is a solution of a linear complementarity problem, then zi=0 or fiz=0 for all i=1,2,⋯,n. The linear complementarity problem has been widely studied by researchers from a variety of backgrounds, which has been a rich and varied literature (see [5–17] and references therein). In [18], Kadiri and Yassine described a new purification method for solving monotonic linear complementarity problems. In their paper, the proposed method is associated with each iterate of the sequence, generated by an interior point method, one basis that is not necessarily feasible. The authors proved that, under the strict complementarity and nondegeneracy hypotheses, the sequence of bases converges on a definite number of iterations to an optimal basis which gives the exact solution to the problem. In [19], to solve the linear complementarity problem, Alves and Judice [19] proposed a pivoting heuristic based on tabu search and its integration into an enumerative framework. Recently, El foutayeni et al. [20–28] added a contribution to the resolution of the linear complementarity problem. In particular, in [27], they proved the equivalent between solving a linear complementarity problem and solving a nonlinear equation. Also, they give a globally convergent hybrid algorithm which is based on vector divisions for solving the linear complementarity problem. In [27], the same authors determined the conditions that allow a linear complementarity problem to have a solution. They calculated the solution when it exists. In [24], they proposed to solve the linear complementarity problem in the case where it has several solutions. The aim of [29] is to propose an iterative method of interior points that converge in the polynomial time to the best solution of the linear complementarity problem; this convergence requires at most on0,5L 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 on3,5L arithmetic operations until its convergence. In [24], El foutayeni and Khaladi have shown that the linear complementarity problem LCPM,q is completely equivalent to finding the fixed point of the map x=max0,I−Mx−q, and they showed that to find an approximation of the solution to the second problem, they proposed an algorithm that starts from an arbitrary interval vector X0, then they generalize a sequence of the interval vector Xkk=1,⋯ that converges to the best solution of linear complementarity problems. Newly, in [30], for solving the linear complementarity problem, Wang et al. [31] propose an interior point method to find the solution of the linear complementarity problem, where the matrix is a real square hidden Z-matrix. In this context, we can see the works [31–39].It is well known that it is impossible to ensure the existence of a linear complementarity problem solution associated with any matrix and vector. This leads us to ask the following questions: Under which conditions on the matrix and the vector does this type of problem admit a solution, and if it exists, what are the conditions for the uniqueness of this solution? Once the existence and uniqueness are assured, how we can express this solution according to the data of the problem? Despite the great importance of the linear complementarity problems in several areas, they are not yet completely resolved. However, many results exist and give good approximations of the solutions, but the main disadvantage of many existing methods resides in the fact that, for large systems, they require a large number of operations during each iteration and they consume large amounts of memory and computation time. This is the reason that drives us to look for new methods that deal with this kind of problem which lower the number of operations at each iteration compared to existing methods.In the present work, we formulate an algorithm that can solve the linear complementarity problemLCPM,q. This algorithm has a finite number of steps and converges to the solution. Also, we consider a new class of matrices called the E-matrix. The algorithm has been surprisingly effective. A numerical implementation of the algorithm is given in this work.We organized this document as follows. In Section1, we give preliminary definitions and we list some initial notations that we need throughout this document. In Section 2, we present the proposed linear complementarity problem under some conditions. In Section 3, we formulate an algorithm for solving our linear complementarity problem with the E class’s matrix. And in Section 4, we give numerical examples to confirm the theoretical part of our algorithm.


## 2. Preliminary and Notations

In this section, we recall preliminary definitions and general notations used in this paper.For any positive integern, let ℝn×n be the ensemble of all real n×n matrices. We denote by I the matrix of identity, ek is the kth column of I, and e=1,⋯,1T is a vector where all entries equal to 1. We also use the following notation Ck· and C·k to represent the kth row and the kth column of the C matrix, respectively; Yn=y/∣y∣=e is the ensemble of all ±1 vectors of ℝn, and its cardinality is equal to 2n. For each x∈Rn, we define his sign vector sgnx by sgnxi=1 if xi≥0 and sgnxi=−1 if xi<0 with i∈1,2,⋯,n. Then, sgnx∈Yn. For each z∈ℝn, we denote Tz=diagz1,⋯,zn.Definition 1.
GivenM∈ℝn×n, the set of matrices(1)A=S∈ℝn×n:S−M+I≤I+M=M−M,2I+M+M,
is called an interval matrix.Definition 2.
A square interval matrixAis called regular if eachS∈Ais regular and singular if it existsS∈Asingular.Proposition 3.
An interval matrixAis singular if and only if the inequality(2)M+Ix≤I+Mx,has a nontrivial solution.Proof.
We suppose thatA contains a singular matrix S, then there exist x≠0 such that Sx=0, which implies that M+Ix=M+Ix−Sx≤I+Mx. Conversely, let (2) hold for x≠0. Define y∈ℝn and z∈Yn by yi=I+Mxi/I+∣M∣∣x∣i, for i=1,⋯,n. If I+∣M∣∣x∣i>0 or yi=1 and I+∣M∣∣x∣i=0 taking into account that z=sgnx, then Tzx=x. Hence, I+M−TyI+∣M∣Tzxi=I+Mxi−yiI+∣M∣∣x∣i=0 for each i.Therefore,I+M−TyI+∣M∣Tz is singular, and since yi≤1 for each i due to 1, it follows that I+M−TyI+MTz−I+M=TyI+MTz≤I+∣M∣.Hence,I+M−TyI+∣M∣Tz∈A and A is singular.We use the previous proposition to show the regularity or the singularity of the matrixA in some cases.Proposition 4.
LetAbe regular and let(3)I+M+I−MTz′x′=I+M+I−MTz″x″,hold for somez′,z″∈Ynandx′≠x″.So, there exists anisatisfyingzi′zi′′=−1andxi′xi′′>0.Proof.
We assume that for eachi,zi′zi′′=−1 implies xi′xi′′≤0, so ∣xi′−xi′′∣=∣xi′∣+∣xi′′∣. We shall prove in this case that
(4)Tz′x′−Tz″x″≤x′−x″,
i.e., the inequalityzi′xi′−zi′′xi′′≤∣xi′−xi′′∣ holds for each i.Sincezi′xi′−zi′′xi′′=zi′xi′−zi′zi′′xi′′=xi′−zi′zi′′xi′′, this is clear fact for zi′zi′′=−1. If zi′zi′′=−1, so zi′xi′−zi′′xi′′=xi′+xi′′≤∣xi′∣+∣xi′′∣=∣xi′−xi′′∣ which together proves (3).Now, from (3), we have I+Mx′−x″=I−MTz′x′−Tz″x″≤I+Mx′−x″, by (4), with x′−x″≠0, then A is singular following the first proposition, and this is a contradiction.We use the Sherman-Morrison formula to prove the efficiency of the proposed algorithm.LetA∈ℝn×n be nonsingular matrix, b,c∈ℝn×n, and let α=1+cTA−1b.So, we havedetA+bcT=αdetA, if α=0, then A+bcT is singular, and if α≠0, we deduce that A+bcT−1=A−1−1/αA−1bcTA−1 (see [40]).


## 3. Main Results

It is a known fact (see El foutayeni and Khaladi [27]) that the linear complementarity problem LCPq,M is completely equivalent to solving the equation I+Mx+I−M∣x∣=q, where z=∣x∣−x and w=∣x∣+x. To present the algorithm, we define a new class of matrices that we call the class of E-matrices.Definition 5.
LetM∈ℝn×n. The matrixMis called theE-matrix if all the principal minors ofMare nonzero and if all the eigenvalues ofMare different from−1.Notation 6.
We denoteEthe set ofE-matrices(5)E=M∈Mn/MP≠0andλi≠−1,∀i∈1,2,⋯,n,such that MP is the set of the principal minors ofMandλiis the eigenvalues ofM.Lemma 7.
We have the equivalence between the following four properties of a matrixA:
(1)
All the principal minors of matrixAare positive(2)
For each vectorx≠0,there existsisuch thatxiyi>0,withy=Ax(3)
For each vectorx≠0,there exists a diagonal matrixDx≥0such thatAx,Dxx>0(4)
The real eigenvalues associated withAand every principal minor ofAare positiveProof.
1⇒2. We denote by N the set of indices 1,2,3⋯,n. We select an arbitrary vector x≠0, and we assume that xiyi≤0, for each i∈N, with y=Ax. Let Γ=i/xi≠0. Clearly Γ≠0. If AΓ is the main submatrix with rows and columns of Γ, xΓ is the vector wherein coordinates have indices of Γ and coincide with those of x; hence, for i∈Γ, the coordinates zi of the vector z=AΓxΓ coincide with yi. So, there exists a diagonal matrix U≥0 (over Γ×Γ) such as z=−UxΓ, i.e., AΓ+UxΓ=0. Therefore, the matrix AΓ+U is singular. Note that the principal minors of AΓ are positive. So, we have the same result for AΓ+U since U is diagonal positive. This is a contradiction that proves the implication. 2⇒3. We suppose that x≠0 is a vector, y=Ax, and i is the index for which xiyi>0. There exists a positive number η, such as xiyi+η∑j≠ixjyj is positive. To prove this, it is sufficient to choose Dx as the diagonal matrix, where dii=1 and djj=η, for j≠i.3⇒4. Let 0≠Γ⊂N and let λ be a real eigenvalue of AΓ with the eigenvector xΓ. We denote by x the vector with the coordinates xi that coincide with those of xΓ for i∈Γ. In accordance with (4), there exists a diagonal matrix Dx≥0 such that Ax,Dxx>0. But evidently, Ax,Dxx=λx,Dxx, since x,Dxx>0. Then, we have λ>0.4⇒1. Now, using the fact that the determinant of a matrix A is equal to the product of all eigenvalues of A and that the product of the nonreal eigenvalues of a real matrix is positive, we can easily complete the proof.Lemma 8.
Any matrixP-matrix is anE-matrix.Proof.
LetM be a P-matrix. Then, all principal minors of M are positive. From the previous Lemma, we can deduce that all real eigenvalues of M are positive sinceMis anE-matrix.It is easy to check that the identity matrix is anE-matrix; every symmetric positive definite matrix is an E-matrix and any Hilbert matrix is an E-matrix (we recall that a Hilbert matrix is a square matrix of general terms hij=1/i+j−1).Theorem 9.
For all matrixM∈E‐matricesand vectorq∈ℝn, the following algorithm “SolveLCP” has a finite number of steps and converges to the solution of the linear complementarity problemLCPM,qif it exists.Algorithm 1.
An algorithm for solving the linear complementarity problemLCPM,qfunctionz∗=SolveLCPM,qp=0∈ℝnz=sgnI+M−1qx=I+M+I−MTz−1qC=−I+M+I−MTz−1I−Mwhilezixi<0 for some ij=mini/zixi<0if1+2zjCjj≤0x=;display(no solution)returnendpj=pj+1if log2pj>n−jx=;display(no solution)returnendif1+2zjCjj>0Tz=Tz−2zjejejT;zj=−zj;α=2zj/1−2zjCjj;x=x+αxjC·j;C=C+αC·jCj·;endendz∗=∣x∣−x;endThe linear complementarity problemLCPM,q implies
(6)I+Mx+I−Mx=q.According to a change of variables,z=∣x∣−x and w=∣x∣+x. Hence, if we consider Tz=diagz with z=sgnx, then the equation (4) becomes
(7)I+M+I−MTzx=q.The problem is that we do not know the values of eitherx or z, but we know that they must satisfy Tzx=x≥0, i.e., zixi≥0 for each i.Step 1.
The algorithm beginning with the vectorp=0 and during each pass of the loop “while” it increases by 1; hence pk becomes pk+1 which means that after a finite number of steps, pk will become superior to 2n−k and the algorithm will end.Step 2.
The initial point isz=sgnI+M−1q; it is achievable since I+M is a regular matrix; indeed, we have M∈E‐matrices, so all the principal minors of M are nonzero, and for all λ eigenvalues of M, λ≠−1. Then, there exists v∈ℝn such that Mv=λv. Therefore, I+Mv=1+λv; hence, 1+λ is an eigenvalue of I+M.Step 3.
x=I+M+I−MTz−1q is also feasible, since the matrix H=I+M+I−MTz is regular. We have H=Hij1≤i,j≤n where
(8)Hij=1+mii+zi1−mii,ifi=j,mij−mijzj,ifi≠j.Consequently,Hij=2ej if zj>0 or Hij=2mij if zj<0; M is regular because M∈E‐matrices. Therefore, all the column vectors of M are linearly independent, so H is regular.Step 4.
Whenx and z are held, we calculate xz; we have two casesCase 1.
xizi>0, for all i∈1,⋯,n, then Tzx≥0 implies that Tzx=∣x∣ and such x=I+M+I−MTz−1q, we find I+Mx+I−M∣x∣=I+M+I−MTzx=q. So, x solves the equation (4) and z=∣x∣−x is the solution of the linear complementarity problem LCPM,q.Case 2.
xizi<0, we assume the existence of j such as j=mini:xizi<0 and we updated the matrix Tz and z. So, we bring back zj to −zj, and the Tz matrix will be modified. Then, for all real t,Tz~=Tz−2tzjejejT.The matrixH will change to the matrix H~ defined by H~=H−2tzjI−MejejT.Now checking the regularity of the matrixH~. We have, according to the formula of Sherman-Morrison, detH~=1−2tzjejTH−1I−MejdetH.We considerC=−H−1I−M, then detH~=1+2tzjCjjdetH. Therefore, we have two possible cases
(a)
If1+2zjCjj≤0, we have Cjj≠0 and the function φ:ℝ⟶ℝdefined by φt=1+2tzjCjj satisfies φ0φ1=1+2zjCjj≤0. Then, according to the Theorem of Intermediate Values, there exist t0∈0,1 such as φt0=0, so t0=−1/2zjjCjj and thus detH−2t0zjI−MejejT=0; hence, in this case, the matrixH~is singular and the solution does not exist(b)
If1+2zjCjj>0, we have the matrix I+M+I−MTz¯=H−2zjI−MejejT which is regular for t=1, then according to Sherman-Morrison’s formula(9)I+M+I−MTz¯−1=H−1+H−12zjI−MejejTH−11+2zjCjj=H−1+αC·jejTH−1.We obtain(10)α=−2zj1+2zjCjj,x¯=H−1q+αC·jejTH−1q=x+αxjC·j,C¯=−H−1I−M−αC·jejTH−1I−M=C+αCj·C·j.Therefore, we conclude that the matrixC plays an important role for giving an explicit calculation of x=I+M+I−MTz−1q at each step.Step 5.
Let us show that iflog2pj>n−j, then the matrix A is singular and the solution x does not exist. This will be proven by showing that if A is regular so pj≤2n−j for each j. So, we can demonstrate that every j can appear at most 2n−j times j=n,⋯,1; we have two casesCase 1.
j=n: we suppose that n appears at least twice in the sequence and that x′,z′ and x",z" correspond to the two closest occurrences, that is to say, that there is no other occurrence of n between them. So, xi′zi′≥0 and xizi≥0 for i=1,⋯,n−1, and xn′zn′<0,xn"zn"<0,zn′zn"=−1, which implies that xn′zn′xn"zn">0 and xn′xn"<0. Then, xi′zi′xizi≥0 for all i=1,⋯,n−1. But since
(11)I+M+I−MTzx′=q=I+M+I−MTzx",we obtain the relation (11) using the fact that x=I+M+I−MTz−1q and x′≠x" since xn′xn"<0; it follows from Proposition 4 that there is an i where zi′zi"=−1 and xi′xi">0, which implies that xi′zi′xi"zi"<0, which is a contradiction, so n occurs at most once in the sequence.Case 2.
j<n: let z′,x′ and z",x" correspond to two occurrences of j, so that zi′xi′≥0,zixi≥0 for i=1,⋯,j−1,zj′xj′<0,zj"xj"<0 and zj′zj"=−1. This gives that xi′zi′xizi≥0 for i=1,⋯,j−1,xj′zj′xj"zj">0 and xj′xj"<0. Then, as the condition (11) holds because of x=I+M+I−MTz−1q and x′≠x" since xn′xn"<0, then Proposition 4 implies the existence of an i where zi′zi"=−1 and xi′xi">0, as well as xi′zi′xi"zi"<0 so that i>j. So as zi′zi"=−1,i should have entered the sequence of j; there is an occurrence of some i>j in the sequence; this means, by the assumptions, that j cannot appear there more than 2n−j−1+⋯+2+1+1=2n−j times.


## 4. Numerical Examples

In this section, we demonstrate the effectiveness of our proposed algorithm in relation to the execution time and the number of iterations. To do this, we made comparisons between our algorithm and other existing methods. In the first, we give a simple example of a matrixE-matrix of order 4, for which we find the solution in a short time. In the second example, we compare the results obtained by our method with those obtained by the method of El foutayeni et al., the method of Yu, and the method of Chen-Harker-Kanzow-Smale (CHKS), and in the third example, we compare the execution time of our method with the method of Lemke and the method of the interior point.Example 10.
Considering the next linear complementarity problem, where we search to determine a vectorz in ℝ4 such that z≥0,w=Mz+q≥0 and zTw=0, with
(12)M=4203−14−3−61−1110105,q=−12−1−1.It is easy to prove that the associated matrixM is an E-matrix, by applying the proposed algorithm. Then, we obtain z=0,1,2,0T and the elapsed time is 0.000547 seconds.Example 11.
In this example, we compare the results obtained with our method to those obtained with the method of El foutayeni, the method given by Yu, and the method of Chen-Harker-Kanzow-Smale (CHKS). For attending this, we adopt our MATLAB program to calculate the optimal solutionz, the final values w=Mz+q, the number of iterations, and the time in seconds. Considering the following linear complementarity problem LCPM,q, where M=mij1≤i,j≤n such as mii=4 for i=j,mi,i+1=mi+1,i=−1 for all i=1,⋯,n, and it equals to 0 otherwise, and q=qi1≤i≤n such as qi=−1.Tables1–4 present the summaries of the results obtained, where Iter represents the iteration numbers when the algorithm ends and Time indicates the total cost in seconds to resolve the problem.Table 1
Numeric outcomes of our method.
z∗w∗IterTime (s)n=4(0.3636, 0.4545, 0.4545, 0.3636)(0, 0, 0, 0)10.0040n=8(0.3660, 0.4641, 0.4902, 0.4967, 0.4967, 0.4902, 0.4641, 0.3660)(0, 0, 0, 0 0, 0, 0, 0)10.0050Table 2
Numeric outcomes of the El foutayeni method.
z∗w∗IterTime (s)n=4(0.363636, 0.454545, 0.454545, 0.363636)(0, 0, 0, 0)20.000000n=8(0.366013, 0.464052, 0.490196, 0.496732, 0.496732, 0.490196, 0.464052, 0.366013)(0, 0, 0, 2.220446E−16, 2.220446E−16, 4.440892E−16, 0, −1.110223E−16)20.031200Table 3
Numeric outcomes of the Yu method.
z∗w∗IterTime (s)n=4(0.363636, 0.454545, 0.454545, 0.363636)(0, 0, −1.11022E−16, 0)50.031n=8(0.366013, 0.464052, 0.490196, 0.496732, 0.496732, 0.490196, 0.464052, 0.366013)(−1.11022E−16, 0, 0, 0, 0, −1.11022E−16, 0, 0)50.016Table 4
Numeric outcomes of the CHKS method.
z∗w∗IterTime (s)n=4(0.363636, 0.454545, 0.454545, 0.363636)(−6.72751E−12, −5.38214E−12, −5.38214E−12, −6.72751E−12)50.016n=8(0.366013, 0.464052, 0.490196, 0.496732, 0.496732, 0.490196, 0.464052, 0.366013)(−6.68399E−12, −5.27156E−12, −4.9909E−12, −4.92495E−12, −4.92495E−12, −4.9909E−12, −5.27178E−12, −6.68399E−12)50.031From Figures1 and 2, we can notice that our method can be comparable with the method of El foutayeni, the method of Yu, and the method of CHKS, from the iteration numbers and CPU computation time in seconds.Example 12.
In this example, we compare three different methods in order to solve a linear complementarity problemCPM,q. The first one is our method, the second one is Lemke’s method, and the last one is the interior point method [30]. We take the same example, where M=mij1≤i,j≤nsuch asmii=4,mi,i+1=mi+1,i=−1for alli=1,⋯,nand zero in the rest andq=qi1≤i≤nsuch asqi=−1.The matrixMis definitely positive, so we ensure the convergence of Lemke’s method. In Table 5, the first column represents the dimension of the linear complementarity problem. The second provides (the third and the fourth) the computation time in seconds for Lemke’s method to be performed (interior point algorithm and our algorithm).Figure 1
Comparison between our method with the method of El foutayeni, the method of Yu, and the method of CHKS as a function of time and number of iterations in the case wheren=4.Figure 2
Comparison between our method with the method of El foutayeni, the method of Yu, and the method of CHKS as a function of time and number of iterations in the case wheren=8.Table 5
The execution time for the different methods.
nLemkeInterior pointProposed algorithm105230.00447208340.0051605014560.014906100321480.030162200742890.041484001265180.1108115001596650.17719010003348750.928443Based on this table, in the case wheren=1000, we conclude that Lemke’s method is divergently compared to time (it needs 334 seconds to display the results), but our method only needs 0.928443 seconds to find the solution of LCPM,q. The same is said for the point interior method. We noticed that our algorithm is faster than the other algorithms compared to the execution time. Then, we can deduce that the performance of our method is effective.


## 5. Conclusion

Solving a linear LCP complementarity problem has been the goal of much research. Thus, in this article, we have proposed an algorithm allowing us to solve the LCP linear complementarity problem. This algorithm has a finite number of steps and converges to the solution. In addition, we have considered a new class of matrices called theE-matrix such that the algorithm is efficient. In perspective, we seek to find a simple method to solve linear complementarity problems with any matrix M and vector q without treating the cases on the matrix M, so that it is fast in execution time and in the number of iterations. A digital implementation of the algorithm is given in this work.



---

*Source: 8881915-2020-12-30.xml*