A Monotone Semismooth Newton Method for a Kind of Tensor Complementarity Problem

Shuilian Xie

School of Mathematics, Jiaying University, Meizhou, Guangdong, China.

DOI: 10.4236/apm.2021.114023                

Abstract

Tensor complementarity problem (TCP) is a special kind of nonlinear complementarity problem (NCP). In this paper, we introduce a new class of structure tensor and give some examples. By transforming the TCP to the system of nonsmooth equations, we develop a semismooth Newton method for the tensor complementarity problem. We prove the monotone convergence theorem for the proposed method under proper conditions.

Keywords

Tensor Complementarity Problem, M-Like Tensor, Semismooth Newton Method, Monotone Convergence

1. Introduction

A Tensor is a multi-arrray. We denote by $T\left(m\mathrm{,}n\right)$ the space of all m-order and n-dimension tensors. $A\in T\left(m\mathrm{,}n\right)$ is in the form of

$A=\left[a_{i_1{i}_2\cdots i_m}\right],a_{i_1{i}_2\cdots i_m}\in R,1\le i_1,i_2,\cdots ,i_m\le n.$

If the entries $a_{i_1{i}_2\cdots i_m}$ are invariant under any permutation of their indices, then $A$ is called a symmetric tensor. We denote by $ST\left(m\mathrm{,}n\right)\subset T\left(m\mathrm{,}n\right)$ the space of all symmetric tensors in $T\left(m\mathrm{,}n\right)$.

In this paper, we discuss the following tensor complementarity problem (simplified as TCP $\left(A\mathrm{,}p\mathrm{,}q\right)$ ): finding a point $x\in R^n$ such that

$F\left(x\right)=A{x}^{m-1}-q\ge 0,x\ge p,{\left(x-p\right)}^{\text{T}}F\left(x\right)=0,$ (1.1)

where $q\mathrm{,}p\in R^n$, $p>0$ and $A\in ST\left(m\mathrm{,}n\right)$. $A{x}^{m-1}$ is an n-dimensional vector, whose ith component is given by [1]

${\left(A{x}^{m-1}\right)}_i={\displaystyle \underset{i_2,\cdots ,i_m=1}{\overset{n}{\sum }}}{a}_{i{i}_2\cdots i_m}{x}_{i_2}{x}_{i_3}\cdots x_{i_m}.$

$A{x}^{m-2}$ is an $n\times n$ matrix, whose ith row and jth column is given by

${\left(A{x}^{m-2}\right)}_{ij}={\displaystyle \underset{i_3,\cdots ,i_m=1}{\overset{n}{\sum }}}{a}_{ij{i}_3\cdots i_m}{x}_{i_3}{x}_{i_4}\cdots x_{i_m}.$

It is obvious that $\nabla F\left(x\right)=\left(m-1\right)A{x}^{m-2}$.

Tensor complementarity problem has many applications, such as nonlinear compressed sensing, communications, DNA microarrays, n-person noncooperative game and so on, see for example [2] [3]. TCP has received much attention and has taken good progress in recent years [4] - [13], such as the structure of the solution set, the global uniqueness solvability and the error bound and so on. Bai, Huang and Wang [4] proved that the P-tensor complementarity problem has a nonempty compact solution set. What’s more, they showed the global uniqueness solvability property for the TCP with a strong P-tensor. Che, Qi and Wei [5] showed that when the tensor is a positive definite or strictly copositive tensor, the TCP has a nonempty compact solution set. On the other hand, however, the study in the related numerical methods is very few. Luo, Qi and Xiu [3] proposed an iterative method to find the sparsest solutions to theZ-tensor complementarity problem with a non-positive constant term. Xu, Li and Xie [14] concerned with the tensor complementarity problem with a positive semi-definite Z-tensor. Under the assumption that the problem has a solution at which the strict complementarity holds, they showed that the problem is equivalent to a system of lower dimensional tensor equations. In this paper, we present a semismooth Newton method for TCP, under the assumption that $F\left(x\right)$ is a concave function, we establish the monotone convergence theorem for the proposed method. Here $F\left(x\right)$ is concave means $F_i\left(x\right)$ is a concave function, $i=1,2,\cdots ,n$.

For convenience of presentation, we introduce some concepts and notations which will be used throughout the paper. We denote $\left[n\right]=\left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$. Let $I\subset \left[n\right]$ with $\left|I\right|=r$. Denote by ${\left(A{x}^{m-1}\right)}_I$ the r-dimensional subvector of $A{x}^{m-1}$ and its elements are ${\left(A{x}^{m-1}\right)}_i$, $i\in I$. Similarly, we denote $q_I$ as the r-dimensional subvector of q and its elements are $q_i$, $i\in I$.

2. Semismooth Newton Method and Its Convergence

We first introduce a new class of structure tensor, called M-like tensor.

Definition 2.1. A tensor $A\in T\left(m\mathrm{,}n\right)$ is called an M-like tensor, if for $\forall x\in R_{+}^n$, $A{x}^{m-2}$ is an M-matrix.

Remark 2.1. As an example, it is easy to verify that the even-order diagonal tensors with all positive diagonal entries are M-like tensors. We give a non-diagonal M-like tensor.

Example 2.1. Let $A$ be a 4th-order 2-dimensional tensor with elements

$\{\begin{array}{l}{a}_{1111}=a_{2222}=2,\hfill \\ a_{1212}=a_{1221}=-1/2,\hfill \\ a_{2112}=a_{2121}=-1/3.\hfill \end{array}$

It is easy to verify $A$ is an M-like tensor over $R_{+}^2$. In the following, without specification, we always suppose $A$ is an M-like tensor.

Let $\varphi \mathrm{<mo>\; :\; </mo>}{R}^2\to R$ be the well-known Fischer-Burmeister function defined by

$\varphi \left(\mu \mathrm{,}\nu \right)=\mu +\nu -\sqrt{{\mu }^2+{\nu }^2}\mathrm{.}$ (2.1)

It is easy to see that TCP (1.1) can be transformed to the system of nonsmooth equations:

$H\left(x\right)\triangleq \left(\begin{array}{c}{H}_1\left(x\right)\\ H_2\left(x\right)\\ ⋮\\ H_n\left(x\right)\end{array}\right)\triangleq \left(\begin{array}{c}\varphi \left(x_1-p_1,F_1\left(x\right)\right)\\ \varphi \left(x_2-p_2,F_2\left(x\right)\right)\\ ⋮\\ \varphi \left(x_n-p_n,F_n\left(x\right)\right)\end{array}\right)=0,$ (2.2)

where $F_i\left(x\right)={\left(A{x}^{m-1}-q\right)}_i$.

Let ${\partial }_{B}H\left(x^{\left(k\right)}\right)$ denote the B-subdifferential of H at $x^{\left(k\right)}$. $V^k\in {\partial }_{B}H\left(x^{\left(k\right)}\right)$, if it satisfies

$\Vert H\left(x^{\left(k\right)}\right)-H\left(x^{\star }\right)-V^k\left(x^{\left(k\right)}-x^{\star }\right)\Vert =O\left({\Vert x^{\left(k\right)}-x^{\star }\Vert }^2\right)\text{as}\Vert x^{\left(k\right)}-x^{\star }\Vert \to 0.$

For any $V\in {\partial }_{B}H\left(x\right)$ can be expressed as follows.

$V=diag\left(a_i\right)\left(m-1\right)\left(A{x}^{m-2}\right)+diag\left(b_i\right)\mathrm{,}$ (2.3)

where

${\left(a_i-1\right)}^2+{\left(b_i-1\right)}^2\le \mathrm{1,}i=\mathrm{1,2,}\cdots \mathrm{,}n\mathrm{.}$ (2.4)

It is easy to see that $a_i\ge \mathrm{0,}{b}_i\ge 0$ and $a_i^2+b_i^2>0$ for $i=\mathrm{1,2,}\cdots \mathrm{,}n$.

Now, we present semismooth Newton method for TCP (1.1).

Algorithm 2.1 (Semismooth Newton Method)

Step 0. Choose $\epsilon >0$ and initial point $x^{\left(0\right)}$. Let $k=0$.

Step 1. If $\Vert H\left(x^{\left(k\right)}\right)\Vert <\epsilon$, stop.

Step 2. Choose $V^k\in {\partial }_{B}H\left(x^{\left(k\right)}\right)$, calculate $d^k$ satisfying the following linear equations

$V^k{d}^k=-H\left(x^{\left(k\right)}\right).$ (2.5)

Step 3. Calculate

$x^{\left(k+1\right)}=x^{\left(k\right)}+d^{\left(k\right)}\mathrm{.}$ (2.6)

Let $k:=k+1$ and goto Step 1.

Theorem 2.2. [15] Let $x^{\star }$ be the solution of (1). Then the sequence $\left\{x^{\left(k\right)}\right\}$ generated by (6) is Q-quadratically convergent to $x^{\star }$ if $x^{\left(0\right)}$ is sufficiently close to $x^{\star }$.

In the following, we will prove the sequence $\left\{x^{\left(k\right)}\right\}$ monotonically converges to the solution of (1). First, we give some useful lemmas.

Lemma 2.3. [16] Let $A\in R^{n\times n}$ be an M-matrix and $B\ge A$ satisfy $b_{ij}\le 0$ for $i\ne j$. Then B is an M-matrix and

$0\le B^{-1}\le A^{-1}\mathrm{.}$

Furthermore, any principle submatrix of A is again an M-matrix.

By the definition of V, the ith row $V_i$ of V can be presented by

$V_i=\{\begin{array}{ll}\left(m-1\right)a_i{\left(A{x}^{m-2}\right)}_i+b_i{e}_i,\hfill & a_i>0\text{and}{b}_i>0,\hfill \\ \left(m-1\right){\left(A{x}^{m-2}\right)}_i,\hfill & a_i=1\text{and}{b}_i=0,\hfill \\ e_i,\hfill & a_i=0\text{and}{b}_i=1,\hfill \end{array}$

where ${\left(A{x}^{m-2}\right)}_i$ is the ith row of $A{x}^{m-2}$ and $e_i$ is the ith row of the $n\times n$ identity matrix. It is easy to verify $V=KB$, where $K=diag\left(k_i\right)$ with

$k_i=\{\begin{array}{ll}{a}_i,\hfill & a_i\ne 0,\hfill \\ 1/\left(a_{ii}\right),\hfill & a_i=0\hfill \end{array}$

and

$B=\left(\begin{array}{c}{B}_1\\ B_2\\ ⋮\\ B_n\end{array}\right)$

with

$B_i=\{\begin{array}{ll}\left(m-1\right){\left(A{x}^{m-2}\right)}_i+\left(b_i/a_i\right)e_i,\hfill & a_i\ne 0,\hfill \\ a_{ii}{e}_i,\hfill & a_i=0,\hfill \end{array}$

where $a_{ii}$ is the ith diagonal element of $\left(m-1\right)A{x}^{m-2}$. Noting that $B\ge \left(m-1\right)A{x}^{m-2}$ with the off-diagonal element being nonpositive, we have B is an M-matrix and $0\le B^{-1}\le {\left(\left(m-1\right)A{x}^{m-2}\right)}^{-1}$ by Lemma 2.3. This together with K being a positive diagonal matrix, we obtain the following lemma.

Lemma 2.4. Let the matrix V be defined by (2.3), then V is an M-matrix.

Define the set D by

$D=\left\{x\ge p\mathrm{<mo>\; |\; </mo>}H\left(x\right)\le 0\right\}\mathrm{.}$

As p always belongs to D, D is not empty.

Lemma 2.5. Let $x^{\star }$ be the solution of (1.1). Then $x^{\star }\in D$ and

$x^{\star }\ge x\mathrm{,}\forall x\in D\mathrm{.}$

Proof. Since $x^{\star }$ is the solution of (1.1), we have $x^{\star }\ge p$ and $H\left(x^{\star }\right)=0$. This implies that $x^{\star }\in D$.

For any $x\in D$, we have $x\ge p$ and $H\left(x\right)\le 0$. Associated to x, we define two disjoint index sets as follows:

$I_1:=\left\{i|x_i=p_i\right\}\text{and}{I}_2:=\left\{i|x_i>p_i\right\}.$

This together with the fact $x^{\star }\ge p$ implies $x_i^{\star }\ge x_i$ for all $i\in I_1$. Since $H\left(x\right)\le 0$, we have

$F_{I_2}\left(x\right)\le 0\le F_{I_2}\left(x^{\star }\right)\mathrm{.}$

Noting that $A$ is an M-like tensor, by Theorem 4 in [17], we have $F\left(x\right)$ is a strong T-monotone function. Hence by Lemma 2.2 in [18], we immediately have that $x^{\star }\le x$. This completes the proof.

Lemma 2.6. Let $x^{\left(0\right)}\in D$. Then the sequence $\left\{x^{\left(k\right)}\right\}$ generated by (2.6) is contained in D and satisfies

$x^{\left(k\right)}\le x^{\left(k+1\right)},k=0,1,\cdots$

Proof. We prove the conclusion by induction. For simplicity, we denote $x^{\left(k\right)}$ and $x^{\left(k+1\right)}$ by x and y respectively. Suppose $x\in D$, we only need to verify $x\le y$ and $y\in D$. Since $V^{-1}\ge 0$, by (2.5) we have

$d=-V^{-1}H\left(x\right)\ge 0.$

Hence, we get

$y=x+d\ge x\ge p\mathrm{.}$ (2.7)

Now, we prove $H\left(y\right)\le 0$. Associated to x, we define four disjoint index sets as follows:

$J_1:=\left\{i|x_i=p_i,F_i\left(x\right)>0\right\},J_2:=\left\{i|x_i>p_i,F_i\left(x\right)=0\right\},$

$J_3:=\left\{i|x_i=p_i,F_i\left(x\right)=0\right\},J_4:=\left\{i|x_i\ge p_i,F_i\left(x\right)<0\right\}.$

Then by (2.1), (2.2), (2.4), we have

$\{\begin{array}{ll}{H}_i\left(x\right)=0,a_i=0,b_i=1,\hfill & \text{if}i\in J_1,\hfill \\ H_i\left(x\right)=0,a_i=1,b_i=0,\hfill & \text{if}i\in J_2,\hfill \\ H_i\left(x\right)=0,a_i\ge 0,b_i\ge 0,\hfill & \text{if}i\in J_3,\hfill \\ H_i\left(x\right)<0,a_i>1,b_i\in \left(0,1\right],\hfill & \text{if}i\in J_4.\hfill \end{array}$ (2.8)

If $i\in J_1$, by (2.3), (2.5), (2.8) we get $d_i=-H_i\left(x\right)=0$ and $y_i=x_i+d_i=x_i=p_i$. This together with (2.2), (2.1) implies $H_i\left(y\right)\le 0$.

If $i\in J_2$, $y_i=x_i+d_i\ge x_i>p_i$. Since $F_i\left(x\right)$ is concave, by (2.3), (2.5), (2.8) again, we have

$\begin{array}{c}{F}_i\left(y\right)=F_i\left(x+d\right)=F_i\left(x\right)+{\displaystyle {\int }_0^1}\nabla F_i{\left(x+t\left(y-x\right)\right)}^{\text{T}}\left(y-x\right)\text{d}t\\ \le F_i\left(x\right)+{\displaystyle {\int }_0^1}\nabla F_i{\left(x\right)}^{\text{T}}\left(y-x\right)\text{d}t=0.\end{array}$

Hence, $H_i\left(y\right)\le 0$.

If $i\in J_3$, by (2.5) and (2.3), we obtain

$a_i\left(m-1\right){\left(A{x}^{m-2}\right)}_i^{\text{T}}d+b_i{d}_i=-H_i\left(x\right)=0.$

where $a_i\ge 0$ and $b_i\ge 0$. Hence, we have

$a_i\left(m-1\right){\left(A{x}^{m-2}\right)}^{\text{T}}d=-b_i{d}_i\le 0.$

If $a_i>0$, then $F_i\left(y\right)\le F_i\left(x\right)+\left(m-1\right){\left(A{x}^{m-2}\right)}_i^{\text{T}}d\le 0$, which implies $H_i\left(y\right)\le 0$.

If $a_i=0$, then by (2.4) we have $b_i=1$, and then $d_i=0$. Since $A$ is an M-like tensor, ${\left(A{x}^{m-2}\right)}_{ij}\le 0$ and $d_j\ge 0$ for $j\ne i$, we have

$F_i\left(y\right)\le F_i\left(x\right)+\left(m-1\right){\left(A{x}^{m-2}\right)}_i^{\text{T}}d=\left(m-1\right){\displaystyle \underset{j\ne i}{\sum }}{\left(A{x}^{m-2}\right)}_{ij}{d}_j\le 0.$

Hence, $H_i\left(y\right)\le 0$.

Similarly, if $i\in J_4$, by simple calculations,

$a_i\left(m-1\right){\left(A{x}^{m-2}\right)}_i^{\text{T}}d\le -H_i\left(x\right)\text{and}{a}_i=1-F_i\left(x\right)/\sqrt{x_i^2+F_i^2\left(x\right)},$

and hence

$\left(m-1\right){\left(A{x}^{m-2}\right)}_i^{\text{T}}d\le \frac{\sqrt{x_i^2+F_i^2\left(x\right)}-x_i-F_i\left(x\right)}{1-F_i\left(x\right)/\sqrt{x_i^2+F_i^2\left(x\right)}}\mathrm{.}$

Therefore, we have

$\begin{array}{c}{F}_i\left(y\right)\le F_i\left(x\right)+\left(m-1\right){\left(A{x}^{m-2}\right)}_i^{\text{T}}d\\ \le F_i\left(x\right)+\frac{\sqrt{x_i^2+F_i^2\left(x\right)}-x_i-F_i\left(x\right)}{1-F_i\left(x\right)/\sqrt{x_i^2+F_i^2\left(x\right)}}\\ =\frac{x_i^2-x_i\sqrt{x_i^2+F_i^2\left(x\right)}}{\sqrt{x_i^2+F_i^2\left(x\right)}-F_i\left(x\right)}\le 0.\end{array}$

Hence,

$H_i\left(y\right)\le \mathrm{0,}\forall i\in J_4\mathrm{.}$

The above argument has shown $H\left(y\right)\le 0$. From (2.7), we have $y\ge x$ and $y\in D$. The proof is completed.

Noting that the sequence $\left\{V^k\right\}$ is uniformly bounded, by Lemmas 2.5 and 2.6 and Theorem 2.2, it is easy to obtain the following theorem.

Theorem 2.7. Let $x^{\left(0\right)}\in D$ and $\left\{x^{\left(k\right)}\right\}$ be the sequence generated by (2.6). Then we have for all $k\ge 0$

$x^{\left(k\right)}\le x^{\left(k+1\right)}\le x^{\star }\mathrm{.}$

Moreover, the sequence $\left\{x^{\left(k\right)}\right\}$ converges to $x^{\star }$ Q-quadratically.

3. Conclusion

We have introduced a new kind of structure tensor and discussed the numerical algorithm for TCP. By transforming the TCP to the system of nonsmooth equations, we have presented a semismooth Newton method for TCP. At each iteration, only linear equations need to be solved. The sequence generated by the algorithm is monotonically convergent to the solution of the TCP under proper conditions. This method can be regarded as a kind of Newton-iteration method. There are still some interesting future works that need to be done. For example, we can extend Algorithm 2.1 for other structure TCP and discuss its convergence.

Founding

The work was supported by the Educational Commission of Guangdong Province, China (grant No. 2019KTSCX172).

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Qi, L. (2005) Eigenvalues of a Real Supersymmetric Tensor. Journal of Symbolic Computation, 40, 1302-1324. https://doi.org/10.1016/j.jsc.2005.05.007
[2]	Huang, Z. and Qi, L. (2017) Formulating an n-Person Noncooperative Game as a Tensor Complementarity Problem. Computation Optimization and Applications, 66, 557-576. https://doi.org/10.1007/s10589-016-9872-7
[3]	Luo, Z.Y., Qi, L. and Xiu, N.H. (2017) The Sparse Solutions to Z-Tensor Complemenatiry Problems. Optimization Letters, 11, 471-482. https://doi.org/10.1007/s11590-016-1013-9
[4]	Bai, X.L., Huang, Z.H. and Wang, Y. (2016) Global Uniqueness and Solvability for Tensor Complementarity Problems. Journal of Optimization Theory and Applications, 170, 72-84. https://doi.org/10.1007/s10957-016-0903-4
[5]	Che, M., Qi, L. and Wei, Y. (2016) Positive-Definite Tensors to Nonlinear Complementarity Problems. Journal of Optimization Theory and Applications, 168, 475-487. https://doi.org/10.1007/s10957-015-0773-1
[6]	Ding, W., Luo, Z. and Qi, L. (2015) P-Tensors, P0-Tensors, and Tensor Complementarity Problem. arXiv:1507.06371.
[7]	Gowda, M.S., Luo, Z., Qi, L. and Xiu, N. (2015) Z-Tensors and Complementarity Problems. arXiv:1510.07933.
[8]	Huang, Z., Suo, Y. and Wang, J. (2015) On Q-tensors. arXiv:1509.03088.
[9]	Song, Y. and Qi, L. (2015) Properities of Some Classes of Structured Tensors. Journal of Optimization Theory and Applications, 165, 854-873. https://doi.org/10.1007/s10957-014-0616-5
[10]	Song, Y. and Qi, L. (2017) Properties of Tensor Complemenatiry Problem and Some Classes of Structured Tensors. Annals of Applied Mathematics, 33, 308-323.
[11]	Song, Y. and Qi, L. (2015) Error Bound of P-Tensor Nonlinear Complementarity Problem. arXiv:1508.02005v2.
[12]	Song, Y. and Yu, G.H. (2016) Properties of Solution Set of Tensor Complemenatiry Problem. Journal of Optimization Theory and Applications, 170, 85-96. https://doi.org/10.1007/s10957-016-0907-0
[13]	Wang, Y., Huang, Z.H. and Bai, X.L. (2016) Exceptionally Regular Tensors and Tensor Complementarity Problems. Optimization Methods and Software, 31, 815-828. https://doi.org/10.1080/10556788.2016.1180386
[14]	Xu, H.R., Li, D.H. and Xie, S.L. (2019) An Equivalent Tensor Equation to the Tensor Complementarity Problem with Positive Semi-Definite Z-Tensor. Optimization Letters, 13, 685-694. https://doi.org/10.1007/s11590-018-1268-4
[15]	Qi, L. (1993) Convergence Analysis of some Algorithms for Solving Nonsmooth Equations. Mathematics of Operations Research, 18, 227-244. https://doi.org/10.1287/moor.18.1.227
[16]	Hackbusch, W. (1994) Iterative Solution of Large Sparse Systems of Equations, Springer-Verlag, Berlin. https://doi.org/10.1007/978-1-4612-4288-8
[17]	Zeng, J.P. and Xu, H.R. (2008) T-Monotone Mapping and Its Properties. Mathematica Applicata, 21, 288-292.
[18]	Xu, H.R. (2011) An Additive Schwarz Algorithm for NCP with a T-Monotone Function. Journal of Jiaying University, 29, 15-17.