Tensor Complementarity Problems—Part II: Solution Methods

Abstract

This work, with its three parts, reviews the state-of-the-art of studies for the tensor complementarity problem and some related models. In the first part of this paper, we have reviewed the theoretical developments of the tensor complementarity problem and related models. In this second part, we review the developments of solution methods for the tensor complementarity problem. It has been shown that the tensor complementarity problem is equivalent to some known optimization problems, or related problems such as systems of tensor equations, systems of nonlinear equations, and nonlinear programming problems, under suitable assumptions. By solving these reformulated problems with the help of structures of the involved tensors, several numerical methods have been proposed so that a solution of the tensor complementarity problem can be found. Moreover, based on a polynomial optimization model, a semidefinite relaxation method is presented so that all solutions of the tensor complementarity problem can be found under the assumption that the solution set of the problem is finite. Further applications of the tensor complementarity problem will be given and discussed in the third part of this paper.

1 Introduction

In the 1st part of this paper [1], we reviewed some theoretical developments of the tensor complementarity problem (TCP), in which we can see that many theoretical results for the TCP are extensions of those obtained in the linear complementarity problem (LCP) and that they are not covered by those achieved in the general nonlinear complementarity problem (NCP).

Undoubtedly, one of the central tasks is to develop numerical methods to solve the TCP. On the one hand, it is known that the TCP is an extension of the LCP and that the solution methods of LCPs depend heavily on the linearity of the involved function and the special structure of the involved matrix. Since the function involved in the TCP is nonlinear and the structure of the involved tensor is far more complex than that of the matrix, the design and analysis of algorithms for TCPs are different from those for LCPs. On the other hand, since the TCP is a subclass of the NCP, solution methods for the NCP are applicable to the TCP, if required conditions are satisfied. However, since the function involved in the TCP is a special class of polynomials defined by a tensor, one may expect to design effective methods for the TCP by making use of the structure of the involved tensor. Recently, several methods for the TCP have been proposed. In this 2nd part, we review these methods for the TCP.

It was proved that the TCP is equivalent to several systems of tensor equations under appropriate conditions (see [2,3,4,5,6]). By solving these systems of tensor equations, several numerical methods for solving the TCP were developed, including solution methods based on systems of tensor equations (see [2,3,4]), potential reduction methods [7], and homotopy continuation methods [6]. These numerical methods will be reviewed in Sect. 3.

It was proved that the TCP is equivalent to several systems of nonlinear equations in terms of some NCP-function or the modulus-based reformulation (see [8, 9]). By solving these reformulated systems of nonlinear equations, several numerical methods for solving the TCP were developed, including smoothing Newton method [8] and modulus-based methods [9]. These numerical methods will be reviewed in Sect. 4.

It was proved that the TCP could be solved by several nonlinear programming problems [4, 10]. One of them is to solve a finite number of lower-dimensional polynomial optimization problems so that the least solution of the TCP is obtained [4], and the other is to solve a reformulated mixed integer programming, by which one can obtain either a solution of the TCP, or a certificate which implies that the TCP has no solution [10]. These numerical methods will be reviewed in Sect. 5.

Under the assumption that the TCP has finite number of solutions, a semidefinite relaxation method was proposed to solve several polynomial optimization problems with the objectives being random polynomials and the constraints being the solution set of the TCP and some additional inequality constraints of polynomials, so that all solutions of the TCP can be found [11]. We will review such an approach in Sect. 6.

Some perspectives and open problems are given in Sect. 7, and conclusions in Sect. 8.

2 Preliminaries

We would like to point out that all related notations used in this part are the same as those in the 1st part of this paper [1]. Moreover, we also use the following notations. For any two vectors x and y, we use (x, y) to denote $(x^\top ,y^\top )^\top$ for simplicity. For any $x\in {\mathbb {R}}^n$, we use $\hbox {diag}(x)$ to denote the diagonal matrix whose (i, i)th entry is $x_i$ for all $i\in [n]$. For any index set I, we use |I| to denote its cardinality. For any vector $x\in {\mathbb {R}}^n$, tensor ${\mathscr {A}}\in {\mathbb {R}}^{[m,n]}$, and index set $I\subset [n]$, $x_I$ denotes the subvector of x whose components are $x_i$ for $i\in I$, and ${\mathscr {A}}_I$ denotes the principal subtensor of ${\mathscr {A}}$ of order m dimension |I|, which is defined by ${\mathscr {A}}_{I}:=(a_{i_1i_2\ldots i_m})$ for all $i_1,i_2,\ldots ,i_m\in I$.

Suppose that $F: {\mathbb {S}}\subseteq {\mathbb {R}}^n\rightarrow {\mathbb {R}}^n$ is a locally Lipschitz function, where the set ${\mathbb {S}}$ is nonempty and open. By Rademacher’s Theorem, it holds that F is differentiable almost everywhere in the sense of the Lebesgue measure on ${\mathbb {R}}^n$ [12, 13]. Let ${\mathbb {D}}_F\subseteq {\mathbb {R}}^n$ denote the set of points at which F is differentiable. For any $x\in {\mathbb {D}}_F$, we denote the Jacobi matrix of F at x by $F^\prime (x)$. The B-subdifferential of F at x is defined by

$$\begin{aligned} \partial _BF(x):=\left\{ V\in {\mathbb {R}}^{[2,n]}: \exists \{x^k\}\subseteq {\mathbb {D}}_F\; \hbox { with}\; x^k\rightarrow x\;\hbox { and}\; F^\prime (x^k)\rightarrow V\right\} . \end{aligned}$$

The generalized Jacobian of the function F at x in the sense of Clarke [14] is defined by $\partial F(x)=\hbox { co}\{\partial _BF(x)\}$, where “co” denotes the convex hull. Furthermore, the function $F: {\mathbb {S}}\subseteq {\mathbb {R}}^n\rightarrow {\mathbb {R}}^n$ is called to be semismooth at x, iff it is locally Lipschitz at x and $\lim _{V\in \partial F(x+t{\hat{d}}),{\hat{d}}\rightarrow d, t\rightarrow 0^+}V{\hat{d}}$ exists for any $d\in {\mathbb {R}}^n$ [15,16,17].

Recall that the TCP is to find a vector $x\in {\mathbb {R}}^n$ such that

$$\begin{aligned} x\ge 0,\quad {\mathscr {A}}x^{m-1}+q\ge 0, \quad \mathrm {and} \quad x^\top ({\mathscr {A}}x^{m-1}+q)=0, \end{aligned}$$

(1)

where ${\mathscr {A}}\in {\mathbb {R}}^{[m,n]}$ and $q\in {\mathbb {R}}^n$ are given. We denote it by the TCP$({\mathscr {A}},q)$. Obviously, it can be equivalently written as: Find a vector $(x,y)\in {\mathbb {R}}^n\times {\mathbb {R}}^n$ such that

$$\begin{aligned} x\ge 0,\quad y={\mathscr {A}}x^{m-1}+q\ge 0, \quad \mathrm {and} \quad x^\top y=0 \end{aligned}$$

(2)

in the sense that $x\in {\mathbb {R}}^n$ solves the TCP$({\mathscr {A}},q)$ (1) if and only if there exists $y\in {\mathbb {R}}^n$ such that $(x,y)\in {\mathbb {R}}^n\times {\mathbb {R}}^n$ solves (2).

3 Solution Methods for the TCP Based on Reformulated Tensor Equations

In this section, we describe several methods for solving the TCP with the help of some approaches for solving systems of tensor equations.

3.1 Methods Based on Systems of Tensor Equations

Recall that a tensor ${\mathscr {A}}=(a_{i_1i_2\ldots i_m})\in {\mathbb {R}}^{[m,n]}$ is said to be a Z-tensor, iff all its off-diagonal entries are non-positive. Luo et al. [2] considered the TCP$({\mathscr {A}},q)$ with ${\mathscr {A}}$ being a Z-tensor and q being a non-positive vector and showed that it is equivalent to a system of tensor equations with nonnegative constraints.

Theorem 3.1

[2, Corollary 2] Let ${\mathscr {A}}\in {\mathbb {R}}^{[m,n]}$ be a Z-tensor and $-q\in {\mathbb {R}}^n_+$. Then, the following two statements are equivalent.

• (a) $x\in {\mathbb {R}}^n_+,\; {\mathscr {A}}x^{m-1}+q\in {\mathbb {R}}^n_+$, and $x^\top ({\mathscr {A}}x^{m-1}+q)=0$.

• (b) $x\in {\mathbb {R}}^n_+$ and ${\mathscr {A}}x^{m-1}+q=0$.

Theorem 3.1 demonstrates that, when ${\mathscr {A}}$ is a Z-tensor and $-q\in {\mathbb {R}}^n_+$, an arbitrary method of finding nonnegative solutions of ${\mathscr {A}}x^{m-1}+q=0$ can be employed in order to obtain a solution to the TCP$({\mathscr {A}},q)$ (1). Furthermore, when ${\mathscr {A}}$ is a strong M-tensor, i.e., ${\mathscr {A}}=\tau {\mathscr {I}}-{\mathscr {B}}$ where $\tau \in {\mathbb {R}}$, ${\mathscr {I}}$ is the unit tensor, ${\mathscr {B}}$ is a nonnegative tensor, and $\tau >\rho ({\mathscr {B}})$ with $\rho ({\mathscr {B}})$ being the spectral radius of ${\mathscr {B}}$, Ding and Wei [18] proved that ${\mathscr {A}}x^{m-1}+q=0$ has a unique nonnegative solution if $-q\in {\mathbb {R}}^n_+$, and proposed several approaches to find such a solution. Thus, the methods proposed in [18] can be employed to obtain a solution to the TCP$({\mathscr {A}},q)$ (1) with ${\mathscr {A}}$ being a strong M-tensor and $-q\in {\mathbb {R}}^n_+$.

Recall that a solution $x^*$ of the TCP$({\mathscr {A}},q)$ (1) is strictly complementary, iff

$$\begin{aligned} x^*+y^*>0, \end{aligned}$$

where $y^*:={\mathscr {A}}(x^*)^{m-1}+q$. In [3], Xu et al. showed the following result.

Theorem 3.2

[3, Theorem 2.4] Let ${\mathscr {A}}\in {\mathbb {R}}^{[m,n]}$ be a positive semidefinite Z-tensor and $q\in {\mathbb {R}}^n$. Suppose that there is a solution of the TCP$({\mathscr {A}},q)$ which is strictly complementary. Then, the TCP$({\mathscr {A}},q)$ is equivalent to the system of tensor equations:

$$\begin{aligned} {\mathscr {A}}_Ix_I^{m-1}+q_I=0_I\quad \hbox { and}\quad x_J=0_J, \end{aligned}$$

(3)

where $I:=\{i\in [n]: q_i\le 0\}$ and $J:=\{i\in [n]: q_i>0\}$.

When all the assumptions of Theorem 3.2 are satisfied, the TCP$({\mathscr {A}},q)$ (1) can be solved by the system of tensor equations (3). Generally, the equivalent system of equations (3) to the TCP$({\mathscr {A}},q)$ (1) is lower dimensional unless $q\le 0$. When ${\mathscr {A}}$ is a strong M-tensor, the system of equations (3) can be solved by the numerical methods proposed by Ding and Wei [18].

Recall that a tensor ${\mathscr {A}}\in {\mathbb {R}}^n$ is said to be strongly monotone over $K\subseteq {\mathbb {R}}^n$, iff

$$\begin{aligned} {\mathscr {A}}(x^{m-1}-y^{m-1})\ge 0\quad \Longleftrightarrow \quad x\ge y,\quad \forall x,y\in K. \end{aligned}$$

If $K={\mathbb {R}}^n$, then ${\mathscr {A}}$ is said to be strongly monotone (see [4, Definition 2.5]). Xie et al. [4] considered the TCP$({\mathscr {A}},q)$ with ${\mathscr {A}}$ being a strongly monotone Z-tensor, and showed that it can be solved by finitely many systems of lower-dimensional tensor equations. In fact, this method is to find the least solution of the TCP whose definition is given as follows.

Definition 3.1

[4, Definition 2.4] Let the feasible set of the TCP (1) be denoted by

$$\begin{aligned} {\mathscr {F}}({\mathscr {A}},q):=\left\{ x\in {\mathbb {R}}^n_+: F(x):={\mathscr {A}}x^{m-1}+q\ge 0\right\} . \end{aligned}$$

(4)

A vector ${\bar{x}}\in {\mathscr {F}}({\mathscr {A}},q)$ is said to be the least element of ${\mathscr {F}}({\mathscr {A}},q)$, iff ${\bar{x}}\le x$ holds for all $x\in {\mathscr {F}}({\mathscr {A}},q)$. Furthermore, ${\bar{x}}$ is said to be the least solution to the TCP$({\mathscr {A}},q)$ (1), iff it is the least element of ${\mathscr {F}}({\mathscr {A}},q)$ and a solution to the TCP$({\mathscr {A}},q)$ (1).

Suppose that index sets I and J are a partition of [n], which means that $I\bigcap J=\emptyset$ and $I\bigcup J=[n]$. Let $x\in {\mathbb {R}}^n$ and P(I, J) denote the following system of equations:

$$\begin{aligned} F_I(x):=({\mathscr {A}}x^{m-1}+q)_I=0\quad \hbox { and}\quad x_J=0. \end{aligned}$$

(5)

If ${\bar{x}}\in {\mathbb {R}}^n$ solves P(I, J) given by (5), and satisfies ${\bar{x}}_I\ge 0$ and $F_J({\bar{x}})\ge 0$, then ${\bar{x}}$ solves the TCP$({\mathscr {A}},q)$ (1). Moreover, it is obvious from Definition 3.1 that if the least solution to the TCP exists, then it is unique. The specific algorithm is given as follows.

Algorithm 3.1

(A sequential tensor equations method) [4, Algorithm 1]

Step 0:

Set the initial index sets $I_0:=\{i\in [n]: q_i<0\}$ and $J_0:=[n]\setminus I_0$. Stop if $I_0=\emptyset$ ($x=0$ is a solution to (1)). Otherwise, set $k:=0$.

Step 1:

Solve the lower-dimensional tensor equations $P(I_k,J_k)$ to get $x^k$.

Step 2:

Stop if $F_{J_k}(x^k)\ge 0$. Otherwise, let

$$\begin{aligned} I_{k+1}:=I_k\bigcup \{i\in J_k: F_i(x^k)<0\}\quad \hbox { and}\quad J_{k+1}:=[n]\setminus I_{k+1}. \end{aligned}$$

Step 3:

Let $k:=k+1$. Go to Step 1.

The convergence of Algorithm 3.1 is given as follows.

Theorem 3.3

[4, Theorem 2.1] Let ${\mathscr {A}}\in {\mathbb {R}}^{[m,n]}$ be a strongly monotone Z-tensor, and the sequence $\{x^k\}$ be generated by Algorithm 3.1. Then, $\{x^k\}$ is finite and monotone, and the last point of the sequence is the least solution to the TCP$({\mathscr {A}},q)$ (1).

It should be pointed out that only finitely many systems of lower-dimensional tensor equations need to be solved in order to achieve the least solution to the TCP (1).

Remark 3.1

In this subsection, we reviewed three methods to solve the TCP (1) by solving systems of equations in the form of ${\mathscr {A}}x^{m-1}+q=0$. In fact, in recent years, the system of equations ${\mathscr {A}}x^{m-1}+q=0$ has attracted a lot of attention, and a large number of numerical methods have been proposed [18,19,20,21,22,23,24,25,26,27]. It is possible that the methods in [18,19,20,21,22,23,24,25,26,27] provide potential approaches for solving the TCP (1).

3.2 Potential Reduction Methods

Throughout this subsection, we assume that ${\mathscr {A}}\in {\mathbb {R}}^{[m,n]}$ is symmetric.

The potential reduction method is an important kind of interior point methods (IPMs), which is based on reducing a suitable potential function at each iteration. It has been successfully applied to solve linear programming, the LCP, and some nonlinear optimization (see [5, 28]). In this subsection, we describe a potential reduction method for solving the TCP, which was proposed by Zhang et al. [7].

For any $x\in {\mathbb {R}}^n$, let $X:=\hbox { diag}(x)$ and

$$\begin{aligned} H(x,y):=\left( \begin{array}{l} Xy \\ y-({\mathscr {A}}x^{m-1}+q) \end{array}\right) =0, \quad x,y\in {\mathbb {R}}^n_{+}. \end{aligned}$$

(6)

Then, $(x,y)\in {\mathbb {R}}^n\times {\mathbb {R}}^n$ solves (6) if and only if it solves the TCP$({\mathscr {A}},q)$. Thus, one may solve (6) to obtain a solution of the TCP$({\mathscr {A}},q)$. The IPM is an iterative method which solves (6), where, in each iteration, a Newton-type equation for $H(x,y)=0$ is solved and the iterative point (x, y) satisfies $(x,y)\in {\mathbb {R}}^n_{++}\times {\mathbb {R}}^n_{++}$, until some stopping criteria are met.

Before the detailed description of the algorithm, we point out the following three issues.

• First, for an IPM, if each iterative point (x, y) satisfies $y={\mathscr {A}}x^{m-1}+q$ besides $(x,y)\in {\mathbb {R}}^n_{++}\times {\mathbb {R}}^n_{++}$, then it is called a feasible IPM; otherwise, it is called an infeasible IPM. Since ${\mathscr {A}}x^{m-1}$ is nonlinear, it is generally difficult to keep the feasibility (i.e., $y={\mathscr {A}}x^{m-1}+q$ with $(x,y)\in {\mathbb {R}}^n_{++}\times {\mathbb {R}}^n_{++}$) at each iteration. Thus, we’ll consider an infeasible IPM for the TCP$({\mathscr {A}},q)$ where all iterative points are desired to lie in the set $\varOmega _{++}$ defined by

  $$\begin{aligned} \varOmega _{++}:=\{(x,y)\in {\mathbb {R}}^n_{++}\times {\mathbb {R}}^n_{++}: \Vert y-({\mathscr {A}}x^{m-1}+q)\Vert _\infty <\varepsilon \}, \end{aligned}$$

  where $\varepsilon >0$ is a small tolerance.

• Second, it is well known that, for IPMs, one of the basic issues is the invertibility of the Jacobi matrix of the reformulated function $H(\cdot ,\cdot )$. Let $H^\prime (x,y)$ denote the Jacobi matrix of H(x, y) at $(x,y)\in {\mathbb {R}}^n\times {\mathbb {R}}^n$. Then

  $$\begin{aligned} H^\prime (x,y)=\left( \begin{array}{ll} Y &{}\quad X \\ -(m-1){\mathscr {A}}x^{m-2} &{}\quad I \end{array}\right) , \end{aligned}$$

  where $X:=\hbox { diag}(x)$ and $Y:=\hbox { diag}(y)$. Recall that a symmetric tensor ${\mathscr {A}}\in {\mathbb {R}}^{[m,n]}$ is called diagonalizable [29], iff ${\mathscr {A}}={\mathscr {D}}\times _1 B\times _2 B\times _3 \cdots \times _m B$ where $B\in {\mathbb {R}}^{[2,m]}$ with det$(B)\ne 0$, ${\mathscr {D}}$ is a diagonal tensor, and $\times _i$ denotes the mode-i product; and that ${\mathscr {A}}$ is called positive definite, iff ${\mathscr {A}}x^m>0$ for all $x\in {\mathbb {R}}^n\setminus \{0\}$. It was proved in [7, Theorem 3.2] that $H^\prime (x,y)$ is nonsingular for any $(x,y)\in {\mathbb {R}}^n_{++}\times {\mathbb {R}}^n_{++}$, if ${\mathscr {A}}\in {\mathbb {R}}^{[m,n]}$ is diagonalizable and positive definite.

• Third, the IPM we’ll consider here is a potential reduction method which is based on the following potential function:

  $$\begin{aligned} \phi (z):=(n+s)\hbox { ln}[x^\top y+\Vert y-{\mathscr {A}}x^{m-1}-q\Vert ^2_2]-\sum _{i=1}^n\hbox { ln}x_iy_i, \end{aligned}$$

  where $z:=(x,y)$ and $s>0$ is a parameter. Such a function has been used in several potential reduction methods (see [30,31,32,33]).

Algorithm 3.2

(A potential reduction method) [7, Algorithm 1]

Step 0:

(Initialization) Let $s>0, \varepsilon>0, \alpha \in (0,1), {\bar{\beta }}\in [0,1), \sigma >0$, and $\rho \in (0,1)$ be given. Choose any $z^0:=(x^0,y^0)\in \varOmega _{++}$ and $\beta _0\in [0,{\bar{\beta }})$. Set $k:=0$.

Step 1:

(Direction generation) Solve the system of equations

$$\begin{aligned} \left( \begin{array}{ll} Y^k &{}\quad X^k \\ -(m-1){\mathscr {A}}(x^k)^{m-2} &{}\quad I \end{array}\right) \left( \begin{array}{l} \varDelta x^k \\ \varDelta y^k \end{array}\right) =\left( \begin{array}{l} -X^ky^k+\beta \frac{(x^k)^\top y^k}{n}e \\ -y^k+{\mathscr {A}}(x^k)^{m-1}+q \end{array}\right) \end{aligned}$$

to obtain the search direction $d^k:=(\varDelta x^k,\varDelta y^k)$, where e is the vector of all ones.

Step 2:

(Stepsize determination) Let $l_k$ be the smallest nonnegative integer l such that the following two conditions hold:

$$\begin{aligned} z^k+\sigma \rho ^l d^k\in \varOmega _{++}\quad \hbox { and}\quad \phi (z^k+\sigma \rho ^l d^k)-\phi (z^k)\le -\alpha \sigma \rho ^l(1-\beta _k)s. \end{aligned}$$

Set $z^{k+1}=z^k+\sigma \rho ^{l^k}d^k$.

Step 3:

(Termination verification) If $z^{k+1}$ satisfies

$$\begin{aligned} f(z^{k+1})=(x^{k+1})^\top y^{k+1}+\Vert y^{k+1}-{\mathscr {A}}(x^{k+1})^{m-1}-q\Vert ^2<\varepsilon , \end{aligned}$$

then $z^{k+1}$ is an approximation solution of the TCP$({\mathscr {A}},q)$; else if

$$\begin{aligned} z^{k+1}-z^k<\varepsilon \quad \hbox { and}\quad \hbox { ln}x_j^{k+1}y_j^{k+1}=0\; \hbox { for some}\; j\in [n], \end{aligned}$$

then $z^{k+1}$ is an approximation solution; otherwise, pick any $\beta _{k+1}\in [0,{\bar{\beta }}]$ and return to Step 1 with $k=k+1$.

It was proved in [7, Theorems 4.1–4.3] that Algorithm 3.2 is well defined. Furthermore, the convergence of Algorithm 3.2 can be found in [7, Theorem 4.6], which is given as follows.

Theorem 3.4

Suppose that ${\mathscr {A}}\in {\mathbb {R}}^{[m,n]}$ is diagonalizable and positive definite, and the sequence $\{z^k\}$ is generated by Algorithm 3.2. Then, the sequence $\{z^k\}$ is bounded and every accumulation point of $\{z^k\}$ is a solution of the $\hbox { TCP}({\mathscr {A}},q)$ (2).

Remark 3.2

In this subsection, we reviewed a potential reduction method to solve the TCP, which possesses the global convergence under suitable assumptions. In fact, a key issue in the field of IPMs is to investigate the polynomial complexity of algorithms. Thus, it is an important issue to study the polynomial complexity of IPMs for solving TCPs. It is known that the IPM is a large class of methods which is very successful for solving various optimization problems, and it contains affine scaling methods and path-following methods besides potential reduction methods. In all kinds of IPMs, the primal-dual path-following IPM is one of the most popular methods. Thus, more effective IPMs for the TCP need to be further studied.

3.3 Homotopy Continuation Methods

Homotopy continuation methods form an important class of methods for solving complementarity problems (see [34,35,36,37,38]), and they have been successfully developed for solving tensor eigenvalue problems [39] and systems of tensor equations [20]. In the following, we describe a homotopy continuation method for the TCP proposed by Han [6], which is based on a Kojima–Megiddo–Mizuno [36]-type homotopy mapping $H: [0,1]\times {\mathbb {R}}^{2n}\rightarrow {\mathbb {R}}^{2n}$ defined by

$$\begin{aligned} H(t,x,y):=\left( \begin{array}{l} Xy-ta \\ y-(1-t)({\mathscr {A}}x^{m-1}+q)-tb \end{array}\right) , \end{aligned}$$

where $X:=\hbox { diag}(x)$, and $a\in {\mathbb {R}}^n_{+}$ and $b\in {\mathbb {R}}^n_{++}$ are two known vectors.

Starting with $t=1$ and $(x^0,y^0):=(B^{-1}a,b)$, where $B=\hbox { diag}(b)$, the homotopy continuation method follows a path from $t=1$ to $t=0$ by solving the system

$$\begin{aligned} H(t,x,y)=0,\quad \forall (x,y)\ge 0. \end{aligned}$$

(7)

In order to ensure the boundedness of the homotopy trajectory of the continuation method for solving the NCP, several conditions were proposed in [34,35,36,37,38], which were summarized to Conditions 1–3 in [6]. However, it was illustrated in [6] that these conditions are not satisfied when ${\mathscr {A}}\in {\mathbb {R}}^{[m,n]}$ is strictly semi-positive.

Furthermore, in order to ensure that the homotopy system (7) yields a specific trajectory, it is sufficient if the Jacobi matrix of H(t, x, y) with respect to (x, y) is invertible. This can be guaranteed when ${\mathscr {A}}\in {\mathbb {R}}^{[m,n]}$ is strong strictly semi-positive (i.e., $\max _{i\in [n]}(x_i-y_i)[({\mathscr {A}}x^{m-1})_i-({\mathscr {A}}y^{m-1})_i]>0$ for any distinct $x,y\in {\mathbb {R}}^n_+$). Note that the partial derivatives of the homotopy mapping H(t, x, y) can be given by

$$\begin{aligned} D_{t}H(t,x,y)= & {} \left( \begin{array}{l} -a \\ {\mathscr {A}}x^{m-1}+q-b \end{array}\right) ;\\ D_{(x,y)}H(t,x,y)= & {} \left( \begin{array}{ll} Y &{}\quad X \\ -(1-t)(m-1)\hat{{\mathscr {A}}}x^{m-2} &{}\quad I_n \end{array}\right) , \end{aligned}$$

where $\hat{{\mathscr {A}}}=\frac{1}{p}\sum _{k=1}^p{\mathscr {A}}_{i_1i_2^{(k)}\ldots i_m^{(k)}}$, where the sum is over all the p different permutations $i_2^{(k)},\ldots , i_m^{(k)}$ of $i_2,\ldots ,i_m$. The following results hold true.

Theorem 3.5

[6, Theorem 2.3] Let $a\in {\mathbb {R}}^n_{++}$. Suppose that ${\mathscr {A}}\in {\mathbb {R}}^{[m,n]}$ is a strong strictly semi-positive tensor and $q\in {\mathbb {R}}^n$. Then, for almost every $b\in {\mathbb {R}}^n_{++}$, solving the system (7) yields a smooth and bounded trajectory

$$\begin{aligned} T=\{(t,x(t),y(t)): 0<t\le 1\}\subset (0,1]\times {\mathbb {R}}^n_{+}\times {\mathbb {R}}^n_{+}. \end{aligned}$$

Moreover, tracing this trajectory, the solution of the initial value problem:

$$\begin{aligned} D_{z}H(t,z)\frac{\hbox {d}z}{\hbox {d}t}=-D_{t}H(t,z),\;\; z(1)=(x^0,y^0), \quad \hbox { where}\; z:=(x,y), \end{aligned}$$

converges to the unique solution $(x^*,y^*)$ of the TCP$({\mathscr {A}},q)$ (2) as $t\rightarrow 0$.

A specific algorithm was proposed as follows.

Algorithm 3.3

(An Euler–Newton predictor–corrector method) [6, Algorithm 3.1]

Step 0:

Choose $a,b\in {\mathbb {R}}^n_{++}$. Choose initial step size $\varDelta t^0>0$, tolerance $\varepsilon _1>0$ and $\varepsilon _2>0$. Let $t^0=1$, $x^0=B^{-1}a$, $y^0=b$. Let $z=(x,y)$ and $z^0=(x^0,y^0)$. Set $k:=0$.

Step 1:

Set $t^{k+1}=t^k-\varDelta t^k$. If $t^k>0$ and $t^{k+1}\le 0$ for some k, then set $N=k$ and reset $t^{N+1}=0$ and $\varDelta t^N=t^N$.

Step 2:

Compute the tangent vector g to $H(t,z)=0$ at $t^k$ by solving the linear system $D_zH(t^k,z^k)g=-D_tH(t^k,z^k)$ for g. Then compute the approximation ${\tilde{z}}$ to $z^{k+1}$ by ${\tilde{z}}=z^k+\varDelta t^kg$.

Step 3:

Initialize $w^0={\tilde{z}}$. For $i=1,2,\ldots$, compute

$$\begin{aligned} w^{i+1}=w^i-[D_zH(t^{k+1},w^i)]^\dag H(t^{k+1},w^i) \end{aligned}$$

until $\Vert H(t^{k+1},w^J)\Vert \le \varepsilon _1$ if $k<N$, or $\Vert H(t^{k+1},w^J)\Vert \le \varepsilon _2$ if $k=N$, where $^\dag$ denotes the pseudo-inverse. Then let $z^{k+1}=w^J$. If $k=N$, set $(x^*,y^*)=z^{N+1}$ as the computed solution of problem (6) and stop.

Step 4:

If more than three steps of Newton iterations were required to converge within the desired accuracy, then $\varDelta t^{k+1}=0.5\varDelta t^k$. If $\varDelta t^{k+1}\le 10^{-6}$, set $\varDelta t^{k+1}=10^{-6}$. If two consecutive steps were not cut, then $\varDelta t^{k+1}=2\varDelta t^k$. If $\varDelta t^{k+1}\ge 0.5$, set $\varDelta t^{k+1}=0.5$. Otherwise, $\varDelta t^{k+1}=\varDelta t^k$. Set $k:=k+1$. Go to Step 1.

Remark 3.3

In this subsection, we reviewed a homotopy continuation method for the TCP based on a Kojima–Megiddo–Mizuno type homotopy mapping. It is known that various homotopy methods have been successfully designed to solve the complementarity and related problems. Thus, by making use of structures of the involved tensors, it is possible that more effective homotopy methods for the TCP can be proposed.

4 Solution Methods for the TCP Based on Reformulated Nonlinear Equations

In this section, we describe several methods for solving the TCP with the help of some approaches for solving some reformulated systems of nonlinear equations.

4.1 Methods for the TCP Based on Smoothing Reformulations

It is well known that an NCP can be equivalently reformulated as a system of non-smooth equations by using some NCP-function [40, 41]. In order to overcome the difficulty caused by the non-smoothness of the NCP-function, replacing the NCP-function by its smooth approximation function, the NCP can be reformulated as a system of parameterized smooth equations. Thus, the NCP can be solved by applying the reformulated smooth equations by the Newton method iteratively, and making the smooth approximation function tend to the original one, which is called the smoothing Newton method [42,43,44,45,46,47,48].

We use the following function:

$$\begin{aligned} \phi _{FB}^\mu (a,b)=a+b-\sqrt{a^2+b^2+\mu ^2},\quad \forall a,b\in {\mathbb {R}} \end{aligned}$$

which is the smooth approximation of the Fischer–Burmeister function [49]. Let

$$\begin{aligned} H(\mu ,x,y):=\left( \begin{array}{l} \mu \\ y-({\mathscr {A}}x^{m-1}+q) \\ \phi _{FB}^\mu (x_1,y_1) \\ \vdots \\ \phi _{FB}^\mu (x_n,y_n) \end{array}\right) . \end{aligned}$$

It is easy to see that the function $H(\mu ,x,y)$ is continuously differentiable at any $(\mu ,x,y)\in {\mathbb {R}}_{++}\times {\mathbb {R}}^n\times {\mathbb {R}}^n$, and $H(\mu ,x,y)=0$ if and only if $\mu =0$ and (x, y) solves the TCP$({\mathscr {A}},q)$ (2). Thus, we may apply some Newton-type method to solve the smoothing equations $H(\mu ,x,y)$ = 0 at each iteration and make $H(\mu ,x,y)\rightarrow 0$ so that a solution of the TCP$({\mathscr {A}},q)$ (2) can be found.

Algorithm 4.1

(A smoothing Newton method) [8, Algorithm 5.1]

Step 0:

Choose $\delta , \sigma \in (0,1)$, $\mu _0>0$, and $(x^0,y^0)\in {\mathbb {R}}^{2m}$. Set $z^0:=(\mu _0,x^0,y^0)$. Choose $\beta >1$ such that $\Vert H(z^0)\Vert \le \beta \mu _0$. Set $\hbox {e}^0:=(1,0,\ldots ,0)\in {\mathbb {R}}^{1+2m}$ and $k:=0$.

Step 1:

If $\Vert H(z^k)\Vert =0$, stop.

Step 2:

Compute $\varDelta z^k:=(\varDelta \mu _k,\varDelta x^k,\varDelta s^k)\in {\mathbb {R}}\times {\mathbb {R}}^m \times {\mathbb {R}}^{m}$ by

$$\begin{aligned} H(z^k)+ H^\prime (z^k)\varDelta z^k=(1/\beta ) \Vert H(z^k)\Vert \hbox {e}^0. \end{aligned}$$

Step 3:

Let $\lambda _k$ be the maximum of the values $1,\delta ,\delta ^2,\ldots$ such that

$$\begin{aligned} \Vert H(z^k+\lambda _k\varDelta z^k)\Vert \le [1-\sigma (1-1/\beta )\lambda _k]\Vert H(z^k)\Vert . \end{aligned}$$

Step 4:

Set $z^{k+1}:=z^k+\lambda _k\varDelta z^k$ and $k:=k+1$. Go to Step 1.

The related algorithmic framework was proposed in [50]. It follows that Algorithm 4.1 is globally convergent if $(x-y)^\top ({\mathscr {A}}x^{m-1}-{\mathscr {A}}y^{m-1})\ge 0$ for any $x,y\in {\mathbb {R}}^n$.

Remark 4.1

The smoothing Newton method is a powerful tool for solving complementarity and related problems, and a large number of smoothing Newton methods have been proposed in the literature. In order to use smoothing Newton methods to solve the TCP effectively, the structures of the tensors involved need to be thoroughly dissected. It is worthy of investigating various smoothing Newton methods by making use of special structures of the tensors involved.

Moreover, by using a reformulation based on the Fischer–Burmeister function, a gradient dynamic approach for solving the TCP was proposed in [51].

4.2 Methods for the TCP Based on the Modulus-Based Reformulation

Recently, Liu et al. [9] proposed an approach to solve the TCP based on a modulus-based reformulation.

Theorem 4.1

[9, Theorem 4.3] $|x|+x\in {\mathbb {R}}^n$ is a solution of the TCP$({\mathscr {A}},q)$ (1) if and only if $x\in {\mathbb {R}}^n$ is a solution of the system of equations: $x=|x|-{\mathscr {A}}(|x|+x)^{m-1}-q$, where $|x|=(|x_1|,|x_2|,\ldots ,|x_n|)^\top \in {\mathbb {R}}^n$.

Thus, the TCP$({\mathscr {A}},q)$ (1) can be solved in terms of some effective approaches for solving the system of equations $x=|x|-{\mathscr {A}}(|x|+x)^{m-1}-q$. In the following, we describe a non-smooth Newton method given in [9].

Suppose that ${\mathscr {A}}\in {\mathbb {R}}^{[m,n]}$ is semi-symmetric, i.e., it is symmetric on the last $m-1$ indices. Since $\partial |x|=\hbox { diag}\{\partial |x_1|,\partial |x_2|,\ldots ,\partial |x_n|\}$ where

$$\begin{aligned} \partial |x_i|\left\{ \begin{array}{ll} =-1, &{}\quad \hbox { if}\quad x_i<0,\\ \in [-1,1], &{}\quad \hbox { if}\quad x_i=0,\\ =1, &{}\quad \hbox { if}\quad x_i>0, \end{array}\right. \quad \forall i\in [n], \end{aligned}$$

if we denote $H(x):=x-|x|+{\mathscr {A}}(|x|+x)^{m-1}+q$ for all $x\in {\mathbb {R}}^n$, then the generalized Jacobi matrix of H(x) is given by $\partial H(x)=(I+\Psi (x))+(\Psi (x)-I)\partial |x|$, where I is the identity matrix and $\Psi (x):=(m-1){\mathscr {A}}(|x|+x)^{m-2}$ and

$$\begin{aligned} ({\mathscr {A}}z^{m-2})_{ij}=\sum _{i_3,\ldots ,i_m=1}^na_{iji_3\ldots i_m}z_{i_3}\ldots z_{i_m},\quad \forall i,j\in [n], \forall z\in {\mathbb {R}}^n. \end{aligned}$$

The following non-smooth Newton method is a slight modification of Algorithm 4.5 proposed in [9].

Algorithm 4.2

(A modulus-based non-smooth Newton method)

Step 0:

Given ${\mathscr {A}}\in {\mathbb {R}}^{[m,n]}$, $q\in {\mathbb {R}}^n$, and an initial vector $x^0$. Set $k:=0$.

Step 1:

If $\Vert H(x^{k})\Vert =0$, output $x=|x^{k}|+x^{k}$, stop.

Step 2:

Take $V^k\in \partial H(x^k)$; and solve $V^k\bigtriangleup x^{k}=-H(x^k)$ to obtain $\bigtriangleup x^{k}$.

Step 3:

Let $x^{k+1}:=x^k+\bigtriangleup x^{k}$.

Step 4:

Let $k:=k+1$. Go to Step 1.

Using methods given in [9, Corollary 4.11], we can obtain the convergence of Algorithm 4.2.

Theorem 4.2

Let ${\mathscr {A}}\in {\mathbb {R}}^{[m,n]}$ be a strongly semi-positive tensor and the sequence $\{x^k\}$ be generated by Algorithm 4.2. If for every $x^k$, ${\mathscr {A}}(|x^k|+x^k)^{m-2}$ is a P-matrix, then Algorithm 4.2 is well defined and convergent to the unique solution $x^*$ in a neighborhood of $x^*$ quadratically.

Remark 4.2

The LCP has been well studied by using its modulus-based reformulation [52,53,54,55], and these studies provide important resources for further research on the TCP.

5 Solution Methods for the TCP Based on Reformulated Programming Problems

In this section, we describe two methods for solving the TCP with the help of some approaches for solving the reformulated mathematical programming problems.

5.1 Methods for the TCP Based on Reformulated Polynomial Optimization

For any $x\in {\mathbb {R}}^n$, let $\Vert x\Vert _0$ denote the number of nonzero components of x. Then, the problem of finding the sparsest solution to the TCP$({\mathscr {A}},q)$ can be modeled as

$$\begin{aligned} \min \Vert x\Vert _0\quad \hbox { s.t.}\quad x\in \hbox {SOL}({\mathscr {A}},q). \end{aligned}$$

(8)

By Definition 3.1, it follows that the least solution of the TCP$({\mathscr {A}},q)$ must be an optimal solution of (8). Thus, in order to find the sparsest solution of the TCP$({\mathscr {A}},q)$, one may find the least solution of the TCP$({\mathscr {A}},q)$. However, since $\Vert \cdot \Vert _0$ is nonconvex and non-smooth, it is a difficult task to solve (8) directly.

In the field of sparse optimization, in order to overcome the difficulties caused by the function $\Vert \cdot \Vert _0$, one replaces $\Vert x\Vert _0$ by $\Vert x\Vert _1$ to obtain a relaxed problem and solves the relaxed problem instead of the original one. In this regard, problem (8) can be relaxed as

$$\begin{aligned} \min \hbox {e}^\top x\quad \hbox { s.t.}\quad x\in \hbox {SOL}({\mathscr {A}},q) \end{aligned}$$

(9)

where e is the vector of all ones. But (9) is still a difficult problem since it contains a complementarity constraint. Fortunately, by Theorem 3.1, such a constraint can be removed when ${\mathscr {A}}$ is a Z-tensor and $-q\in {\mathbb {R}}^n_+$. That is, when ${\mathscr {A}}$ is a Z-tensor and $-q\in {\mathbb {R}}^n_+$, (9) is equivalent to

$$\begin{aligned} \min \hbox {e}^\top x\quad \hbox { s.t.}\quad x\ge 0, {\mathscr {A}}x^{m-1}+q=0. \end{aligned}$$

(10)

Furthermore, Luo et al. [2] showed that if ${\mathscr {F}}({\mathscr {A}},q)\ne \emptyset$ where ${\mathscr {F}}({\mathscr {A}},q)$ is the feasible set of the TCP$({\mathscr {A}},q)$ defined by (4), then ${\mathscr {F}}({\mathscr {A}},q)$ has a unique least element $x^*$, which is also the least solution of the TCP$({\mathscr {A}},q)$ and the unique solution to problem (10). In particular, when ${\mathscr {A}}$ is a strong M-tensor and $-q\in {\mathbb {R}}^n_+$, problem (8) is equivalent to problem (10). Since problem (10) is a polynomial optimization with the linear objective function and homogeneous polynomial equality constraints together with nonnegative constraints, some polynomial optimization methods can be used to solve problem (10), by which one may obtain the least solution of the TCP$({\mathscr {A}},q)$, which is also a sparsest solution of the TCP$({\mathscr {A}},q)$.

In the above method, $-q\in {\mathbb {R}}^n_+$ is required. Such a requirement was removed by Xie et al. [4] based on the following result.

Theorem 5.1

[2, Corollary 1] Let ${\mathscr {A}}\in {\mathbb {R}}^{[m,n]}$ be a Z-tensor and $q\in {\mathbb {R}}^n$. Suppose that the TCP$({\mathscr {A}},q)$ is feasible, i.e., ${\mathscr {F}}({\mathscr {A}},q)\ne \emptyset$. Then, ${\mathscr {F}}({\mathscr {A}},q)$ has a unique least element $x^*$, which is also a solution to the TCP$({\mathscr {A}},q)$ (1).

Suppose that ${\mathscr {A}}\in {\mathbb {R}}^{[m,n]}$ is a Z-tensor, $q\in {\mathbb {R}}^n$, and ${\mathscr {F}}({\mathscr {A}},q)\ne \emptyset$. Then, it follows from Theorem 5.1 that the least solution of the TCP$({\mathscr {A}},q)$ (1) is the unique solution of the following polynomial optimization problem:

$$\begin{aligned} \min p^\top x\quad \hbox { s.t.}\quad x\ge 0, {\mathscr {A}}x^{m-1}+q\ge 0, \end{aligned}$$

(11)

where $p\in {\mathbb {R}}^n$ is an arbitrary positive vector. Thus, we may solve (11) to obtain the least solution of the TCP$({\mathscr {A}},q)$ (1). In fact, we may solve a sequence of polynomial optimization problems in the form of (11).

Let $I\subset [n]$ and $S_I:=\{x_I\in {\mathbb {R}}^{|I|}: x_I\ge 0, {\mathscr {A}}_Ix_I^{m-1}+q_I\ge 0\}$, and consider the following polynomial optimization problem denoted by MP(I):

$$\begin{aligned} \min p_I^\top x_I\quad \hbox { s.t.}\quad x_I\ge 0, {\mathscr {A}}_Ix_I^{m-1}+q_I= 0. \end{aligned}$$

(12)

The following theorem provides a theoretical basis for designing algorithm.

Theorem 5.2

[4, Theorem 3.1] Let I and J be a partition of [n], and let ${\bar{x}}_I$ be the unique solution to the MP(I) (12) that is the least element of $S_I$. Denote ${\bar{x}}:=({\bar{x}}_I,0_J)$,

$$\begin{aligned} I^\prime :=\{i\in J: ({\mathscr {A}}{\bar{x}}^{m-1}+q)_i<0\},\quad {\hat{I}}:=I\bigcup I^\prime ,\quad \hbox { and}\quad {\hat{J}}:=[n]\setminus {\hat{I}}. \end{aligned}$$

• (a) If $I^\prime =\emptyset$, then ${\bar{x}}$ is the least solution to the TCP$({\mathscr {A}},q)$ (1).

• (b) When $I^\prime \ne \emptyset$, we let ${\hat{x}}_{{\hat{I}}}$ be the unique solution to the MP$({\hat{I}})$ and let ${\hat{x}}:=({\hat{x}}_{{\hat{I}}},0_{{\hat{J}}})$. Then, ${\hat{x}}_{{\hat{I}}}$ is the least element of $S_{{\hat{I}}}$, and ${\bar{x}}\le {\hat{x}}$.

Based on Theorem 5.2, an algorithm can be described as follows.

Algorithm 5.1

(A sequential polynomial optimization method) [4, Algorithm 2]

Step 0:

Determine an initial partition $I_0$ and $J_0$ of [n] such that the solution $x_{I_0}^0$ to the MP$(I_0)$ is the least solution to the TCP$({\mathscr {A}}_{I_0},q_{I_0})$ (1). Set $k:=0$.

Step 1:

Let $x^k:=(x^k_{I_k},0_{J_k})$. If $x^{k}$ is the solution to the TCP$({\mathscr {A}},q)$, stop. Otherwise, let

$$\begin{aligned} I_{k+1}:=I_k\bigcup \{i\in J_k: ({\mathscr {A}}(x^k)^{m-1}+q)_i<0\}\quad \hbox { and}\quad J_{k+1}:=[n]\setminus I_{k+1}. \end{aligned}$$

Step 2:

Let $k:=k+1$ and calculate MP$(I_k)$ to obtain $x^k_{I_k}$. Go to Step 1.

Let the sequences $\{I_k\}$ and $\{x^k\}$ be generated by Algorithm 5.1. Then, it is easy to see that the sequence of index sets $\{I_k\}$ is monotonically increasing, and the sequence $\{x^k\}$ monotonically converges to the least solution to the TCP$({\mathscr {A}},q)$ (1).

Remark 5.1

Suppose that the feasible set of the TCP (1) is nonempty and the involved tensor is a Z-tensor. Then, the least solution of (1) can be found by Algorithm 5.1. Obviously, a main subproblem to be solved in Algorithm 5.1 is a polynomial optimization problem with a linear objective function and polynomial inequality constraints together with a nonnegative constraint. Thus, the successful solution of such a subproblem is the key to the effectiveness of Algorithm 5.1. It is worthwhile to develop effective methods to solve polynomial optimization problems in this form.

5.2 Methods for the TCP Based on Reformulated Integer Programming

The LCP can be solved via linear integer programming [56, 57]. As a natural extension of the LCP, the TCP can also be solved by polynomial integer programming, which was investigated by Du and Zhang [10].

Consider the mixed integer programming (MIP):

$$\begin{aligned} \begin{array}{cl} \max \limits _{t,y,z} &{}\;\; t^{m-1}\\ \hbox { s.t.} &{}\;\; 0\le {\mathscr {A}}y^{m-1}+t^{m-1}q\le e-z,\; 0\le y\le z,\; 0\le t,\; z\in \{0,1\}^n. \end{array} \end{aligned}$$

(13)

The relation between problem (13) and the TCP is described as follows.

Theorem 5.3

[10, Theorem 2] Let $(t^*,y^*,z^*)$ be an arbitrary optimal solution of the MIP (13). Then, $x^*:=\frac{y^*}{t^*}$ solves the TCP$({\mathscr {A}},q)$ (1) if $t^*>0$, and the TCP$({\mathscr {A}},q)$ (1) has no solution if $t^*=0$.

Theorem 5.3 shows that any approach to solve the MIP (13) can be employed to investigate the solvability of the TCP. Moreover, some famous software, such as LINGO, can be used to solve (13), by which we can obtain either a solution to the TCP, or a certificate to show that the TCP has no solution.

Remark 5.2

It is well known that the MIP is a class of difficult problems to be solved effectively. However, problem (13) is a special class of MIPs with favorite structures. It is worthy of designing effective methods to solve problem (13) by making use of structures of tensors and the particularity of the problem.

6 Solution Methods for the TCP Based on Semidefinite Relaxation Methods

Semidefinite relaxation methods have been successfully applied to solve polynomial optimization problems [58,59,60]. Recently, Zhao and Fan [11] extended a semidefinite relaxation approach proposed by Nie [61] to solve the TCP to find its all real solutions, if it has only finite number of solutions. We review it in this section.

Some basic notations need to be introduced before the description of the method. Let ${\mathbb {N}}$ denote the set of nonnegative integers and ${\mathbb {N}}^n$ denote the set of n-element sequences (vectors) of nonnegative integers; ${\mathbb {R}}[x]$ denote the ring of polynomials in $x\in {\mathbb {R}}^n$ over the real field and ${\mathbb {R}}[x]_k$ denote the set of polynomials in ${\mathbb {R}}[x]$ with degree at most k. For any $x=(x_1,\ldots ,x_n)\in {\mathbb {R}}^n$ and $\alpha =(\alpha _1,\ldots ,\alpha _n)\in {\mathbb {N}}^n$, denote the monomial $x^\alpha :=x_1^{\alpha _1}\cdots x_n^{\alpha _n}$ and $|\alpha |:=\sum _{i=1}^n\alpha _i$; and for any positive integer d,

$$\begin{aligned}{}[x]_d:=(1,x_1,\ldots ,x_n,x_1^2,x_1x_2,\ldots ,x_1^d,\ldots ,x_n^d)^\top . \end{aligned}$$

For any polynomial $f\in {\mathbb {R}}[x]$, its degree is denoted by deg(f); and it is said to be SOS if it is the sum of squares of several real polynomials in x. Let $\sum [x]$ denote the set of all SOS polynomials in x, and $\sum [x]_k:=\sum [x]\bigcap {\mathbb {R}}[x]_k$. For any $\gamma \in {\mathbb {R}}$, $\lceil \gamma \rceil$ denotes the smallest integer not smaller than $\gamma$. Given tuples $h=(h_1,\ldots ,h_t)$ and $g=(g_1,\ldots ,g_s)$ where $h_i,g_j\in {\mathbb {R}}[x]$ with $i\in [t]$ and $j\in [s]$, the kth truncation of the ideal generated by h and kth truncation of the quadratic module of g are denoted by

$$\begin{aligned} I_k(h):=h_1\cdot {\mathbb {R}}[x]_{k-\hbox { deg}(h_1)}+\cdots +h_t\cdot {\mathbb {R}}[x]_{k-\hbox { deg}(h_t)} \end{aligned}$$

(14)

and

$$\begin{aligned} Q_k(g):=\sum [x]_{2k}+g_1\cdot \sum [x]_{2k-\hbox { deg}(g_1)}+\cdots +g_s\cdot \sum [x]_{2k-\hbox { deg}(g_s)}, \end{aligned}$$

(15)

respectively. Let ${\mathbb {N}}_d^n:=\{\alpha \in {\mathbb {N}}^n: |\alpha |\le d\}$ and ${\mathbb {R}}^{{\mathbb {N}}_d^n}$ be the space of real vectors indexed by $\alpha \in {\mathbb {N}}_d^n$. For any $y\in {\mathbb {R}}^{{\mathbb {N}}_d^n}$, define

$$\begin{aligned} \langle p,y\rangle =\sum \limits _{\alpha \in {\mathbb {N}}_d^n}p_\alpha y_\alpha \;\; \hbox { for all}\; p(x)=\sum \limits _{\alpha \in {\mathbb {N}}_d^n}p_\alpha x^\alpha , \end{aligned}$$

where $(p_\alpha )$ denotes the coefficient vector indexed by $\alpha \in {\mathbb {N}}_d^n$, and y is said to admit a representing measure supported in a set T, iff there exists a Borel measure $\mu$ such that its support is contained in T and $y_\alpha =\int _Tx^\alpha \hbox {d}\mu$ for any $\alpha \in {\mathbb {N}}_d^n$. Define the symmetric matrices $A_\alpha ^{(k)}$ such that $p(x)[x]_d[x]_d^\top =\sum \limits _{\alpha \in {\mathbb {N}}_{2k}^n}A_\alpha ^{(k)}x^\alpha$, where $p\in {\mathbb {R}}[x]_{2k}$ and $d=k-\lceil \hbox { deg}(p)/2\rceil$. The kth-order localizing matrix of p, generated by $y\in {\mathbb {R}}^{{\mathbb {N}}_{2k}^n}$, is the symmetric matrix $L_p^{(k)}$ satisfying

$$\begin{aligned} L_p^{(k)}(y)=\sum _{\alpha \in {\mathbb {N}}_{2k}^n}A_\alpha ^{(k)}y_\alpha . \end{aligned}$$

(16)

When $p=1$, we call it a moment matrix, which is denoted by $M_k(y)$. For a t-tuple $h=(h_1,\ldots ,h_t)$, we use $\hbox { diag}(L_{h_1}^{(k)}(y),\ldots ,L_{h_t}^{(k)}(y))$ to denote the diagonal matrix with its (i, i)th block being $L_{h_i}^{(k)}(y)$ for any $i\in [t]$ and denote

$$\begin{aligned} L_h^{(k)}(y):=\hbox { diag}(L_{h_1}^{(k)}(y),\ldots ,L_{h_t}^{(k)}(y)). \end{aligned}$$

(17)

For any given $f\in {\mathbb {R}}[x]$, and the tuples $h=(h_1,\ldots ,h_t)$ and $g=(g_1,\ldots ,g_s)$ where $h_i,g_j\in {\mathbb {R}}[x]$ with $i\in [t]$ and $j\in [s]$, we consider the following problem:

$$\begin{aligned} f^*:=\min f(x)\quad \hbox { s.t.}\quad h(x)=0, g(x)\ge 0. \end{aligned}$$

(18)

This polynomial optimization problem can be solved by the semidefinite relaxation method, denoted by the SRM1, which is described as follows. The kth-order Lasserre’s hierarchy of semidefinite relaxation [58] for solving (18) is

$$\begin{aligned} \begin{array}{rl} \sigma _{1,k}:=\min &{} \langle f, y\rangle \\ \hbox { s.t.} &{} \langle 1,y\rangle =1, L_h^{(k)}(y)=0, L_g^{(k)}(y)\succeq 0, M_k(y)\succeq 0,\;\; y\in {\mathbb {R}}^{{\mathbb {N}}_{2k}^d} \end{array} \end{aligned}$$

(19)

for $k=k_0,k_0+1,\ldots$, where $k_0=\max \{\lceil \hbox { deg}(f)/2\rceil ,\lceil \hbox { deg}(h)/2\rceil ,\lceil \hbox { deg}(g)/2\rceil \}$, and $L_h^{(k)}(y),L_g^{(k)}(y), M_k(y)$ are defined as in (16) and (17). The dual problem of (19) is

$$\begin{aligned} \omega _{1,k}:=\max \gamma \quad \hbox { s.t.}\quad f-\gamma \in I_{2k}(h)+Q_k(g), \end{aligned}$$

where $I_{2k}(h)$ and $Q_k(g)$ are defined as in (14) and (15). Then, $\omega _{1,k}\le \sigma _{1,k}\le f^*$ for all k, and both sequences $\{\sigma _{1,k}\}$ and $\{\omega _{1,k}\}$ are monotonically nondecreasing as k increases. Suppose that $y^{1,k}$ is an optimal solution of (19). If there exists $r\in [k_0,k]$ such that

$$\begin{aligned} \hbox { rank}\;M_{r-k_0}({\hat{y}})=\hbox { rank}\;M_r({\hat{y}})\quad \hbox { where}\ {\hat{y}}=y^{1,k}|_{2r}, \end{aligned}$$

(20)

then $\sigma _{1,k}=f^*$, and there are $\hbox { rank}\;M_r({\hat{y}})$ real optimal solutions of problem (18).

Now, we describe a semidefinite relaxation approach for the TCP, which is proposed in [11]. The basic idea can be described as follows. For any $x\in {\mathbb {R}}^n$, we denote the tuples $h(x)=(h_1(x),\ldots ,h_n(x))$ and $g(x)=(g_1(x),\ldots ,g_{2n}(x))$, where

$$\begin{aligned} \begin{array}{rcl} h_i(x)&{}=&{}x_i({\mathscr {A}}x^{m-1}+q)_i,\quad \forall i\in [n];\\ g_j(x)&{}=&{}\left\{ \begin{array}{ll} x_j, &{}\quad \hbox { if}\; j\in [n],\\ ({\mathscr {A}}x^{m-1}+q)_{j-n}, &{}\quad \hbox { if}\; j\in [2n]\setminus [n]. \end{array}\right. \end{array} \end{aligned}$$

Then, SOL$({\mathscr {A}},q)=\{x\in {\mathbb {R}}^n: h(x)=0, g(x)\ge 0\}$. Let $f\in {\mathbb {R}}[x]$ be a random polynomial. Consider the following optimization problem:

$$\begin{aligned} \min f(x)\quad \hbox { s.t.}\quad h(x)=0, g(x)\ge 0. \end{aligned}$$

(21)

Clearly, $x\in \hbox { SOL}({\mathscr {A}},q)$ if and only if x is a feasible solution of (21). When f is generically chosen, it achieves different values $f_i$ at different points in $\hbox { SOL}({\mathscr {A}},q)$. Under the assumption that the TCP$({\mathscr {A}},q)$ is finite, it holds that there are finite values $f_i$. Without loss of generality, we can assume that they satisfy $f_1<f_2<\cdots <f_N$. Let

$$\begin{aligned} {\mathscr {S}}_i:=\hbox { SOL}({\mathscr {A}},q)\bigcap \{x\in {\mathbb {R}}^n: f(x)=f_i\},\quad \forall i\in [N]. \end{aligned}$$

(22)

Then, $\hbox { SOL}({\mathscr {A}},q)={\mathscr {S}}_1\bigcup {\mathscr {S}}_2\bigcup \cdots \bigcup {\mathscr {S}}_N$. So, the remaining task is to compute ${\mathscr {S}}_i$ sequentially.

We first consider the polynomial optimization problem

$$\begin{aligned} \min f(x)\quad \hbox { s.t.}\quad h(x)=0, g(x)\ge 0 \end{aligned}$$

(23)

with $f_1$ being its optimal value and ${\mathscr {S}}_1$ being the set of its optimal solutions. In order to obtain ${\mathscr {S}}_1$, we use the SRM1 to solve (23). Suppose that $y^{1,k}$ is an optimal solution of the kth-order Lasserre’s hierarchy of semidefinite relaxation of (23). If there exists $r\in [k_0,k]$ such that the rank condition (20) holds, then there are $\hbox { rank}M_r({\hat{y}})$ real optimal solutions of problem (23), which constitute the set ${\mathscr {S}}_1$.

Suppose that ${\mathscr {S}}_i$ defined as in (22) is known. We want to determine whether $f_{i+1}$ exists or not; and if it exists, we compute all the elements in ${\mathscr {S}}_{i+1}$. Let $\varepsilon >0$ be a small number. Consider the polynomial optimization problem

$$\begin{aligned} \min f(x)\quad \hbox { s.t.}\quad h(x)=0, g(x)\ge 0, f(x)\ge f_i+\varepsilon . \end{aligned}$$

(24)

Suppose that $f_{i+1}$ exists and $\varepsilon$ satisfies $0<\varepsilon <f_{i+1}-f_i$. In order to obtain ${\mathscr {S}}_{i+1}$, we use the SRM1 to solve (24). Suppose that $y^{i+1,k}$ is an optimal solution of the kth-order Lasserre’s hierarchy of semidefinite relaxation of (24). If there exists $r\in [k_0,k]$ such that the rank condition (20) holds, then there are $\hbox { rank}M_r({\hat{y}})$ real optimal solutions of problem (24), which constitute the set ${\mathscr {S}}_{i+1}$.

In practice, however, the existence of $f_{i+1}$ is usually not known in advance. Fortunately, this difficulty can be overcome by solving the following optimization problem:

$$\begin{aligned} \max f(x)\quad \hbox { s.t.}\quad h(x)=0, g(x)\ge 0, f(x)\le f_i+\varepsilon . \end{aligned}$$

(25)

A practical method can be described as follows.

Algorithm 6.1

(A semidefinite relaxation method) [11, Algorithm 3.2]

Step 0:

Choose a random polynomial f(x). Let $j:=0$ and $k:=k_0$.

Step 1:

If the kth semidefinite relaxation of (23) is infeasible, then SOL$({\mathscr {A}},q)=\emptyset$ and stop. Otherwise, solve the kth semidefinite relaxation of (23) to get an optimal solution $y^{1,k}$ and the optimal value $\sigma _{1,k}$.

Step 2:

If (20) is satisfied for some $r\in [k_0,k]$, then let ${\mathscr {S}}:={\mathscr {S}}_1$, where ${\mathscr {S}}_1$ is the set of optimal solution of (23). Let ${\mathscr {F}}=\{\sigma _{1,k}\}, k:=k_0, j:=j+1$, and go to Step 3. If such r does not exist, let $k:=k+1$ and go to Step 1.

Step 3:

Let $\varepsilon =0.05$. Compute the optimal value ${\bar{f}}_{j+1}$ of (25). If ${\bar{f}}_{i+1}>f_j$, let $\varepsilon =\varepsilon /2$ and compute (25) again. Repeat this procedure until we get ${\bar{f}}_{j+1}=f_j$.

Step 4:

Solve the kth semidefinite relaxation of (24). If it is infeasible, then there are no more real solutions; let SOL$({\mathscr {A}},q)={\mathscr {S}}$ and stop. Otherwise, compute an optimal solution $y^{j+1,k}$ and the optimal value $\sigma _{j+1,k}$.

Step 5:

If (20) is satisfied for some $t\in [k_0,k]$, then update ${\mathscr {S}}:={\mathscr {S}}\bigcup {\mathscr {S}}_{j+1}$, where ${\mathscr {S}}_{j+1}$ is the set of minimizers of (24). Let ${\mathscr {F}}:={\mathscr {F}}\bigcup \{\sigma _{j+1,k}\}$, $k:=k_0$, $j:=j+1$, and go to Step 3. If such t does not exist, let $k:=k+1$ and go to Step 4.

Remark 6.1

Suppose that $\{x\in {\mathbb {R}}^n: h(x)=0\}$ is finite and SOL$({\mathscr {A}},q)\ne \emptyset$. It was proved in [11] that Algorithm 6.1 can find all solutions of the TCP$({\mathscr {A}},q)$, whatever its scale is. In practice, however, with the increasing of the relaxation order k, the scale of the semidefinite relaxation problem will be too large to implement as the computer may be out of memory. So, only small-scale TCPs could be solved effectively so far. Therefore, it is important to develop effective methods for solving large-scale polynomial optimization problems by combining the above method with some dimensionality reduction techniques.

It should be noted that the design and analysis of the semidefinite relaxation method in this section are mainly based on polynomial optimization techniques. Since the function involved in the TCP is a special class of polynomials defined by a tensor, it is possible that this method can be improved by combining polynomial optimization techniques with the structural analysis of the involved tensor.

7 Perspectives and Open Problems

We have reviewed the developments of solution methods for TCPs. During the evaluation of this paper, we find two new algorithms for TCPs were proposed: Hu et al. [62] proposed an inexact augmented Lagrangian multiplier method for solving quadratic complementary problems, and Chen and Zhang [63] proposed a semismooth Newton method to find a Nash equilibrium for the multi-person noncooperative game via solving the corresponding TCP.

By taking full advantage of the special structures of the involved tensors and thereby the nice properties of the resulting polynomial functions, one can develop various numerical methods for the TCP based on different reformulated problems, including tensor equation system, NCP-function-based nonlinear equation system, nonlinear programming, polynomial optimization problem and so on. More effective algorithms need to be further studied by making use of structures of tensors. In what follows, several further problems are addressed.

Problem 1

Since the number of entries of a tensor increases exponentially with the dimensions, leading to the so-called curse of dimensionality, one of the essential tasks in tensor related problems is to develop highly efficient and robust algorithms that are capable of handling large-scale instances, such as high-order high-dimensional TCPs.

Problem 2

Relying on different reformulation models for the TCP, several classical methods, such as the potential reduction method, the homotopy continuation method, the smoothing/non-smooth Newton method, and the semidefinite relaxation method, are employed and developed for solving the TCP. As it was remarked after each method reviewed, it is quite promising to adopt state-of-the-art algorithms for those reformulation problems and tailor them for the TCP by exploiting the involved tensor structures.

Problem 3

Several related models of TCPs have been proposed, such as polynomial complementarity problems, quadratic complementarity problems, stochastic tensor complementarity problems, and so on (see [1]). Some theoretical results for these related models have also been achieved. Up to now, however, all numerical methods proposed in this field focus on solving the TCP. Thus, it is worthy of investigating numerical methods for solving these related models.

Problem 4

In the numerical method given in Sect. 6, an important assumption is that the solution set of the TCP is finite. What conditions can guarantee such an assumption? Furthermore, it is worthy of investigating the number of solutions to the TCP when it is finite. In fact, such an issue for the LCP has been studied extensively.

8 Conclusions

Several existing methods for solving the TCP have been summarized in this second part, based on different equivalent reformulation problems including a tensor equation system, an NCP-function-based smooth equation, a modulus-based non-smooth equation system, and special-structured nonlinear programming problems. The multi-linear structure resulting from the involved tensors has been exploited and applied among most of these methods, which might in turn open up new possibilities in the development of theory and methods for those related classical problems such as the nonlinear equation system and nonlinear programming.

It is noteworthy that the scale of the TCP, especially those practical problems arising from sciences and engineering, would possibly be huge, since even tensors of a modest order will lead to large-scale. How to break the “curse of dimensionality” and develop efficient and stable numerical algorithms for TCPs turns out to be vital in the community of TCPs and all other tensor-based computation in the big data era.