# Solvability of Two Classes of Tensor Complementarity Problems

Authors: Yang Xu; Weizhe Gu; He Huang
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

In this paper, we first introduce a class of tensors, called positive semidefinite plus tensors on a closed cone, and discuss its simple properties; and then, we focus on investigating properties of solution sets of two classes of tensor complementarity problems. We study the solvability of a generalized tensor complementarity problem with aD-strictly copositive tensor and a positive semidefinite plus tensor on a closed cone and show that the solution set of such a complementarity problem is bounded. Moreover, we prove that a related conic tensor complementarity problem is solvable if the involved tensor is positive semidefinite on a closed convex cone and is uniquely solvable if the involved tensor is strictly positive semidefinite on a closed convex cone. As an application, we also investigate a static traffic equilibrium problem which is reformulated as a concerned complementarity problem. A specific example is also given.


---

## Body

## 1. Introduction

Denote[n]≔{1,2,…,n} and Rn≔{x=(x1,x2,…,xn)⊤:xi∈R,i∈[n]} where R is the set of real numbers. For any set S⊆Rn, we use lin(S) to denote the linear space generated by S; and bd(S) and int(S) to denote the boundary and the interior of S, respectively. A set S⊆Rn is said to be convex if for any x,y∈S and any α∈[0,1], it follows that αx+(1-α)y∈S; and it is said to be a cone if for any λ≥0 and any x∈S, it follows that λx∈S. A cone S⊆Rn is closed convex if it is a closed and convex set. For any set S⊆Rn, we use S∗ to denote the dual cone of S, which is defined by(1)S∗=x∈Rn:x⊤y≥0foranyy∈S.Anmth order n-dimensional real tensor A=(ai1i2…im) is a multidimensional array with real entries, in which ij∈[n] for j∈[m]. We denote the set of all the mth order n-dimensional real tensors by Tm,n. For any A∈Tm,n and x∈Rn, an n-dimensional vector, denoted by Axm-1, is defined by(2)Axm-1i=∑i2,i3,…,im=1naii2i3…imxi2xi3⋯xim,∀i∈n.For any givenA∈Tm,n and q∈Rn, the tensor complementarity problem [1], denoted by the TCP(q, A), is to find an x∈Rn such that(3)x≥0,Axm-1+q≥0,x⊤Axm-1+q=0where x≥0 means xi≥0 for all i∈[n]. Obviously, the TCP(q, A) is a generalization of the linear complementarity problem [2]. Recall that, for any given closed convex cone K⊆Rn and mapping F:K→Rn, the conic complementarity problem [3], denoted by the CP(K, F), is to find a vector x∈Rn such that(4)x∈K,Fx∈K∗,x⊤Fx=0,where K∗ is the dual cone of K. It is obvious that the TCP(q, A) is a subclass of the CP(K, F).As a natural extension of the linear complementarity problem, the TCP(q, A) emerged from the tensor community in 2015 [1]. In recent several years, the TCP(q, A) has been a hot topic and many theoretical results have been obtained, including the nonemptiness and/or compactness of solution set [4–16], the existence of unique solution [7, 8, 14, 17–22], error bound theory [23–25], strict feasibility [22, 26], and so on. Several algorithms for solving the TCP(q, A) have also been proposed [27–31]. Recently, Wang, Hu, and Huang [14] investigated the quadratic complementarity problem, i.e., find an x∈Rn such that(5)x≥0,Ax2+Bx+q≥0,x⊤Ax2+Bx+q=0where A∈T3,n, B∈T2,n, and q∈Rn, which serves as an important bridge linking linear complementarity problems and nonlinear complementarity problems. They studied various properties on the solution set for a quadratic complementarity problem, including existence, compactness, and uniqueness.In this paper, we first introduce a class of structure tensors, called the positive semidefinite plus tensor, which is a generalization of the positive semidefinite plus matrix used in [14]; and we discuss its simple properties. Then, we investigate two classes of tensor complementarity problems, which contain the quadratic complementarity problem (5) as a special case. In particular, we study the solvability of these two problems and obtain some results which are generalizations of those given in [14]. These provide important theoretical basis for designing effective algorithms to solve these two classes of problems.It has been shown that a multiperson noncooperative game can be reformulated as a tensor complementarity problem, and that finding a Nash equilibrium point of the multiperson noncooperative game is equivalent to finding a solution of the resulting tensor complementarity problem [32]. It is well known that many engineering problems can be solved by solving some clustering problems. In the age of big data, hypergraph clustering has become a research hotspot. Recently, game-theoretic approaches for hypergraph clustering have been developed rapidly [33]. In terms of methods developed in [32], several problems of hypergraph clustering can be reformulated as tensor complementarity problems. These provide an impetus for further study of this class of problems. In order to further expand the scope of engineering application of this kind of problem, in this paper we investigate a static traffic equilibrium problem, which can be reformulated as a concerned complementarity problem. A specific example is also given.The remainder of the paper is organized as follows. In the next section, we introduce the positive semidefinite plus tensor and discuss its simple properties. In Section3, we discuss properties of solution sets of two classes of tensor complementarity problems. In Section 4, we reformulate a static traffic equilibrium problem as a concerned complementarity problem. Conclusions are given in the last section.Throughout this paper, for anyA∈Tm,n and x∈Rn, we will use the following notation: (6)Axm≔x⊤Axm-1=∑i1,i2,…,im=1nai1i2⋯imxi1xi2⋯xim.


## 2. A New Class of Tensors and Its Properties

The following tensors are defined similarly as those given in [34], which will be used in this paper.Definition 1.
LetK⊆Rn be a closed cone. A tensor A∈Tm,n is said to be (a)
positive semidefinite onK if Axm≥0 for all x∈K;(b)
positive definite onK if Axm>0 for all x∈K\{0};(c)
strictly positive semidefinite onK if (x-y)⊤(Axm-1-Aym-1)≥0 for all x,y∈K;(d)
strictly positive definite onK if (x-y)⊤(Axm-1-Aym-1)>0 for all x,y∈K with x≠y.Inspired by Definition  3.3 in [14], we introduce a new class of structured tensors as follows.Definition 2.
LetK⊆Rn be a closed cone. A∈Tm,n is said to be positive semidefinite plus on K if it is positive semidefinite on K, and whenever Axm=0 for x∈K, we have Axm-1=0.Recall that if there exist a scalarλ∈R and a nonzero vector x∈Rn which satisfy(7)Axm-1=λx1m-1,x2m-1,…,xnm-1⊤,then λ is called an H-eigenvalue of A with x being corresponding H-eigenvector; and that if there exist a scalar λ∈R and a nonzero vector x∈Rn which satisfy(8)Axm-1=λx,then λ is called a Z-eigenvalue of A with x being corresponding Z-eigenvector [35]. By these definitions and Definition 2, the following result is obvious.Proposition 3.
LetK⊆Rn be a closed cone. If A∈Tm,n is positive semidefinite plus on K, then for any x∈K\{0} satisfying Axm=0, it follows that 0 is an H-eigenvalue of A with x∈K\{0} being corresponding H-eigenvector; and 0 is a Z-eigenvalue of A with x∈K\{0} being corresponding Z-eigenvector.The following two propositions further give some simple properties of the positive semidefinite plus tensor.Proposition 4.
LetA∈Tm,n be positive semidefinite plus on R+n. If there exists i∈[n] such that aii⋯i=0, then aji⋯i=0 for all j∈[n].Proof.
Letei∈Rn denote the vector whose ith entry is 1 and others are 0. Suppose that there exists j∈[n] such that aji⋯i≠0, then we have (9)Aeim=aii⋯i=0,Aeim-1j=aji⋯i≠0,which contradict that A is positive semidefinite plus on R+n. Thus, the desired result holds.Proposition 5.
LetK⊆Rn be a closed cone. A is positive semidefinite plus on K if and only if either (a)
A is positive definite on K, or(b)
A is positive semidefinite on K; and for any x∈K\{0}, x is an H-eigenvector (Z-eigenvector) of A corresponding to Z-eigenvalue (Z-eigenvalue) 0.Proof.
By Definition2 and Proposition 3, it is easy to show that the desired result holds.


## 3. Properties of Solution Sets

For any given∅≠K⊆Rn, we use Kc≔Rn\K. Given a point x∈Rn, R+x is the cone {αx:α∈R+} and (10)R+x∘=R+x∗,ifx≠0,0,otherwise, where (R+x)∗ means the dual cone of the set R+x.Definition 6 (see [14]).
LetD⊆R+n be a closed cone. A tensor A∈Tm,n is called D-strictly copositive if A is copositive and Axm>0 for all x∈D\{0}.Lemma 7 (see [3]).
LetK⊆Rn be a closed convex cone and F:K→Rn be continuous. Consider the following statements: (a)
There exists a vectorx¯∈K such that the set (11)L<≔x∈K:Fx⊤x-x¯<0is bounded (possibly empty).(b)
There exists a bounded open setΩ and a vector x¯∈K⋂‍Ω such that (12)Fx⊤x-x¯≥0,∀x∈K⋂bdΩ.(c)
The CP(K, F) given by (4) has a solution.
It holds that (a)⇒(b)⇒(c). Moreover, if the set L≤≔{x∈K:F(x)⊤(x-x¯)≤0}, which is nonempty and larger than L<, is bounded, then CP(K, F) given by (4) has a nonempty and compact solution set.The following theorem is an extension of Proposition  3.3 in [14].Theorem 8.
LetA∈Tm,n be D-strictly copositive on a closed cone D⊆R+n, B∈Tp,n(2≤p<m) be positive semidefinite plus on a closed cone K⊆Rn, and q∈Rn be a given vector. Let L⊆Rn be the intersection of the solution set of Bxp-1=0 and the subspace lin(K) generated by K. Suppose that Kc⋂‍R+n⊆D, and(13)L⋂R+n⊆D⋃intR+q∘⋂R+nThen, the generalized tensor complementarity problem (14)x≥0,q+Bxp-1+Axm-1≥0,x⊤q+Bxp-1+Axm-1=0 has a nonempty and bounded solution set.Proof.
The proof of this theorem depends heavily on the idea given in the proof of [14, Proposition 3.3]. For completeness, we give it as follows.
By Lemma7, we only need to show that the set (15)L≤=x∈R+n:x⊤q+Bxp-1+Axm-1≤0is bounded. We assume that {xk}⊆L≤ is an unbounded sequence and derive a contradiction by the method of induction.
Since the sequence{xk/x} is bounded, there exists a subsequence {xs/xs} such that lims→∞xs=∞ and lims→∞xs/xs=d∈R+n\{0}. Furthermore, taking subsequence of {xs} if necessary, we assume that either {xs}⊂K or {xs}⊂Kc. Since D is closed and Kc⋂‍R+n⊆D, we have that d∈D if {xs}⊂Kc.
On one hand, it is easy to see that(16)xs⊤q+Bxsp-1+Axsm-1≤0.Thus, by dividing the inequality by xsm and letting s→∞, we obtain that Adm=0 because A is copositive. Since A is strictly copositive on D, we further have(17)d∉D.So, we obtain that {xs}⊂K and d∈K⋂‍R+n.
On the other hand, by (16) and the copositivity of A we have that(18)xs⊤q+Bxsp-1≤-Axsm≤0,∀s.Thus, by dividing the inequality by xsp and letting s→∞, it follows from (18) that Bdp=0 since d∈K⋂‍R+n. Furthermore, we conclude that Bdp-1=0 since B is positive semidefinite plus on K. So, we have that d∈L, i.e.,(19)d∈L⋂R+n.
Furthermore, since{xs}⊂K and B is positive semidefinite plus on K, it follows from (18) that q⊤d≤0, which implies that d∉int((R+q)∘). Clearly, this, together with (17) and (19), contradicts (13).
The proof is complete.Corollary 9.
LetA∈Tm,n be D-strictly copositive on a closed cone D⊆R+n, B∈Tp,n be positive semidefinite plus on a closed cone K⊆Rn for some p∈{2,3,…,m-1}, Al∈Tl,n be copositive on R+n for all l∈{2,3,…,k} with k∈{2,3,…,m-1} and k≠p, and q∈Rn be a given vector. Let L⊆Rn be the interaction of the solution set of Bxp-1=0 and the subspace lin(K) generated by K. Suppose that Kc⋂‍R+n⊆D, and (20)L⋂R+n⊆D⋃intR+q∘⋂R+nThen, the tensor complementarity problem (21)x≥0,y=q+Bxp-1+∑l=2kAlxl-1+Axm-1≥0,x⊤y=0has a nonempty and bounded solution set.Proof.
Clearly, we have(22)x⊤q+Bxp-1+∑l=2kAlxl-1+Axm-1≥x⊤q+Bxp-1+Axm-1because Al(l∈{2,3,…,k}) is copositive on R+n. In the proof of Theorem 8, we know that the set {x∈R+n:x⊤(q+Bxp-1+Axm-1)≤0} is bounded. Then, we have that the set {x∈R+n:x⊤(q+Bxp-1+∑l=2k‍Alxl-1+Axm-1)≤0} is bounded. Furthermore, the desired result holds by Lemma 7.Theorem 10.
LetA∈Tm,n and B∈Tk,n for some k∈{2,3,…,m-1} be positive semidefinite on a closed convex cone K∈Rn, and F(x)≔Axm-1+Bxk-1+q for any q∈Rn. If(23)maxAxm,Bxk>0for x∈K\{0}, then the CP(K, F) has a solution.Proof.
Denoteα≔min{m,k}. We consider the following three optimization problems:(24)ω≔minx∈K⋂B0,1x⊤Fx,(25)μ≔minx∈K⋂B0,1Axm+Bxk,and(26)ν≔minx∈K⋂B0,1x⊤qwhere B(0,1)≔{x∈Rn:x=1}. It is obvious that problems (24), (25), and (26) are solvable because objective functions x⊤F(x), Axm+Bxk, and x⊤q are continuous and the feasible set K⋂‍B(0,1) is nonempty and compact. Furthermore, it follows that the optimal solution sets of three optimization problems are compact by the continuity argument. We divide the proof into the following two parts.
Part 1. Suppose that ω≥0. In this case, for any x∈K⋂‍B(0,1) and t>1, we have that (27)tx⊤Ftx=Atxm+Btxk+tx⊤q=tm-tAxm+tk-tBxk+tFx≥0,which implies that L<≔{x∈K:F(x)⊤(x-0)<0} is bounded (possibly empty). Thus, it follows from Lemma 7 that the CP(K, F) has a solution.
Part 2. Suppose that ω<0, i.e., y⊤F(y)<0 for all y∈K⋂‍B(0,1). In this case, for any y∈K⋂‍B(0,1), it follows from (23) that Aym+Byk>0 and y⊤q<0, which implies that μ>0 and ν<0. Denote (28)y∗≔argminy⊤Fy<0,y∈K⋂B0,1Aym+Byk-y⊤q,γ≔Ay∗m+By∗k-y∗⊤q.Then, it follows that 0<μ/-ν≤γ<1. For any x∈K⋂‍B(0,1), we have (29)γ-1/α-1x⊤Fγ-1/α-1x=Aγ-1/α-1xm+Bγ-1/α-1k+γ-1/α-1x⊤q=γ-1/α-1mAxm+γ-1/α-1kBxk+γ-1/α-1x⊤q≥γ-1/α-1αAxm+γ-1/α-1αBxk+γ-1/α-1x⊤q=γ-1/α-1γ-1Axm+Bxk+x⊤q≥0. Thus, for all t>γ-1/(α-1) and x∈K⋂‍B(0,1), (30)tx⊤Ftx=tmAxm+tkBxk+tx⊤q≥tαAxm+Bxk+tx⊤q=ttα-1Axm+Bxk+x⊤q>tγ-1Axm+Bxk+x⊤q≥0 which implies that L<≔{x∈K:F(x)⊤(x-0)<0} is bounded. So, it follows from Lemma 7 that CP(K, F) has a solution.
CombiningPart 1 withPart 2, we complete the proof.Lemma 11 (see [3]).
LetK⊆Rn be a closed convex cone, and F:K→Rn be continuous. (a)
IfF is strictly monotone on K, i.e., (x-y)⊤(F(x)-F(y))>0 for any x, y∈K with x≠y, then the CP(K, F) has at most one solution.(b)
IfF is strongly monotone on K, i.e., there exists a constant c>0 such that (x-y)⊤(F(x)-F(y))≥cx-y2 for any x, y∈K, then the CP(K, F) has a unique solution.Theorem 12.
LetA∈Tm,n and B∈Tk,n for some k∈{2,3,…,m-1} be strictly positive semidefinite on a closed convex cone K, and F(x)≔Axm-1+Bxk-1+qforq∈Rn. If (31)maxx-y⊤Axm-1-Aym-1,x-y⊤Bxk-1-Byk-1>0 for all x,y∈K with x≠y, then the CP(K, F) has a unique solution.Proof.
By assumptions it follows that, for anyx,y∈K with x≠y, (32)x-y⊤Fx-Fy=x-y⊤Axm-1-Aym-1+x-y⊤Bxk-1-Byk-1≥maxx-y⊤Axm-1-Aym-1,x-y⊤Bxk-1-Byk-1>0, which implies that the function F is strictly monotone on K, and hence, the CP(K, F) has at most one solution by Lemma 11.
On the other hand, sinceA∈Tm,n and B∈Tk,n are strictly positive semidefinite on K and 0∈K, it follows that A∈Tm,n and B∈Tk,n are positive semidefinite on K; and the assumption that for any x,y∈K with x≠y(33)maxx-y⊤Axm-1-Aym-1,x-y⊤Bxk-1-Byk-1>0 implies that max{Axm,Bxk}>0 for all x∈K\{0}.
Therefore, by Theorem10, the desired result holds.Remark 13.
In Theorems10 and 12, when α>2, we can obtain that the function F is not strongly monotone on K, since K is a cone and (34)limt→0tx-0⊤Ftx-F0tx-02=limt→0Atxm+Btxktx2=limt→0tm-2Axm+tk-2Bxk=0for all x∈K⋂‍B(0,1). Thus, Theorem 12 gives a new existence result of unique solution to the concerned complementarity problem.


## 4. Traffic Equilibrium Problems

In this section, we describe a static traffic equilibrium problem [3] as an example for applications of the complementarity problems concerned in this paper. We use the same notations as in [3]. Suppose that there is a network given by a set of nodes N and a set of arcs A. Assume that users compete noncooperatively for the network and attempt to minimize their costs, where the cost of traveling along an arc a∈A is a nonlinear function ca(f) of the total flow vector f with components fb for all b∈A. Let c(f) be the vector with components ca(f) for all a∈A. We denote the set of origin nodes by O and the set of destination nodes by D, and they are distinguished. Further, the set of origin-destination (OD) pairs is a given subset W of O×D. For each w∈W, let Pw denote the set of paths connecting the OD pair w, and let P be the union of Pw ranging over all w∈W. Let hp denote the flow on the path p∈P, and let Cp(h) be the travel cost of flow on this path which is a function of the vector h≔(hp) of path flows. Let Δ be the arc-path incidence matrix with entries (35)δap≔1,ifpathp∈Ptraversesa∈A,0,otherwise. Obviously, f and h satisfy the relationship: f=Δh. A common assumption on the path cost function C(h)≔(Cp(h)) is that it satisfies (36)Ch=Δ⊤cf=Δ⊤cΔh. The unknown vector u≔(uw) where w∈W represents the minimum travel cost between OD pair w∈W. Let d≔(dw) with w∈W, where dw denote the given fixed travel demand between OD pair w. The Wardrop equilibrium principle [36] states that each user will choose the minimum cost path between every OD pair, and through this process the paths that are used will have equal cost; paths with costs higher than the minimum will have no flow. Thus,(37)0≤Cph-uw⊥hp≥0,∀w∈W,p∈Pw.Moreover, the travel demand must be satisfied, i.e.,(38)∑p∈Pwhp-dw=0,∀w∈W;and the minimum travel cost must be nonnegative, i.e.,(39)uw≥0,∀w∈W.Under some assumptions (see, for example, [3, Proposition 1.4.6]), conditions (37)-(39) are equivalent the following complementarity problem: (40)h⊤,u⊤⊤≥0,Fh,u≔Ch-Ω⊤uΩh-d≥0,h⊤,u⊤Fh,u=0,where Ω is the (OD pair, path)-incidence matrix whose entries are (41)ωwp≔1,ifp∈Pw,0,otherwise.Specially, we assume that h∈Rn1, u∈Rn2, and C(h) is a polynomial mapping of degree 2, i.e., C(h)≔Ah2+Bh+q, where A=(ai1i2i3) is a 3th-order n1-dimensional tensor, B is an n1×n1 matrix, and q∈Rn1. Then the above complementarity problem becomes(42)x≥0,A¯x2+B¯x+q¯≥0,x⊤A¯x2+B¯x+q¯=0,where (43)x≔h⊤,u⊤⊤;A¯=a¯i1i2i3∈T3,n1+n2witha¯i1i2i3≔ai1i2i3,ifi1,i2,i3∈n10,otherwise;B¯≔B-Ω⊤ΩΘΘisann2×n2zeromatrix;q¯≔q⊤,-d⊤⊤. Obviously, problem (42) is a specific case of the complementarity problems concerned in Section 3.In the following, we give a specific example for this class of traffic equilibrium problems, which has only an OD pair for simplicity.Example 1.
We consider a network given by a set of nodes{O,N1,N2,D}, where the origin node is O and the destination node is D. There are four arcs: ON1^, N1D^, ON2^, and N2D^. We denote a1≔ON1^, a2≔N1D^, a3≔ON2^, and a4≔N2D^. There are two paths: p1 and p2, connecting the origin O and the destination D, where the path p1 traverses arcs a1 and a2, and the path p2 traverses arcs a3 and a4. The cost of travel along a1, a2, a3, and a4 is defined as follows: (44)cf≔ca1fca2fca3fca4f=fa12+fa1fa22-fa212fa32+fa332fa42-fa4 where f≔(fa1,fa2,fa3,fa4)⊤ is the total flow vector. The travel demand is constant d=2. The minimum travel cost is denoted by u. The arc-path incidence matrix is (45)Δ≔10100101. Let h1 and h2 denote the flow on the paths p1 and p2, respectively. Thus, we have (46)f=Δh=h1,h1,h2,h2⊤ and (47)Ch=Cp1hCp2h=Δ⊤cf=2h122h22. Clearly, Cp1(h), Cp2(h), and d satisfy the conditions of [3, Proposition 1.4.6]. Thus, the static traffic equilibrium problem is equivalent to the following complementarity problem: (48)0≤h1h2u⊥2h12-u2h22-uh1+h2-2≥0, which can be rewritten as (49)x≥0,Ax2+Bx+q≥0,x⊤Ax2+Bx+q=0, where (50)x=x1,x2,x3⊤≔h1,h2,u⊤;A=ai1i2i3∈T3,3witha111=a222=2,andotherentriesbeingzero;B=00-100-1110;q=0,0,-2⊤. It is clear that x=(1,1,2)⊤ is a solution of this complementarity problem.


## 5. Conclusions

In this paper, we introduced a new class of tensors and discussed its simple properties. We mainly studied properties of solution sets of two classes of tensor complementarity problems, including the nonemptiness and compactness of solution set and existence of unique solution. We also investigated an application of the concerned complementarity problem in terms of a static traffic equilibrium problem. One of further issues is to design effective algorithms to solve the concerned complementarity problem; and another further issue is to investigate the error bound theory for the complementarity problems concerned in this paper.



---

*Source: 6107517-2019-03-04.xml*