# Uniqueness of the Minimall1-Norm Solution to the Monotone Linear Complementarity Problem

Authors: Ting Zhang; Xiaoqin Jiang
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

The linear complementarity problem (LCP) has wide applications in economic equilibrium, operations research, and so on, which attracted a lot of interest of experts. Finding the sparsest solution to the LCP has real applications in the field of portfolio selection and bimatrix game. Motivated by the approach developed in compressive sensing, we may try to solve anl1-minimization problem to obtain the sparsest solution to the LCP, where an important theoretical problem is to investigate uniqueness of the solution to the concerned l1-minimization problem. In this paper, we investigate the problem of finding the minimal l1-norm solution to the monotone LCP and propose a sufficient and necessary condition for the uniqueness of the minimal l1-norm solution to the monotone LCP, which provides an important theoretical basis for finding the sparsest solution to the monotone LCP via solving the corresponding l1-minimization problem. Furthermore, several examples are given to confirm our theoretical finding.


---

## Body

## 1. Introduction

The linear complementarity problem (LCP) can be described as follows; we want to find a vectorx∈Rn such that(1)Ax+b≥0,x≥0,x⊤Ax+b=0,where A∈Rn×n and b∈Rn are given. If A is positive semidefinite, then problem (1) is called a monotone LCP. Instances of the LCP can date back to 1940, but it became a scientific direction of study until the mid-1960s. This class of problems has many applications in economics and engineering [1–4]. In this paper, we denote (1) by the LCP(b,A) and the solution set of the LCP(b,A) by SOL(b,A).Compressive sensing (CS) has attracted plenty of attention in the fields of signal processing and machine learning [5, 6]. The basic model of CS can be described as the problem of seeking the sparsest solution under linear equality constraints; that is,(2)minx0s.t.Qx=q,where Q∈Rm×n(m≪n), q∈Rn, and x0 denotes the number of nonzero components of the vector x∈Rn. Since (2) is known to be an NP-hard problem, a tractable approximation is the commonly considered l1-minimization problem:(3)minx1s.t.Qx=q,where x1 is the l1-norm of x, that is, the sum of each component’s absolute value.Problem (3) is a convex program which can be reformulated as a linear program [7]. In most cases, l1-minimization problem can find the sparsest solution to the underdetermined linear system effectively from a lot of empirical results. Recently, the theoretical results with respect to the equivalence of l1-minimization problem and l0-minimization problem have made significant progress and led to a sharp increase of research in CS [8–10]. In detail, the mutual-coherence-based analysis [11], the null space property (NSP) [12], the restricted isometry property (RIP) [10], and the range space property (RSP) [13] can guarantee the equivalence of problems (2) and (3), where uniqueness of problem (3) plays an important role in the theoretical analysis.Problem (2) is to find the sparest solution to the system of equalities. However, only the equalities may be not enough for practical problems sometimes. As the deepening of the research, the nonnegative sparsest solution to the underdetermined linear system of equations has attracted people’s interesting, and some theoretical results have been obtained, such as the RIP [14], the NSP [15], and the RSP [16]. Furthermore, Zhang et al. [17] proposed the conditions to guarantee the equivalence between the l0-norm solution to the system of absolute value equations and its l1-norm solution, where a key is to characterize uniqueness of the solution to the corresponding l1-minimization problem.Seeking the minimall0-norm solution of the LCP has many applications in real world, such as portfolio selection [18] and bimatrix game [1]. Chen and Xiang [19] investigated the characterization and computation of sparse solutions and least-p-norm (p∈(0,1)) solutions to the LCP and provided some conditions on the involved matrix such that a sparse solution can be found by solving a convex minimization problem. Shang et al. [20] studied minimal l0-norm solutions of the LCP. They investigated the approximation of the concerned problem by using p-norm (p∈(0,1)) and proposed a sequential smoothing gradient method to solve it.It is well-known that the existence and uniqueness of the solution to theLCP(b,A) play an important role in theory and algorithms for solving the LCP(b,A) [1–3]. Motivated by the researches mentioned above, in this paper, we consider the following l1-minimization problem:(4)minx1s.t.Ax+b≥0,x≥0,x⊤Ax+b=0,where A∈Rn×n is positive semidefinite and b∈Rn. It is a relaxation of the problem to find the sparsest solution to the LCP:(5)minx0,s.t.Ax+b≥0,x≥0,x⊤Ax+b=0.We will propose a sufficient and necessary condition to guarantee uniqueness of the solution to problem (4), which provides an important theoretical basis in studying the equivalence between problems (4) and (5) so that the sparest solution to the monotone LCP (1) can be found by solving problem (4).This paper is organized as follows. Some basic concepts and results for the LCP are stated in Section2. In Section 3, we investigate the necessary conditions for uniqueness of the solution to problem (4) if it has at least a solution. In Section 4, we propose a sufficient and necessary condition for uniqueness of the minimal l1-norm solution to the monotone LCP. In Section 5, we give two specific examples to confirm the theoretical result. Conclusions and further work are arrived at the last section.Now, we outline the notations that will be used in this paper. We denote[n]≔{1,2,…,n} throughout this paper. For any matrix M∈Rm×n, index sets I⊆[m] and J⊆[n], MI∈R|I|×n denotes the submatrix of matrix M with rows in I, MJ∈Rm×|J| denotes the submatrix of M with columns in J, and MI×J∈R|I|×|J| is the submatrix with rows in I and columns in J, where I(J) denotes the number of the elements in I(J). For any vector x∈Rn and an index set I⊆[n], xI∈R|I| denotes the vector with components of x in set I. For the vector x∗∈Rn with x∗≥0, we define index sets I+ and I0 by I+≔{i∈[n]∣xi∗>0} and I0≔{i∈[n]∣xi∗=0}, respectively. e∈Rn denotes the vector whose components are all one. For simplicity, we denote (x⊤,y⊤)⊤ as (x,y) for any vectors x,y∈Rn.


## 2. Preliminaries

For theLCP(b,A) (1), the following results are significant in our sequential analysis.Theorem 1 (Cottle et al. [1]).
LetA∈Rn×n be positive semidefinite and b∈Rn. Then, (a)
if theLCP(b,A) (1) is feasible, that is, there exists a vector x¯∈Rn such that x¯≥0 and Ax¯≥b hold, then the LCP(b,A) (1) is solvable; that is, SOL(b,A)≠∅;(b)
if theLCP(b,A) has a solution, then SOL(b,A) is polyhedral and (6)SOLb,A=x∈Rn∣x≥0,b+Ax≥0,b⊤x-x¯=0,A+A⊤x-x¯=0,wherex¯∈Rn is an arbitrary solution.Suppose thatA∈Rn×n is positive semidefinite and the LCP(b,A) has a solution, denoted by x¯∈Rn; then by using Theorem 1(b), we have (7)SOLb,A=x∣Ax+b≥0,x≥0,Ax=u,b⊤x=v, where u=Ax¯ and v=b⊤x¯.Thus, in order to investigate uniqueness of the sparsest solution to the monotoneLCP, we consider the following problem:(8)minx0s.t.Ax=c,b⊤x=d,Ax+b≥0,x≥0,where A∈Rn×n is positive semidefinite, b,c∈Rn, and d∈R. Since problem (8) is NP-hard, we consider its relaxed problem: (9)minx1s.t.Ax=c,b⊤x=d,Ax+b≥0,x≥0, which can be rewritten as follows:(10)minx1s.t.Ab⊤x=cd,Ax≥-b,x≥0.Suppose thatx∗ is an optimal point of problem (10). Then, for inequality constraint Ax≥-b, we denote the index set of the active constraints at point x∗ by I∗ and the index set of the inactive constraints by I^∗, which means(11)AI∗x∗=-bI∗,AI^∗x∗>-bI^∗.These notations will be used throughout this paper.At the end of this section, we recall a classical theory for linear programming (LP). Consider the LP(12)minc⊤xs.t.Mx=p,x≥0and its dual(13)maxp⊤ys.t.M⊤y+z=c,z≥0,where M is a given matrix and p and c are two given vectors. The following result is significant for our analysis.Theorem 2.
If the LP (12) and its dual (13) are both feasible, then there exists a pair of strictly complementary solutions (x∗,(y∗,z∗)) satisfying x∗+z∗>0.In the following, we will discuss some conditions for uniqueness of the solution to problem (10), which further leads to a sufficient and necessary conditions for uniqueness of the minimal l1-norm solution to the monotone LCP.


## 3. Necessary Conditions

In this section, we give two necessary conditions for uniqueness of the solution to problem (10) under the assumption that it has at least a solution.Suppose thatx∗ is an optimal point to problem (10); then problem (10) has a unique optimal solution if and only if (14)w∣Aw=c,b⊤w=d,Aw≥-b,w≥0,w1≤x∗1=x∗. Since x∗≥0 and w≥0, it follows that x∗1=e⊤x∗ and w1=e⊤w. Thus the above relationship can be written as (15)w∣Aw=Ax∗,b⊤w=b⊤x∗,Aw≥-b,w≥0,e⊤w≤e⊤x∗=x∗. So we have the following lemma.Lemma 3.
Suppose thatx∗ is an optimal point to problem (10); then problem (10) has a unique optimal solution if and only if (w,s,t)=(x∗,Ax∗+b,0) is the unique optimal point of the following problem:(16)min0⊤ws.t.Ab⊤w=Ab⊤x∗,-Aw+s=b,e⊤w+t=e⊤x∗,w,s,t≥0.The dual problem of problem (16) is given by(17)maxAb⊤x∗⊤y1+b⊤y2+e⊤x∗σs.t.A⊤by1+-A⊤y2+σe≤0,y2≤0,σ≤0.Furthermore, by introducing slack variables r1,r2,r, problem (17) can be converted to the following problem:(18)maxAb⊤x∗⊤y1+b⊤y2+e⊤x∗σs.t.A⊤by1+-A⊤y2+σe+r1=0,y2+r2=0,σ+r=0,r1,r2,r≥0.Based on problems (16) and (18), by using the dual theory of the LP, we will show the following result.Theorem 4.
Ifx∗ is the unique optimal point of problem (10) with I∗ being defined by (11), then there exist ζ∈R|I∗| and η∈Rn such that(19)AI∗⊤ζ+η∈RangeA⊤b,ζ<0,ηi=1,∀i∈I+,ηi<1,∀i∈I0.Proof.
Since problems (16) and (18) are both feasible, there exists a pair of strictly complementary solutions of (16) and (18) by Theorem 2. Denote the strictly complementary solution pair by (w,s,t) and (r1,r2,r)=(-[A⊤by1+(-A)⊤y2+σe],-y2,-σ). Then, we have (20)w⊤r1=0,s⊤r2=0,tr=0,w+r1>0,s+r2>0,t+r>0. Since x∗ is the unique optimal point of the problem (10), it follows from Lemma 3 that (w,s,t)=(x∗,Ax∗+b,0). Thus, wi>0 if i∈I+ and wi=0 if i∈I0 and t=0. These imply (21)r1i=0,ifi∈I+,>0,ifi∈I0,r>0. That is,(22)A⊤by1+-A⊤y2+σei=0,ifi∈I+,<0,ifi∈I0,σ<0.Furthermore, since s=Ax∗+b, it follows that (sI∗)i=0 if i∈I∗ and (sI^∗)i>0 if i∈I^∗, which imply that(23)y2i=0,ifi∈I^∗,<0,ifi∈I∗.
Substituting (23) into (22), we have (24)A⊤by1+-AI∗⊤y2I∗+σei=0,y2I∗<0wheni∈I+,A⊤by1+-AI∗⊤y2I∗+σei<0,y2I∗<0wheni∈I0. Let ζ=-(y2)I∗/σ; then ζ<0. So we have(25)A⊤by1-σ-AI∗⊤ζ-ei=0wheni∈I+,A⊤by1-σ-AI∗⊤ζ-ei<0wheni∈I0.
By settingη=A⊤by1/-σ+AI∗⊤(y2)I∗/σ, then we have (26)η+AI∗⊤ζ=A⊤by1-σ∈RangeA⊤b, and by (25), (27)η-ei=0ifi∈I+,η-ei<0ifi∈I0. These, together with ζ<0, imply the desired result.In this paper, condition (19) given in Theorem 4 is called the range space property (RSP).Now we establish the other necessary condition.Theorem 5.
Ifx∗ is the unique optimal point of problem (10) with I∗ being defined by (11), then(28)H=AI+bI+⊤AI∗×I+has column full rank.Proof.
Define(29)H^=AI+bI+⊤AI∗×I+eI+⊤;we first show that the matrix H^ has column full rank. Suppose that H^ does not have column full rank; then there must exist a nonzero vector ν such that H^ν=0. On the one hand, let (w,s,t) be given by w=wI+,wI0=xI+∗,0, s=Aw+b, and t=0; it is easy to see that (w,s,t) is an optimal point to problem (16). On the other hand, let (w¯,s¯,t¯) be given by w¯=w¯I+,w¯I0=wI++λν,0, s¯=Aw¯+b, and t¯=0. Since wI+=xI+∗>0, there must exist a small λ≠0 satisfying w¯I+=wI++λν≥0 and s¯=Aw¯+b≥0. Thus (w¯,s¯,t¯) is also an optimal point to problem (16). However, since w¯≠w, we obtain two different optimal points of problem (16), which contradicts Lemma 3. Thus, the matrix H^ defined by (29) has column full rank.
Sincex∗ is the unique optimal point of problem (10), it follows from Theorem 4 that condition (19) holds, which further implies that there exist θ and ζ such that (30)eI+⊤=θ⊤Ab⊤I+-ζ⊤AI∗×I+. Thus, we have rank(H)=rank(H^), which leads to the desired result.


## 4. Sufficient and Necessary Condition

In this section, we first discuss the sufficient and necessary condition for uniqueness of the solution to problem (10), which is given as follows.Theorem 6.
Suppose thatx∗ is an optimal point to problem (10) with I∗ being defined by (11). Then, x∗ is the unique optimal point of problem (10) if and only if the matrix H defined by (28) has column full rank and there exist ζ∈R|I∗| and η∈Rn such that RSP condition (19) holds.Proof.
By Theorems4 and 5, we only need to prove the sufficiency of Theorem 6. Suppose that there exist ζ∈R|I∗| and η∈Rn such that RSP condition (19) holds. Then, there exists θ such that η=(A⊤b)θ-AI∗⊤ζ. Since ηi=1 for any i∈I+ and ηi<1 for any i∈I0, by letting σ=-1, we have (31)A⊤bθ-AI∗⊤ζi+σ=0,ifi∈I+,A⊤bθ-AI∗⊤ζi+σ<0,ifi∈I0. Let (32)y1=θ,y2I∗=ζ,y2I^∗=0,σ=-1. Clearly, (y1,y2,σ) is a feasible point of problem (17); then we prove that (y1,y2,σ) is an optimal point of problem (17). In fact, the objective function value of problem (17) at (y1,y2,σ) can be calculated as follows: (33)Ab⊤x∗⊤y1+b⊤y2+e⊤x∗σ=x∗⊤A⊤by1+b⊤y2+e⊤x∗σ=∑i∈I+xi∗A⊤by1i+σ∑i∈I+xi∗+b⊤y2=∑i∈I+xi∗A⊤by1i+σ+b⊤y2=∑i∈I+xi∗AI∗⊤ζi+b⊤y2=xI+∗⊤AI+×I∗⊤ζ+b⊤y2=xI+∗⊤AI+×I∗⊤ζ+bI∗⊤ζ=AI∗×I+xI+∗+bI∗⊤ζ=0. By weak duality, the maximal value of the dual problem (17) is 0. Therefore, the point (y1,y2,β) is an optimal point to problem (17). Then the slack variables in (18) have the properties which are described in the following:(34)r1i=0,∀i∈I+,>0,∀i∈I0,r2i=0,∀i∈I^∗,>0,∀i∈I∗,r=1.Suppose that (w,s,t) is an arbitrary optimal point of problem (16), in order to prove the uniqueness of the optimal point x∗ for the problem (10); we just need to verify (w,s,t)=(x∗,Ax∗+b,0) by Lemma 3. Using Theorem 2, we have (35)w⊤-A⊤by1+A⊤y2-σe=0,s⊤-y2=0,t-σ=0,w+-A⊤by1+A⊤y2-σe>0,s+-y2>0,t+-σ>0. Using (34), we obtain that(36)wi=0,∀i∈I0;si=0,∀i∈I∗;t=0.According to the constraints of problem (16), we have(37)Ab⊤I+wI+=Ab⊤I+xI+∗,AI∗×I+wI+=AI∗×I+xI+∗.
Letd=(w-x∗)I+, then we have (38)Ab⊤I+d=0,AI∗×I+d=0, which mean Hd=0. Since H has column full rank, we have d=0; that is, wI+=xI+∗. Furthermore, we can obtain w=x∗ and s=Ax∗+b.By using Theorems1(a) and 6, it is easy to obtain the sufficient and necessary condition for uniqueness of the solution to the monotone LCP, which is given as follows.Theorem 7.
LetA∈Rn×n be positive semidefinite and b∈Rn. Suppose that there exists a vector x¯∈Rn such that x¯≥0 and Ax¯≥b hold; then SOL(b,A)≠∅. Furthermore, let x∗∈SOL(b,A) with I∗ being defined by (11); then x∗ is the unique optimal point of problem (4) if and only if the matrix H defined by (28) has column full rank, and there exist ζ∈R|I∗| and η∈Rn such that RSP condition (19) holds.


## 5. Examples

In this section, we give two examples to verify the obtained sufficient and necessary condition for uniqueness of the minimall1-norm solution to the monotone LCP.Example 8.
Consider theLCP(b,A), where (39)A=1-1-1021-101,b=-101.It is easy to find that(40)x∗=201 is the unique minimal l1-norm solution of the LCP(b,A). In the following, we show that all conditions in Theorem 7 hold for this problem.First, it is easy to see that the matrixA is positive semidefinite.Second, it is easy to obtain that(41)I+=1,3,I0=2,I∗=1,3,I^∗=2, and hence, the matrix H defined by (28) can be written as (42)H=1-101-11-111-1-11. Obviously, H has column full rank.Third, there exist(43)
ζ
=
-
1
-
1
,
η
=
1
1
2
1
,
θ
=
5
2
2
3
4
3
4
, such that AI∗⊤ζ+η=(A⊤b)θ∈Range(A⊤b), which shows that the RSP conditions (19) hold at x∗.Example 9.
Consider theLCP(b,A), where (44)A=1111,b=-1-1.It is easy to find that(45)
x
1
=
1
0
,
x
2
=
1
2
1
2 are two minimal l1-norm solutions of the LCP(b,A), so the minimal l1-norm solution is not unique. In the following, we show that some condition in Theorem 7 does not hold for this problem.If we takex∗≔x(1), then (46)I+=1,I0=2,I∗=1,2,I^∗=∅. In this case, we show that the RSP conditions (19) do not hold. In fact, if the RSP conditions hold at x(1), then we have η=1ϵ with ϵ<1. Denote ζ=(ζ1ζ2)⊤<0 and θ=(θ1θ2θ3)⊤; then from AI∗⊤ζ+η=(A⊤b)θ∈Range(A⊤b), we can obtain (47)1111ζ1ζ2+1ϵ=11-111-1θ1θ2θ3; that is, (48)ζ1+ζ2+1=θ1+θ2-θ3,ζ1+ζ2+ϵ=θ1+θ2-θ3, which is impossible. So the RSP conditions (19) do not hold in this case.If we takex∗≔x(2), then (49)I+=1,2,I0=∅,I∗=1,2,I^∗=∅. In this case, the matrix H defined by (28) is (50)H=1111-1-11111. Obviously, H does not have column full rank.


## 6. Conclusions

In this paper, we investigated the uniqueness of the minimall1-norm solution to the monotone LCP. By using an equivalence reformulation, we proposed a sufficient and necessary condition to guarantee uniqueness of the minimal l1-norm solution to the monotone LCP, which provide an important theoretical basis for finding the sparsest solution to the monotone LCP.Some issues are worth studying in our further research. It is meaningful to investigate various recovery conditions and design high-efficiency algorithms to seek the minimall1-norm solution to the monotone LCP. Moreover, since the nonconvex relaxation methods have been studied extensively in the last years (see, e.g., [19–23] and references therein), it is also worth investigating theory and algorithms for solving some nonconvex relaxation problems of finding the sparsest solution to the monotone LCP.



---

*Source: 7175385-2017-01-04.xml*