Abstract
The tensor complementarity problem is a special instance of nonlinear complementarity problems, which has many applications. How to solve the tensor complementarity problem, via analyzing the structure of the related tensor, is one of very important research issues. In this paper, we propose a mixed integer programming approach for solving the tensor complementarity problem. We reformulate the tensor complementarity problem as an equivalent mixed integer feasibility problem. Based on the reformulation, some conditions for the solution existence and some solution properties of the tensor complementarity problem are given. We also prove that the tensor complementarity problem, corresponding to a positive definite diagonal tensor, has a unique solution. Finally, numerical results are reported to indicate the efficiency of the proposed algorithm.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
The tensor complementarity problem, as a generalization of the linear complementarity problem and a special instance of nonlinear complementarity problems, was proposed very recently [17]. A tensor complementarity problem (TCP) can be formulated as follows: finding \(x\in {\mathbb {R}}^n\) such that
or showing that no such vector exists, where \({\mathcal {A}}=(a_{i_1\ldots i_m})\) is an mth order n-dimensional tensor whose entries \(a_{i_1\ldots i_m}\in {\mathbb {R}}\) for \(i_j\in [n]:=\{1,\ldots ,n\}\) and \(j\in [m]:=\{1,\ldots ,m\}\), \({\mathcal {A}}x^{m-1}\) is a vector in \({\mathbb {R}}^n\) with the ith component as
for \(i\in [n]\), and \(q\in {\mathbb {R}}^n\). The TCP problem (1) is denoted as TCP\(({\mathcal {A}},q)\). When \(m=2\), TCP\(({\mathcal {A}},q)\) is just the well-known linear complementarity problem [4]. The notion of the tensor complementarity problem was used firstly by Song and Qi [23] as an application of structured tensors. Recently, many theoretical results about the solution properties of TCP\(({\mathcal {A}},q)\) have been developed [17], including existence of solution [7, 8, 19, 22, 24], global uniqueness of solution [1, 7], boundedness of solution set [3, 5, 20, 21, 24], stability of solution [26], sparsity of solution [13], solution methods [12, 25], and so on. Among them, Song and Qi [22] discussed the solution of TCP\(({\mathcal {A}},q)\) with a strictly semi-positive tensor. Che et al. [3] discussed the existence and uniqueness of solution of TCP\(({\mathcal {A}},q)\) with some special tensors. Song and Yu [20] obtained global upper bounds of the solution of the TCP\(({\mathcal {A}},q)\) with a strictly semi-positive tensor. Luo et al. [13] obtained the sparsest solutions to TCP\(({\mathcal {A}},q)\) with a Z-tensor. Gowda et al. [7] studied the various equivalent conditions for the existence of solution to TCP\(({\mathcal {A}},q)\) with a Z-tensor. Ding et al. [5] showed the properties of TCP\(({\mathcal {A}},q)\) with a P-tensor. Bai et al. [1] considered the global uniqueness and solvability for TCP\(({\mathcal {A}},q)\) with a strong P-tensor. Wang et al. [24] gave the solvability of TCP\(({\mathcal {A}},q)\) with exceptionally regular tensors. Huang, Suo and Wang [8] presented several classes of Q-tensors and discussed the solvability of TCP\(({\mathcal {A}},q)\) corresponding to Q-tensors. In addition, a practical application of TCP\(({\mathcal {A}},q)\) was given in [9]. To the best of our knowledge, the study on solution algorithms for solving TCP\(({\mathcal {A}},q)\) has few results. So how to design efficient solution methods for TCP\(({\mathcal {A}},q)\), via analyzing the structure of the related tensor, is one of very important research issues.
As shown in the above, the tensor complementarity problem TCP\(({\mathcal {A}},q)\) is a natural extension of the linear complementarity problem (LCP), which consists in finding a vector \(x\in {\mathbb {R}}^n\) that satisfies a certain system of inequalities
for given \(q\in {\mathbb {R}}^n\) and \(A\in {\mathbb {R}}^{n\times n}\). The LCP problem has been a subject with a rich mathematical theory, a variety of algorithms, and a wide range of applications in applied science and technology [4]. In past several decades, there have been numerous mathematical workers concerned with LCPs [4, 6]. There are so many well-established and fruitful methods for solving LCPs. Among them, solving LCPs via integer programming problems is an interesting and important approach [14, 15]. The authors in [14, 15] proved that how to solve an LCP problem or verify that a solution does not exist using different equivalent mixed zero-one integer programming formulations. Especially, It was shown that in the general case, the number of zero-one integer variables introduced is equal to the dimension of the LCP problem, and the number of integer variables can be reduced if it was known that a solution exists. Motivated by these interesting results, we will present a new approach to solve TCP\(({\mathcal {A}},q)\) via solving a mixed integer programming in this paper, which is the generalization of the method in [14].
In this paper, we extend the results in [14] to TCPs. We first show that TCP\(({\mathcal {A}},q)\) is solvable if and only if TCP\(({\mathcal {A}},\beta ^{m-1}q)\) has a solution for \(\beta >0\). Based on this conclusion, we reformulate TCP\(({\mathcal {A}},q)\) as a zero-one mixed integer programming (MIP) problem and establish the relationship between TCP\(({\mathcal {A}},q)\) and the MIP problem. Using different mixed zero-one integer programming formulations, we present a necessary and sufficient condition for the solvability of TCP\(({\mathcal {A}},q)\) and a sufficient condition to verify that a solution of TCP\(({\mathcal {A}},q)\) does not exist. We prove that TCP\(({\mathcal {A}},q)\) is equivalent a mixed zero-one integer feasibility problem with n zero-one integer variables. It was proved that for the LCP problem, when it is known that a solution exists, the number of integer variables can be reduced [14]. However, this result can not be extended to the TCP problem (refeqtcp) because the Hessian matrix of the nonlinear function \({{\mathcal {A}}}x^{m-1}+q\) in TCP\(({\mathcal {A}},q)\) is not constant like as LCP. In addition, since TCP\(({\mathcal {A}},q)\) with a positive definite tensor \({\mathcal {A}}\) has a nonempty and compact solution set [3], a concrete bound is given in this paper. Specially, we also prove that if \({\mathcal {A}}\) is a diagonal positive definite tensor then TCP\(({\mathcal {A}},q)\) has a unique solution, which answers Conjecture 5.1 in [3].
This paper is organized as follows. In Sect. 2, we list some preliminaries. In Sect. 3, we propose a mixed integer programming approach to solve TCP\(({\mathcal {A}},q)\) and some properties of TCP\(({\mathcal {A}},q)\) are given. Some numerical results are reported in Sect. 4. In the final section, we give some conclusions.
2 Preliminaries
In this section, we recall some basic definitions and essential conclusions in tensor eigenvalue theory, which are useful in the sequel.
Throughout this paper, we assume that m and n are integers, and \(m,n\ge 2\). Denote \({\mathbb {R}}^n:=\{(x_1,x_2,\ldots ,x_n)^T: x_i\in {\mathbb {R}}, i\in [n]\}\), where \({\mathbb {R}}\) is the set of real numbers. Define \(e:=(1,\ldots ,1)^T\in {\mathbb {R}}^n\). The set of all mth order n-dimensional real tensors is denoted as \(T_{m,n}\). For any tensor \({\mathcal {A}}=(a_{i_1\ldots i_m})\in T_{m,n}\), if its entries \(a_{i_1\dots i_m}\) are invariant under any permutation of their indices, then \(\mathcal {A}\) is called a symmetric tensor. The set of all mth order n-dimensional real symmetric tensors is denoted as \(S_{m,n}\). For a tensor \({\mathcal {A}}=(a_{i_1\ldots i_m})\in T_{m,n}\), entries \(a_{i\ldots i}\) are called diagonal entries of \({\mathcal {A}}\), for \(i\in [n]\). The other entries of \({\mathcal {A}}\) are called off-diagonal entries of \({\mathcal {A}}\). A tensor \({\mathcal {A}}\) is called diagonal if all of its off-diagonal entries are zero. Clearly, a diagonal tensor is a symmetric tensor.
Let \({\mathcal {A}}=(a_{i_1\ldots i_m})\in T_{m,n}\) and \(x\in {\mathbb {R}}^n\). Denote \(\Vert x\Vert \) as 2-norm of x and \(x^T\) as the transpose of x. Define \(\Vert x\Vert _\infty =\max \{|x_1|,\ldots ,|x_n|\}\) and
Apparently, we have \(\Vert {\mathcal {A}}x^{m-1}\Vert _\infty \le \Vert {\mathcal {A}}\Vert _\infty \Vert x\Vert ^{m-1}_\infty \) for any \(x\in {\mathbb {R}}^n\) [17].
Define
Clearly, \({\mathcal {A}}x^m\) is a homogeneous polynomial of degree m. If \({\mathcal {A}}x^m> 0\) for all \(x\in {\mathbb {R}}^n, x\ne 0\), then we say that the tensor \({\mathcal {A}}\) is positive definite. Clearly, when m is odd, there is no nontrivial positive definite tensor. This is only meaningful for even-order tensors.
In the following, we recall the definitions of E-eigenvalues and Z-eigenvalues of tensors in \(T_{m,n}\) [2, 10, 16]. Denote \({\mathbb {C}}^n:= \{(x_1,x_2,\ldots ,x_n)^T: x_i\in {\mathbb {C}}, i\in [n]\}\), where \({\mathbb {C}}\) is the set of complex numbers. For a tensor \({\mathcal {A}}\in T_{m,n}\), if there is a nonzero vector \(x\in {\mathbb {C}}^n\) and a number \(\lambda \in {\mathbb {C}}\) such that
then \(\lambda \) is called an E-eigenvalue of \({\mathcal {A}}\) and x is called an E-eigenvector of \({\mathcal {A}}\), associated with \(\lambda \). If the E-eigenvector x is real, then the E-eigenvalue \(\lambda \) is also real. In this case, \(\lambda \) and x are called a Z-eigenvalue and a Z-eigenvector of \({\mathcal {A}}\), respectively. For a symmetric tensor, Z-eigenvalues always exist. It has been shown that for any tensor \({\mathcal {A}}\in S_{m,n}\) with even order m, \({\mathcal {A}}\) is positive definite if and only if all its Z-eigenvalues are positive [16]. By [16, Theorem 5], for both the largest Z-eigenvalue \(\lambda _{max}\) and the smallest Z-eigenvalue \(\lambda _{min}\) of a symmetric tensor \(\mathcal {A}\), we have
and
3 A mixed integer programming method
In this section, we first discuss the solution existence of TCP\(({\mathcal {A}},q)\) corresponding to a diagonal tensor \({\mathcal {A}}\) and we prove that the TCP\(({\mathcal {A}},q)\) with a positive definite diagonal tensor \({\mathcal {A}}\) has a unique solution, which gives a confirmed answer to [3, Conjecture 5.1]. We reformulate the TCP\(({\mathcal {A}},q)\) as a mixed integer programming and gives a necessary and sufficient condition for the solution existence of TCP\(({\mathcal {A}},q)\). We also propose an approach to solve TCP\(({\mathcal {A}},q)\) via solving a mixed integer programming.
Clearly, TCP\(({\mathcal {A}},q)\) is equivalent to the following constrained optimization problem with optimal value 0,
It is easy to see that \(\phi (x)\ge 0\) if the feasible region of (6) is nonempty, that is, the problem (6) is bounded from below.
Based on the model (6), some properties of the solution set of TCP\(({\mathcal {A}},q)\) are easily obtained in some special cases:
-
Let \(q\ge 0\). It is clear that \(x=0\) is a trivial solution of TCP\(({\mathcal {A}},q)\) for any tensor \(\mathcal {A}\in T_{m,n}\). So, in general, we assume that \(q\ngeq 0\).
-
Let \(\mathcal {A}=(a_{i_1\ldots i_m})\in T_{m,n}\) be a diagonal tensor. In this case, the constrained optimization problem (6) is reduced as follows:
$$\begin{aligned} \min&\sum _{i=1}^{n}(a_{i\ldots i}x_{i}^{m-1}+q_i)x_i \\ \text{ s.t. }&x_i\ge 0, \quad a_{i\ldots i}x_{i}^{m-1}+q_i\ge 0, \quad i\in [n]. \end{aligned}$$From the above model, we know that if there exists \(i_0\in [n] \) such that \(a_{i_0\cdots i_0}\le 0\) and \( q_{i_0}<0\), then TCP\(({\mathcal {A}},q)\) is infeasible. Moreover, if for any \(i\in [n], q_i\ge 0\), or \( q_{i}<0\) and \(a_{i\cdots i}>0\), then TCP\(({\mathcal {A}},q)\) has a solution \(x^*\) with the ith component:
$$\begin{aligned} x^*_i=\left\{ \begin{array}{ll} 0,&{} \hbox { if}\ q_i\ge 0. \\ \left( \frac{-q_i}{a_{i\cdots i}}\right) ^{\frac{1}{m-1}},&{} \hbox { if}\ q_i<0\hbox { and }a_{i\ldots i}>0. \end{array} \right. \end{aligned}$$(7) -
In [3, Conjecture 5.1], Che, Qi and Wei proposed a conjecture that if a diagonal tensor \({\mathcal {A}}\) is positive definite then TCP\(({\mathcal {A}},q)\) has a unique solution. Here, we can give a confirmed answer to this conjecture. Since the diagonal tensor \({\mathcal {A}}\) is positive definite, \(a_{i\ldots i}>0\) for \(i\in [n]\) and every solution x of TCP\(({\mathcal {A}},q)\) satisfies
$$\begin{aligned} x_i\ge 0,\quad a_{i\ldots i}x_{i}^{m-1}+q_i\ge 0, \quad (a_{i\ldots i}x_{i}^{m-1}+q_i)x_i=0, \quad i\in [n]. \end{aligned}$$(8)When \(q\ge 0\), we claim \(x=0\). In fact, if there exists some \(i^*\in [n]\) such that \(x_{i^*}>0\), then \(a_{i^*\ldots i^*}x_{i^*}^{m-1}+q_{i^*}>0\). This is a contradiction with (8). When \(q<0\), we know
$$\begin{aligned} x_i=\left( \frac{-q_i}{a_{i\cdots i}}\right) ^{\frac{1}{m-1}}>0, \quad i\in [n]. \end{aligned}$$In fact, if there exists some \(i^*\in [n]\) such that \(x_{i^*}=0\), then \(a_{i^*\ldots i^*}x_{i^*}^{m-1}+q_{i^*}=q_{i^*}<0\). This is a contradiction with (8). In other cases, it follows from (8) that the ith component of the solution x must be in the form:
$$\begin{aligned} x_i=\left\{ \begin{array}{ll} 0,&{} \hbox { if}\ q_i\ge 0, \\ \left( \frac{-q_i}{a_{i\cdots i}}\right) ^{\frac{1}{m-1}},&{} \hbox { if}\ q_i<0, \end{array} \right. \end{aligned}$$for \(i\in [n]\). Hence, TCP\(({\mathcal {A}},q)\), corresponding to a positive definite diagonal tensor \({\mathcal {A}}\), has a unique solution.
We summarize the above discussions in the following theorem.
Theorem 1
For a given TCP\(({\mathcal {A}},q)\), if the vector \(q\ge 0\) then TCP\(({\mathcal {A}},q)\) has a trivial solution. If \({\mathcal {A}}\) be a diagonal tensor and there exists some \(i\in [n]\) such that \(q_i<0\) and \(a_{i\ldots i}\le 0\), then TCP\(({\mathcal {A}},q)\) has no solution. Otherwise, TCP\(({\mathcal {A}},q)\) with a diagonal tensor \({\mathcal {A}}\) has a solution in the form of (7). Furthermore, if the diagonal tensor \({\mathcal {A}}\) is positive definite then TCP\(({\mathcal {A}},q)\) has a unique solution \(x^*\in {\mathbb {R}}^n\) with the ith component:
Given a general TCP\(({\mathcal {A}},q)\) with \({\mathcal {A}}\in T_{m,n}\) and \(q\in {\mathbb {R}}^n\), we now show that it can always be solved by solving a mixed integer programming. Moreover, every tensor complementarity problem can be written as an equivalent mixed integer feasibility problem. These results are based on the following lemma.
Lemma 1
TCP\(({\mathcal {A}},q)\) has a solution if and only if TCP\(({\mathcal {A}},\beta ^{m-1}q)\) has a solution, where \(\beta >0\) is a real number.
Proof
We assume that \(x\in {\mathbb {R}}^n\) is a solution of TCP\(({\mathcal {A}},q)\). By (1) we have
For any \(\beta >0\), taking \(y=\beta x\), (9) yields for \(i\in [n]\),
which implies that y solves TCP\(({\mathcal {A}},\beta ^{m-1}q)\). Hence, TCP\(({\mathcal {A}},\beta ^{m-1}q)\) has a solution.
On the other hand, we assume that \(y\in {\mathbb {R}}^n\) is a solution of TCP\(({\mathcal {A}},\beta ^{m-1}q)\). Hence, (10) holds. Let \(x=y/\beta \), it follows from (10) that x satisfies (9). Hence, x solves TCP\(({\mathcal {A}},q)\). Thus, TCP\(({\mathcal {A}},q)\) has a solution. \(\square \)
Consider the following mixed integer programming (MIP):
Clearly, \(\alpha =0\), \(y=0\) and \(z=0\) is a feasible solution of MIP (11). The following theorem shows the relationship between TCP\(({\mathcal {A}},q)\) and MIP (11).
Theorem 2
Let \((\alpha ^*,y^*,z^*)\) be any optimal solution of MIP (11). If \(\alpha ^*>0\), then \(x={y^*}/{\alpha ^*}\) solves TCP\(({\mathcal {A}},q)\). If \(\alpha ^*=0\), then TCP\(({\mathcal {A}},q)\) has no solution.
Proof
For any given \({\mathcal {A}}\in T_{m,n}\) and \(q\in {\mathbb {R}}^n\) with \(q\ngeq 0\), MIP (11) always has the feasible solution \(\alpha =0\), \(y=0\) and \(z_i=0\) or 1 for \(i\in [n]\). For any feasible solution \((\alpha ,y,z)\) of MIP (11), it follows from the feasibility constraints and (2) that
Hence, MIP (11) is feasible and bounded. Suppose MIP (11) has an optimal solution \((\alpha ^*,y^*,z^*)\) with \(\alpha ^*>0\). Let \(x={y^*}/{\alpha ^*}\), then we have \(x\ge 0\) and
Furthermore, for each \(i\in [n]\), either \(x_i=0\) or \(({\mathcal {A}}x^{m-1})_i+q_i=0\), so that \(x^T({\mathcal {A}}x^{m-1}+q)=0\). That is, x solves TCP\(({\mathcal {A}},q)\).
Let \((\alpha ^*,y^*,z^*)\) be an optimal solution of MIP (11). If \(\alpha ^*=0\), then we will show that TCP\(({\mathcal {A}},q)\) has no solution. Proof by contradiction, we assume that TCP\(({\mathcal {A}},q)\) has a solution. By Lemma 1, TCP\(({\mathcal {A}},\beta ^{m-1}q)\) has a solution. That is, for any \(\beta >0\), there exists \(y\ge 0\) such that
This implies that \((\beta ,y,z)\) with \(z_i=0\) if \(y_i=0\) and \(z_i=1\) otherwise for \(i\in [n]\), is a feasible solution of MIP (11). Hence, \(\alpha ^*\ge \beta >0\). This is a contradiction and hence TCP\(({\mathcal {A}},q)\) has no solution. \(\square \)
By Theorem 2, every feasible solution \((\alpha ,y,z)\) with \(\alpha >0\) of MIP (11) corresponds to a solution of TCP\(({\mathcal {A}},q)\). Therefore, solving MIP (11), we may generate several solutions of TCP\(({\mathcal {A}},q)\).
We now show that every tensor complementarity problem can be written as an equivalent mixed integer feasibility problem. The next theorem gives a sufficient condition for TCP\(({\mathcal {A}},q)\) without solutions.
Theorem 3
Given a general TCP\(({\mathcal {A}},q)\) with \({\mathcal {A}}\in T_{m,n}\) and \(q\in {\mathbb {R}}^n\), then TCP\(({\mathcal {A}},q)\) has no solution if the system of inequalities
is infeasible.
Proof
We assume by contradiction that TCP\(({\mathcal {A}},q)\) has a solution. By Lemma 1, TCP\(({\mathcal {A}},\beta ^{m-1} q)\) also has a solution for any \(\beta >0\). By Theorem 2, MIP (11) has an optimal solution \((\alpha , y,z)\) with \(\alpha >0\). Without loss of generality, we may assume that \(\alpha \le 1\) due to (12). Hence,
In the above system, we set
Then \((\tau , x,u)\) is a solution to the following system
Hence, the system (13) is feasible, which is a contradiction. \(\square \)
By Theorem 3, if TCP\(({\mathcal {A}},q)\) is solvable then the corresponding system (13) is feasible. More generally, the following theorem gives a necessary and sufficient condition for the solvability of TCP\(({\mathcal {A}},q)\).
Theorem 4
Given a general TCP\(({\mathcal {A}},q)\) with \({\mathcal {A}}\in T_{m,n}\) and \(q\in {\mathbb {R}}^n\), then TCP\(({\mathcal {A}},q)\) is solvable if and only if the system
is feasible.
Proof
The necessary condition is easily obtained from the proof line of Theorem 3. We now show the sufficient condition. Since the system (14) is feasible, let \((x^*,u^*,\tau ^*)\) be a feasible point of (14). Clearly, we have
Furthermore, when \(x^*_i>0\) for some \(i\in [n]\), we have \(u^*_i=\tau ^*\) and hence \(({\mathcal {A}}x^{m-1}+q)_i=0\). Thus,
Therefore, \(x^*\) is a solution of TCP\(({\mathcal {A}},q)\). That is, TCP\(({\mathcal {A}},q)\) is solvable. This completes the proof. \(\square \)
Let \({\mathcal {A}}\in S_{m,n}\). By [3, Theorem 4.5], we know that if \({\mathcal {A}}\) is positive definite then TCP\(({\mathcal {A}},q)\) is solvable for any \(q\in {\mathbb {R}}^n\) and its solution set is nonempty and compact. Furthermore, the following theorem gives a concrete bound.
Theorem 5
Let \({\mathcal {A}}\in S_{m,n}\) and \(q\in {\mathbb {R}}^n\). If \({\mathcal {A}}\) is positive definite, then the solution set of TCP\(({\mathcal {A}},q)\) is contained in the set
where \(\lambda _{min}\) is the smallest Z-eigenvalue of \({\mathcal {A}}\).
Proof
Since \({\mathcal {A}}\) is positive definite, by Theorem 4.5 in [3], TCP\(({\mathcal {A}},q)\) has a nonempty and compact solution set. Let S be its solution set. In addition, by Theorem 5 in [16], Z-eigenvalues of \({\mathcal {A}}\) exist and the smallest Z-eigenvalue \(\lambda _{min}>0\). Taking \(x\in S\) and \(x\ne 0\), we have
Setting \(y=x/{\Vert x\Vert }\), we have \(\Vert y\Vert =1\) and \({\mathcal {A}}x^m=\Vert x\Vert ^m{\mathcal {A}}y^m\). It follows from (5) that
Combining (15) and (16), we obtain
which yields
Hence, \(x\in B\). This completes the proof. \(\square \)
Note that strictly semi-positive tensors were introduced very recently [19]. A tensor \({\mathcal {A}}\in S_{m,n}\) is called strictly semi-positive if for any \(x\ge 0, x\ne 0\) there exists an index \(k\in [n]\) such that \(x_k({\mathcal {A}}x^{m-1})_k>0\). Clearly, a positive definite tensor must be strictly semi-positive. Hence, the result in the above theorem is regards as a special case of [20, Theorem 3.4].
4 Numerical experiments
In this section, we solve some examples of TCP\(({\mathcal {A}},q)\) via solving the related MIP (11). We consider the following examples for numerical experiments with the mixed integer programming method. We implement all experiments using Global Solver in LINGO10 on a laptop with an Intel(R) Core(TM) i5-2520M CPU(2.50 GHz) and RAM of 4.00 GB.
Example 1
Consider TCP\(({\mathcal {A}},q)\), where \(q=(2,2)^T\) and \({\mathcal {A}}=(a_{i_1i_2i_3})\in T_{3,2}\) with its entries \(a_{111}=1, a_{122}=-1, a_{211}=-2, a_{222}=1\) and other \(a_{i_1i_2i_3}=0\).
By straightforward computation, we obtain that the TCP\(({\mathcal {A}},q)\) in Example 1 has two solutions \((0,0)^T\) and \((2,\sqrt{6})^T\). Since \(q=(2,2)^T>0\), the solution \((0,0)^T\) is trivial by Theorem 1. The corresponding MIP is written as follows:
Running the LINGO code, we first obtain a solution of the above MIP:
By Theorem 2, we obtain the trivial solution (0, 0). We adjust the range of \(\alpha \) in the constraints as \(0\le \alpha <0.5\) and obtain another solution:
By Theorem 2, we obtain a solution of the TCP\(({\mathcal {A}},q)\): \(x^*=y^*/\alpha ^*=(2,2.4494895)^T\approx (2,\sqrt{6})^T\). We try different range of \(\alpha \) in the constrained region and obtain the two solutions. The details are listed in Table 1, where Range denotes the constraint on \(\alpha \) in MIP, Iter denotes total solver iterations, SOL-TCP denotes the solution of TCP\(({\mathcal {A}},q)\).
Example 2
Consider TCP\(({\mathcal {A}},q)\), where \(q=(-2,-3)^T\) and \({\mathcal {A}}=(a_{i_1i_2i_3})\in T_{3,2}\) with \(a_{122}=-2, a_{211}=-1\), and other \(a_{i_1i_2i_3}=0\).
In this example, we have
for any \(x\in {\mathbb {R}}^2\). Clearly, the TCP\(({\mathcal {A}},q)\) has no solution. The corresponding MIP is written as follows:
Running the LINGO code of the above MIP, we obtain the global solution:
By Theorem 2, the TCP\(({\mathcal {A}},q)\) in Example 2 has no solution. We take different range of \(\alpha \) in the above MIP and always obtain the same result. The details are listed in Table 2.
Example 3
Consider TCP\(({\mathcal {A}},q)\), where \(q=(0,-1)^T\) and \({{\mathcal {A}}}=(a_{{i_1}{i_2}{i_3}{i_4}})\in T_{4,2}\) with \(a_{1111}=1, a_{1112}=-2, a_{1122}=1,a_{2222}=1,\) and other \(a_{{i_1}{i_2}{i_3}{i_4}}=0\).
This example is taken from [1] and the TCP\(({\mathcal {A}},q)\) has two solutions: \(x^*=(0,1)^T\) and \(x^*=(1,1)^T\). By simple calculating, we have
and its corresponding MIP:
Running the LINGO code of the above MIP, we obtain the global solution:
By Theorem 2, we can obtain the solution \(x^*=(1,1)^T\). We change different range of \(\alpha \) in its LINGO code and always obtain the solution, and we don’t get another solution (0, 1). The details are listed in Table 3.
We observe the related MIP model carefully and find the first constraint without the term \(\alpha \). Thus, we add a small perturbation \(10^{-5}\alpha ^3\) and run the LINGO code again. Fortunately, we obtain the following solution of the above MIP:
By Theorem 2, we can obtain another solution \(x^*=(0,1)^T\). The details are listed in Table 4.
From Tables 3 and 4 , we see that Global Solver in LINGO10 is very sensitive to solve mixed zero-one integer nonlinear optimization problems. The numerical results reported in the above tables show that our proposed approach is a good way to solve tensor complementarity problems. It would be much better if there are powerful solvers for mixed integer nonlinear programming problems.
5 Concluding remarks
In this paper, we proposed a mixed zero-one integer nonlinear programming method to solve the tensor complementarity problem TCP\(({\mathcal {A}},q)\). For a diagonal tensor \({\mathcal {A}}\), we gave conditions to guarantee the solution existence of TCP\(({\mathcal {A}},q)\). Specially, we proved that TCP\(({\mathcal {A}},q)\) with diagonal positive definite tensor \({\mathcal {A}}\) have a unique solution and then gave a confirmed answer for [3, Conjecture 5.1]. We formulated TCP\(({\mathcal {A}},q)\) as an MIP problem (11), based on the MIP model, we shown that TCP\(({\mathcal {A}},q)\) is equivalent to a mixed integer feasibility problem. Moreover, we gave a sufficient condition for TCP\(({\mathcal {A}},q)\) without solutions, and also a necessary and sufficient condition for the solvability of TCP\(({\mathcal {A}},q)\).
We proved that every feasible solution \((\alpha ,y,z)\) with \(\alpha >0\) of MIP (11) corresponds to a solution of TCP\(({\mathcal {A}},q)\). Therefore, by solving MIP (11), we may generate several solutions of TCP\(({\mathcal {A}},q)\). We also reported some numerical results to show the efficiency of the proposed approach.
References
Bai, X., Huang, Z., Wang, Y.: Global uniqueness and solvability for tensor complementarity problems. J. Optim. Theory Appl. 170, 72–84 (2016)
Chang, K.C., Pearson, K., Zhang, T.: Perron–Frobenius theorem for nonnegative tensors. Commun. Math. Sci. 6, 507–520 (2008)
Che, M., Qi, L., Wei, Y.: Positive definite tensors to nonlinear complementarity problems. J. Optim. Theory Appl. 168, 475–487 (2016)
Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, New York (1992)
Ding, W., Luo, Z., Qi, L.: P-Tensors, \(\text{ P }_0\)-Tensors, and tensor complementarity problem. Linear Algebra Appl. 555, 336–354 (2018)
Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)
Gowda, M.S., Luo, Z., Qi, L., Xiu, N.: Z-tensors and complementarity problems, arXiv: 1510.07933v2 (2016)
Huang, Z., Suo, S., Wang, J.: On Q-tensors, arXiv: 1509.03088, (2015)
Huang, Z., Qi, L.: Formulating an \(n\)-person noncooperative game as a tensor complementarity problem. Comput. Optim. Appl. 66, 557–576 (2017)
Lim, L.-H.: Singular values and eigenvalues of tensors: a variational approach. In: Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Addaptive Processing (CAMSAP’05), Vol. 1, pp. 129–132. IEEE Computer Society Press, Piscataway, NJ (2005)
Ling, C., He, H., Qi, L.: On the cone eigenvalue complementarity problem for higher-order tensors. Comput. Optim. Appl. 63, 143–168 (2016)
Liu, D., Li, W., Vong, S.W.: Tensor complementarity problems: the GUS-property and algorithm. Linear Multi Algebra 66, 1726–1749 (2018)
Luo, Z., Qi, L., Xiu, N.: The sparsest solutions to Z-tensor complementarity problems. Optim. Lett 11, 471–482 (2017)
Pardalos, P.M., Rosen, J.B.: Global optimization approach to the linear complementarity problem. SIAM J. Sci. Stat. Comput. 9, 341–353 (1988)
Pardalos, P.M.: Linear complementarity problems solvable by integer programming. Optimization 19, 467–474 (1988)
Qi, L.: Eigenvalues of a real supersymmetric tensor. J. Symb. Comput. 40, 1302–1324 (2005)
Qi, L., Chen, H., Chen, Y.: Tensor Eigenvalues and Their Applications. Springer, Singapore (2018)
Qi, L., Luo, Z.: Tensor Analysis: Spectral Theory and Special Tensors. SIAM, Philadelpia (2017)
Song, Y., Qi, L.: Properties of tensor complementarity problem and some classes of structured tensors. Ann. Appl. Math. 33, 308–323 (2017)
Song, Y., Yu, G.: Properties of solution set of tensor complementarity problem. J. Optim. Theory Appl. 170, 85–96 (2016)
Song, Y., Qi, L.: Strictly semi-positive tensors and the boundedness of tensor complementarity problems. Optim. Lett. 11, 1407–1426 (2017)
Song, Y., Qi, L.: Tensor complementarity problem and semi-positive tensors. J. Optim. Theory Appl. 169, 1069–1078 (2016)
Song, Y., Qi, L.: Properties of some classes of structured tensors. J. Optim. Theory Appl. 165, 854–873 (2015)
Wang, Y., Huang, Z., Bai, X.: Exceptionally regular tensors and tensor complementarity problems. Optim. Methods Softw. 31, 815–828 (2016)
Xie, S., Li, D., Xu, H.: An iterative method for finding the least solution to the tensor complementarity problem. J. Optim. Theory Appl. 175, 119–136 (2017)
Yu, W., Ling, C., He, H.: On the properties of tensor complementarity problems, arXiv:1608.01735v3 (2018)
Acknowledgements
The authors would like to thank the editor and the anonymous referees for their helpful constructive comments and suggestions which lead to a significantly improved version of the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work was supported by the National Nature Science Foundation of China (Grant Nos. 11671220, 11771244) and the Nature Science Foundation of Shandong Province (ZR2016AM29).
Rights and permissions
About this article
Cite this article
Du, S., Zhang, L. A mixed integer programming approach to the tensor complementarity problem. J Glob Optim 73, 789–800 (2019). https://doi.org/10.1007/s10898-018-00731-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-018-00731-4