A note on the unique solution of linear complementarity problem

Abstract

In this note, the unique solution of the linear complementarity problem (LCP) is further discussed. Using the absolute value equations, some new results are obtained to guarantee the unique solution of the LCP for any real vector.

Keywords:

• linear complementarity problem
• the system matrix
• unique solution
• absolute value equations

AMS Subject Classifications:

• 90C05
• 90C30

Public Interest Statement

The linear complementarity problem (LCP) consists in finding a vector in a finite-dimensional real vector space that satisfies a certain system of inequalities. Now, the LCP attracts considerable attention because it comes from many actual applications, such as the linear and quadratic programming.

As is known, the research of the unique solution is important for the LCP. The famous result on its unique solution is that the system matrix is a P-matrix if and only if the LCP has a unique solution for any real vector. This result is answered what kind of the system matrix for the LCP has a unique solution for any real vector.

The goal of this paper is to answer this problem what conditions are required for the system matrix such that the LCP for any real vector has a unique solution. Based on this motivation, some conditions are obtained to guarantee the unique solution of the LCP for any real vector.

1. Introduction

The linear complementarity problem, abbreviated as (LCP(q, M)), is finding $z\in {\mathbb{R}}^n$ such that(1) $$\begin{array}{c}\hfill w=Mz+q\ge 0,z\ge 0\text{and}{z}^{T}w=0,\end{array}$$(1)

where $M\in {\mathbb{R}}^{n\times n}$ is a given matrix and $q\in {\mathbb{R}}^n$ is a given vector. At present, the LCP(q, M) attracts considerable attention because it comes from many actual problems of scientific computing and engineering applications, such as the linear and quadratic programming, the economies with institutional restrictions upon prices, the optimal stopping in Markov chain and the free boundary problems. For more detailed descriptions, one can refer to Cottle and Dantzig (1968), Cottle, Pang, and Stone (1992), Murty (1988), Schäfer (2004) and the references therein.

In recent years, the main research contents about the LCP(q, M) include two aspects: one is to develop numerical methods for solving the system of the linear equations to obtain the solution of the LCP(q, M), such as the projected successive overrelaxation (SOR) iteration methods (Cryer, 1971), the general fixed-point iteration methods (Mangasarian, 1977; Pang, 1984), the modulus-based matrix splitting iteration methods (Bai, 2010) and its various versions (Dong & Jiang, 2009; Hadjidimos, Lapidakis, & Tzoumas, 2012; Li, 2013; Xu & Liu, 2014; Zhang, 2011; Zheng & Yin, 2013), and so on; the other is theoretical analysis, such as the existence and multiplicity of solutions of the LCP(q, M) in Cottle et al. (1992) and Ebiefung (2007), verification for existence of solutions of the LCP(q, M) in Chen, Shogenji, and Yamasaki (2001), and so on.

The research of the unique solution is a very important branch of theoretical analysis of the LCP(q, M) because the goal of the above-quoted numerical methods is to obtain the unique solution of the LCP(q, M). With respect to the unique solution of the LCP(q, M), the classical and famous result is that the system matrix M is a P-matrix if and only if the LCP(q, M) has a unique solution for any real vector in Cottle et al. (1992) and Schäfer (2004). This result is answered what kind of the system matrix for the LCP(q, M) has a unique solution for any real vector. Since P-matrices contain positive definite matrices and H-matrices with positive diagonal (Bai, 2010; Schäfer, 2004), the LCP(q, M) has a unique solution for any real vector with the system matrix being a positive definite matrix or an H-matrix with positive diagonal.

In this note, we further consider the unique solution of the LCP(q, M). Our interest is what conditions are required for the system matrix such that the LCP(q, M) for any real vector has a unique solution. To answer this problem, based on the previous works in Mangasaria and Meyer (2006), Rohn (2009a,2009b), Wu and Guo (2016), Lotfi and Veiseh (2013), Rex and Rohn (1999), some new conditions are obtained to guarantee the unique solution of the LCP(q, M) for any real vector.

This paper is organized as follows. Some necessary definitions and lemmas are reviewed in Section 2. In Section 3, some new conditions are obtained to guarantee the unique solution of the LCP(q, M) for any real vector. In Section 4, some conclusions are given to end the paper.

2. Preliminaries

In this section, some necessary definitions and lemmas are required. Matrix $A\in {\mathbb{R}}^{n\times n}$ is called a P-matrix if all its principal minors are positive. Matrix $A\in {\mathbb{R}}^{n\times n}$ is said to be positive definite if $x^{T}Ax>0$ for all $x\in {\mathbb{R}}^n\backslash \{0\}$. Matrix A is positive stable if the real part of each eigenvalue of A is positive. Matrix $A\in {\mathbb{R}}^{n\times n}$ is called a Z-matrix if its off-diagonal entries are non-positive; an M-matrix if A is a Z-matrix and $A^{-1}\ge 0$; an H-matrix if its comparison matrix $⟨A⟩=({⟨a⟩}_{ij})\in {\mathbb{R}}^{n\times n}$ is an M-matrix, where$$\begin{array}{c}\hfill {⟨a⟩}_{ij}=\left\{\begin{array}{cc}|a_{ii}|,\hfill & \text{for}i=j,\hfill \\ -|a_{ij}|,\hfill & \text{for}i\ne j,\hfill \end{array}\right.i,j=1,2,\dots ,n.\end{array}$$

An H-matrix with positive diagonal is called an $H_{+}$-matrix. $P_{+}$ denotes the positive stable matrix. $|·|$ denotes the absolute value. $\mathit{\rho }(·)$ denotes the spectral radius of the matrix. ${\mathit{\sigma }}_{min}(·)$ and ${\mathit{\sigma }}_{max}(·)$, respectively, denote the smallest and the largest singular values of the matrix, ${\Vert ·\Vert }_2$ denotes the matrix 2-norm.

To obtain some new conditions to guarantee the unique solution of the LCP(q, M) for any real vector, the absolute value equation (AVE) is reviewed, i.e.(2) $$\begin{array}{c}\hfill Ax-|x|=b,\end{array}$$(2)

where $A\in {\mathbb{R}}^{n\times n}$ is a given matrix and $b\in {\mathbb{R}}^n$ is a given vector.

Based on the previous works in Mangasaria and Meyer (2006), Rohn (2009a), the following result, i.e. Lemma 2.1, for the unique solution of the AVE (2) for any real vector was presented in Wu and Guo (2016).

Lemma 2.1

(Wu & Guo, 2016)    Let ${\mathit{\sigma }}_{min}(A)>1({\mathit{\sigma }}_{max}(A^{-1})<1)$, or $\mathit{\rho }(|A^{-1}|)<1$, or $\Vert A^{-1}{\Vert }_2<1$. Then the AVE (2) for any vector $b\in {\mathbb{R}}^n$ has a unique solution.

In Rohn (2009a), a general form of the AVE (2) was introduced below(3) $$\begin{array}{c}\hfill Ax+B|x|=b,\end{array}$$(3)

where $A,B\in {\mathbb{R}}^{n\times n}$ and $b\in {\mathbb{R}}^n$. With respect to the unique solution of the general AVE (3) for any real vector, the following result was obtained in Rohn (2009a).

Lemma 2.2

(Rohn, 2009a)    Let $A,B\in {\mathbb{R}}^{n\times n}$ satisfy(4) $$\begin{array}{c}\hfill {\mathit{\sigma }}_{max}(|B|)<{\mathit{\sigma }}_{min}(A).\end{array}$$(4)

Then the AVE (3) for any vector $b\in {\mathbb{R}}^n$ has a unique solution.

Lemma 2.3

(Rohn, 2009b)    If the interval matrix $[A-|B|,A+|B|]$ is regular, then the AVE (3) for any vector $b\in {\mathbb{R}}^n$ has a unique solution.

Lemma 2.4

(Lotfi & Veiseh, 2013)    Let $A,B\in {\mathbb{R}}^{n\times n}$ and the matrix$$\begin{array}{c}\hfill A^{T}A-{\Vert |B|\Vert }_2^{2}I\end{array}$$

is positive definite. Then the AVE (3) for any vector $b\in {\mathbb{R}}^n$ has a unique solution.

Lemma 2.5

(Rex & Rohn, 1999)    Let $\mathrm{\Delta }\ge 0$ and R be an arbitrary matrix such that$$\begin{array}{c}\hfill \mathit{\rho }(|I-RA|+|R|\mathrm{\Delta })<1\end{array}$$

holds. Then $[A-\mathrm{\Delta },A+\mathrm{\Delta }]$ is regular.

3. Main results

In fact, if we take $z=|x|+x$ and $w=|x|-x$ in (1), then the LCP(q, M) in (1) can be equivalently transformed into a system of fixed-point equations(5) $$\begin{array}{c}\hfill (I+M)x=(I-M)|x|-q.\end{array}$$(5)

This implies that the unique solution of the LCP(q, M) in (1) is the same as the AVE in (5).

Assume that matrix $I-M$ is nonsingular. Then the AVE (5) can be rewritten in the following form(6) $$\begin{array}{c}\hfill {(I-M)}^{-1}(I+M)x=|x|-{(I-M)}^{-1}q.\end{array}$$(6)

Using Lemma 2.1 for the AVE in (6), the following result is easily obtained.

Theorem 3.1

Let $I+M,I-M\in {\mathbb{R}}^{n\times n}$ satisfy either of the following conditions:

(1)	${\mathit{\sigma }}_{min}({(I-M)}^{-1}(I+M))>1$, or ${\mathit{\sigma }}_{max}({(I+M)}^{-1}(I-M))<1$,
(2)	$\mathit{\rho }(|{(I+M)}^{-1}(I-M)|)<1$,
(3)	${\Vert (I+M)}^{-1}{(I-M)\Vert }_2<1$.

Then the LCP(q, M) in (1) for any vector $q\in {\mathbb{R}}^n$ has a unique solution.

Example 3.1

(Ahn, 1983)    Let$$\begin{array}{c}\hfill M={\left[\begin{array}{ccccc}4& -2& 0& \cdots & 0\\ 1& 4& -2& \cdots & 0\\ ⋮& \ddots & \ddots & \ddots & ⋮\\ 0& 0& 0& \cdots & 4\end{array}\right]}_{n\times n}.\end{array}$$

To show the efficiency of Theorem 3.1, we take $n=10$ in Example 3.1. By simple computations, we obtain ${\mathit{\sigma }}_{max}({(I+M)}^{-1}(I-M))={0.7225,\mathit{\rho }(|(I+M)}^{-1}{(I-M)|)=0.8809,\Vert (I+M)}^{-1}{(I-M)\Vert }_2=0.7225$. Based on Theorem 3.1, when the system matrix of LCP(q, M) is matrix M in Example 3.1, the LCP(q, M) has a unique solution for any vector $q\in {\mathbb{R}}^n$.

Using the result of Lemma 2.2 for the AVE in (5) directly, the following result for the unique solution of the LCP(q, M) in (1) for any real vector is obtained.

Theorem 3.2

Let $I+M,I-M\in {\mathbb{R}}^{n\times n}$ satisfy(7) $$\begin{array}{c}\hfill {\mathit{\sigma }}_{max}(|I-M|)<{\mathit{\sigma }}_{min}(I+M).\end{array}$$(7)

Then the LCP(q, M) in (1) for any vector $q\in {\mathbb{R}}^n$ has a unique solution.

Example 3.2

Let$$\begin{array}{c}\hfill M={\left[\begin{array}{ccccc}4& -1& 0& \cdots & 0\\ 1& 4& -1& \cdots & 0\\ ⋮& \ddots & \ddots & \ddots & ⋮\\ 0& 0& 0& \cdots & 4\end{array}\right]}_{n\times n}.\end{array}$$

Here, we take $n=20$ for Example 3.2. By simple computations, we obtain ${\mathit{\sigma }}_{min}(I+M)=5.0022,{\mathit{\sigma }}_{max}(|I-M|)=4.9777$. Clearly, ${\mathit{\sigma }}_{max}(|I-M|)<{\mathit{\sigma }}_{min}(I+M)$. Based on Theorem 3.2, the corresponding LCP(q, M) has a unique solution for any vector $q\in {\mathbb{R}}^n$. This implies that one can use Theorems 3.2 to confirm the unique solution of LCP(q, M) under certain conditions.

Although the results of Theorems 3.1 and 3.2 can be directly obtained by Lemma 2.1 and 2.2, respectively, the conditions of Theorems 3.1 and 3.2 to guarantee the unique solution of the LCP(q, M) for any real vector need confirm that the system matrix M satisfies certain inequalities, need not know whether the system matrix M is a special matrix, such as the positive definite matrix, an $H_{+}$-matrix in Schäfer (2004), and so on.

Remark 3.1

If we take $z=\mathrm{\Gamma }(|x|+x)$ and $w=\mathrm{\Omega }(|x|-x)$, then the LCP(q, M) in (1) can be also equivalently transformed into a system of fixed-point equations$$\begin{array}{c}\hfill (\mathrm{\Omega }+M\mathrm{\Gamma })x=(\mathrm{\Omega }-M\mathrm{\Gamma })|x|-q,\end{array}$$

where $\mathrm{\Omega }$ and $\mathrm{\Gamma }$ are the positive diagonal matrices (see Bai, 2010). In this case, Theorems 3.1 and 3.2 can be generalized. Here is omitted.

Remark 3.2

Although the positive definite matrix and $H_{+}$-matrix not only belong to a class of $P_{+}$-matrices, but also belong to a class of P-matrices, the system matrix $M\in {\mathbb{R}}^{n\times n}$ is only positive stable, we can not obtain that the LCP(q, M) in (1) for any vector $q\in {\mathbb{R}}^n$ has a unique solution. For example,$$\begin{array}{c}\hfill \overline{A}=\left[\begin{array}{cc}4& 2\\ -6& -2\end{array}\right].\end{array}$$

By simple computations, $det(-2)=-2$, the eigenvalue values of matrix $\overline{A}$ are $1\pm \sqrt{3}i$. This shows that the matrix $\overline{A}$ is a $P_{+}$-matrix, is not a P-matrix. Whereas,$$\begin{array}{c}\hfill {\Vert (I+M)}^{-1}{(I-M)\Vert }_2=2.2507,\end{array}$$

This shows that $\overline{A}$ does not meet the criteria of Theorem 3.1.

Based on Lemma 2.5, we have the following result.

Theorem 3.3

If there exists a matrix R such that$$\begin{array}{c}\hfill \mathit{\rho }(|I-R(I+M)|+|R||I-M|)<1,\end{array}$$

Then the LCP(q, M) in (1) for any vector $q\in {\mathbb{R}}^n$ has a unique solution.

Proof

Based on Lemma 2.5, we know that when$$\begin{array}{c}\hfill \mathit{\rho }(|I-R(I+M)|+|R||I-M|)<1,\end{array}$$

then the interval matrix $[M+I-|I-M|,M+I+|I-M|]$ is regular. Based on Lemma 2.3, the result in Theorem 3.3 holds.

Corollary 3.1

If the interval matrix $[M+I-|I-M|,M+I+|I-M|]$ is regular, then the LCP(q, M) in (1) for any vector $q\in {\mathbb{R}}^n$ has a unique solution.

Remark 3.3

From Theorem 3.3, it is easy to know that one can choose a proper matrix to obtain some useful conditions to guarantee the unique solution of LCP(q, M) in (1) for any vector $q\in {\mathbb{R}}^n$. For example, if we take $R={(I+M)}^{-1}$ and M is a M-matrix, then$$\begin{array}{c}\hfill \mathit{\rho }(|I-R(I+M)|+|R||(I-M)|)<1.\end{array}$$

Noting that $R\ge 0$, this inequality reduces to$$\begin{array}{c}\hfill \mathit{\rho }(|{(I+M)}^{-1}(I-M)|)<1,\end{array}$$

which is case (2) of Theorem 3.1.

Based on Theorem 3.3, when $R=\frac{1}{2}I$, we have the following corollary.

Corollary 3.2

Let $M\in {\mathbb{R}}^{n\times n}$ satisfy $\mathit{\rho }(|I-M|)<1$.

Then the LCP(q, M) in (1) for any vector $q\in {\mathbb{R}}^n$ has a unique solution.

Example 3.3

(Murty, 1988)    Let$$\begin{array}{c}\hfill M={\left[\begin{array}{ccccc}1& 2& 2& \cdots & 2\\ 0& 1& 2& \cdots & 2\\ ⋮& \ddots & \ddots & \ddots & ⋮\\ 0& 0& 0& \cdots & 1\end{array}\right]}_{n\times n},q=-e,\end{array}$$

where $e\in {\mathbb{R}}^n$ denote the column vector whose elements are all 1.

Based on Corollary 2, we confirm that the corresponding LCP(q, M) has a unique solution for any vector $q\in {\mathbb{R}}^n$. It is because that $\mathit{\rho }(|I-M|)=0<1$ for Example 3.3.

In addition, based on Lemma 2.4, we have the following result below.

Theorem 3.4

Let ${(I+M)}^T(I+M)-\Vert |I-{M|\Vert }_2^{2}I$ be positive definite. Then the LCP(q, M) in (1) for any vector $q\in {\mathbb{R}}^n$ has a unique solution.

Example 3.4

To confirm the efficiency of Theorem 3.4, Example 3.1 is still considered. For simplicity, we take $n=30$. By simple computations, the smallest eigenvalue of ${(I+M)}^T(I+M)-\Vert |I-{M|\Vert }_2^{2}I$ is 10.1366. This shows that matrix ${(I+M)}^T(I+M)-\Vert |I-{M|\Vert }_2^{2}I$ is positive definite. Based on Theorem 3.4, Example 3.1 has still a unique solution for any vector $q\in {\mathbb{R}}^n$.

As previously mentioned, the system matrix M is a P-matrix if and only if the LCP(q, M) has a unique solution for any real vector. Based on Theorems 3.1–3.4, we have the following corollary.

Corollary 3.3

If matrix $M\in {\mathbb{R}}^{n\times n}$ satisfies the conditions of Theorems 3.1–3.4, then $M\in {\mathbb{R}}^{n\times n}$ is a P-matrix.

4. Conclusion

In this paper, based on the implicit fixed-point equations of the LCP, some new and useful results are obtained to guarantee the unique solution of the LCP in the light of the spectral radius, or the singular value, or the matrix norm of the system matrix.

Additional information

Funding

This research was supported by NSFC [grant number 11301009], Natural Science Foundations of Henan Province [grant number 15A110007], and the Humanities and Social Science Project of Ministry of Education of China [grant number 14YJC910001].

Notes on contributors

Shi-Liang Wu

Shi-Liang Wu has obtained the PhD in applied mathematics from University of Electronic Science and Technology of China. Currently, he is an associate professor in Mathematics and Statistics Department, Anyang Normal University, Anyang, China. His main research interests include Matrix analysis and its application, Numerical methods for differential-algebraic equations, Numerical partial differential equations and Numerical analysis for linear systems and (non-)linear complementarity problem.