ریاضی و جامعه (May 2024)
Existence of the solutions of an interval tensor complementarity problem
Abstract
In this paper, we consider a general tensor complementarity problem with interval parameters, and study the conditions under which, the existence and uniqueness of the solution of the problem are guaranteed. Furthermore, we proved that the solution set of the interval tensor complementarity problem is not necessarily convex. 1. IntroductionInterval analysis is a branch of numerical analysis that was born in the 1960's. It consists of computing with intervals of reals instead of reals, providing a framework for handling uncertainties and verified computations. The result of an interval computation is an interval, a pair of numbers, an upper and a lower bound, and this pair of numbers guarantees to enclose the exact answer. Maybe we still don’t know the truth, but at least we know how much we don’t know! [4]. How is it possible for interval analysis to guarantee that a computational result is true? The answer is very simple. Using the interval analysis we estimate at each calculation step all kinds of errors: inputs errors, rounding errors and truncation errors. One of the most famous references on IA is probably Moore’s Interval Analysis book. Throughout the paper, vectors are written as $\left\{x, y, \ldots \right\}$, matrices are shown by $ \left\{A, B,\ldots \right\}$ and tensors are written as $ \left\{ \mathcal{A}, \mathcal{B},\ldots \right\}.$ Let $[n]$, $\mathbb{R} (\mathbb{C}) $, and $\mathbb{R}^n (\mathbb{C}^n)$ denote the set $\{ 1, 2,\ldots,n\}$, the set of all real (complex) numbers, and the set of all $n$-dimensional real (complex) vectors; respectively. $x \geq 0 \ \ \ (x > 0)$ means $x_i \geq 0 \ \ \ (x_i > 0)$ for all $i \in \left[ n \right]$. Let $\mathbb{R} _{+}^n = \lbrace x \in \mathbb{R}^n \mid x \geq 0\rbrace$ be the positive cone in $\mathbb{R}^n.$ An order $m$ dimension $n$ real tensor $\mathcal{A} = (a_{i_1 i_2\cdots i_m}),$ denoted by $ \mathcal{A} \in \mathbb{R}^{n_1 \times \cdots \times n_m } ,$ consists of $n^m$ entries: \[a_{i_1 i_2 \cdots i_m} \in \mathbb{R}, \quad \; \forall \; i_j = 1,\cdots,n ,\quad j = 1,\cdots,m.\] If $n_1=\cdots=n_m = n$, then it is said $\mathcal{A}$ is an $m$-order $n$-dimensional cubical tensor or for simplicity just $m$-order $n$-dimensional tensor. A vector is a tensor of order $1$ and a matrix is a tensor of order $2$. A tensor $\mathcal{A} = (a_{i_1 i_2 \cdots i_m}) \in \mathbb{R}^{n_1 \times \cdots \times n_m } $ is called nonnegative (positive) if \[a_{i_1 i_2 \cdots i_m} \ge 0 \; (a_{i_1 i_2 \cdots i_m}>0 ), \quad \; \forall \; i_j = 1,\cdots,n ,\quad j = 1,\cdots,m.\] A tensor $ \mathcal{A}$ is said to be symmetric if its entries $ a_{i_1 i_2 \cdots i_m}$ are invariant under any permutation of $ m $ indices $ ( a_{i_1 i_2 \cdots i_m}). $ All the tensors discussed in this paper are real.\\For any two tensors, $\mathcal{A} = (a_{i_1 \cdots i_m } ),$ and $ \mathcal{B} = (b_{i_1 \cdots i_m } ) \in \mathbb{R}^{n_1 \times \cdots \times n_m } $ of identical orders and dimensions, their inner product is defined as $$\left\langle {\mathcal{A},\mathcal{B}} \right\rangle = \sum\limits_{i_1 \cdots i_m } {a_{i_1 \cdots i_m } b_{i_1 \cdots i_m}}. $$ Definition 1.1. If $\mathcal{A} \in \mathbb{R}^{n_1 \times \cdots \times n_m } $ is an $m$-order tensor and $ B \in \mathbb{R}^{J \times n_k }$ is a matrix, then $\mathcal{A} \times_k B $ denotes the mode-$k$ product of $\mathcal{A}$ with $B$, which is of size $ n_1 \times \cdots \times n_{k-1} \times J \times n_{k+1} \times \cdots \times n_m $, and each element of it is defined as follows \[(\mathcal{A} \times_k B)_{i_1,\ldots,i_{k-1}, j, i_{k+1},\ldots,i_m} = \sum\limits_{i_k = 1}^{n_k } a_{i_1 \cdots i_m } b_{j,i_k}.\]If we do the mode-$k$ product of $ \mathcal{A} $ and $B $ for all possible $k \in [m]$ as \[ \mathcal{A} \times_1 B \times_2 \cdots \times_m B,\] and $B $ is reduced to some row vector, say $x^T=\left( x_1,\ldots,x_n \right),$ the following notations are frequently used in this paper:\begin{align*}&\mathcal{A} x^m \equiv \mathcal{A} \times_1 x^T \times_2 \cdots \times_m x^T = \sum\limits_{i_1 \cdots i_m =1}^n {a_{i_1 \cdots i_m} x_{i_1} \cdots x_{i_m}} \in \mathbb{R}, \\&\mathcal{A} x^{m-1 } \equiv \mathcal{A} \times_2 x^T \times_3 \cdots \times_m x^T = \sum\limits_{i_2 \cdots i_m =1}^n {a_{i, i_2 \cdots i_m} x_{i_2} \cdots x_{i_m}} \in \mathbb{R}^n.\end{align*}We call a number $\lambda \in \mathbb{C}$ an eigenvalue of $\mathcal{A}$ if it and a nonzero vector $x \in \mathbb{C}^n$ are solutions of the following homogeneous polynomial equations:(1.1)\begin{equation}\label{e3}\left( \mathcal{A} x^{m-1} \right)_i = \lambda x_i^{m - 1}, \ \ \ \forall i=1,\ldots,n,\end{equation}and call the solution $x$ an eigenvector of $\mathcal{A}$ associated with the eigenvalue $\lambda.$ If we denote $x^{[m-1]}$ as a vector in $\mathbb{C}^n$ such that its $i$th component is $x_i^{m - 1},$ then (1.1) can be simply expressed as $$\mathcal{A} x^{m-1} = \lambda x^{[m-1]}.$$ The set of all the eigenvalues of $\mathcal{A}$ is called the spectrum of $\mathcal{A}.$ The largest modulus of the elements in the spectrum of $\mathcal{A}$ is called the spectral radius of $\mathcal{A},$ denoted as $\rho(\mathcal{A}).$ Definition 1.2. Let $\mathcal{A}$ be an $m$-order and $n$-dimensional cubical tensor, then$(1)$ $\mathcal{A}$ is called an $\mathcal{Z}$-tensor if all of its non-diagonal elements are non-positive. This definition is equivalent to having $\mathcal{A}=s\mathcal{I}-\mathcal{B}$, where $s > 0$, $\mathcal{B}$ is a non-negative tensor and $\mathcal{I}=(I_{i_1 \cdots i_m })$, is the identity tensor with entries$$I_{i_1 \cdots i_m}=\left\{ \begin{gathered}1, \ \ \ i_1=\cdots= i_m,\hfill \\0, \ \ \ otherwise. \hfill \\\end{gathered} \right.$$$(2)$ $\mathcal{A}$ is called an $\mathcal{M}$-tensor if $\mathcal{A}$ is an $\mathcal{Z}$-tensor and $\mathcal{A} = s\mathcal{I} - \mathcal{B}$, $s \geq \rho(\mathcal{B})$. If $s > \rho(B)$, then $\mathcal{A}$ is called a strong(nonsingular) $\mathcal{M}$-tensor. Definition 1.3. An $m$-order $n$-dimensional tensor $\mathcal{A}$ is said to be P-tensor, if for each nonzero $x \in \mathbb{R}^n $, there exists some index $i$such that(1.2)\begin{equation}\label{e4}x_i \left( {\mathcal{A}x^{m - 1}} \right)_i >0.\end{equation}The tensor $\mathcal{M}(\mathcal{A} )=(m_{i_1 \cdots i_m})$ is called the comparison tensor of $\mathcal{A}$ if$$ m_{i_1 \cdots i_m}= \begin{cases}-\left|a_{i_1 \cdots i_m}\right|, & \text { if } (i_2,\cdots,i_m) \neq (i_1,\cdots,i_1) \\ \left|a_{i_1 \cdots i_m}\right|, & \text { if } (i_2,\cdots,i_m)=(i_1,\cdots,i_1)\end{cases} $$ Definition 1.4. A tensor $\mathcal{A}$ is called an $\mathcal{H}$-tensor, if its comparison tensor is an $\mathcal{M}$-tensor, and it is called a nonsingular $\mathcal{H}$ -tensor, if its comparison tensor is nonsingular. The tensor complementarity problem denoted by the $\operatorname{TCP}(\mathbf{q}, \mathcal{A})$, is to find a vector $\mathbf{x}$ such that:$$ \mathbf{x} \geq 0, ~\mathcal{A} \mathbf{x}^{m-1}+\mathbf{q} \geq 0,~\left\langle\mathbf{x}, \mathcal{A} \mathbf{x}^{m-1}+\mathbf{q}\right\rangle=0, $$ where $\left\langle , \right\rangle $ denotes the inner product. Theorem 1.5. [6] Tensor $\mathcal{A}$ is $P$-tensor if and only if TCP(q, $\mathcal{A}$) has a unique solution for every $q > 0.$ 2. Main ResultsInterval linear algebra is a mathematical field developed from classical linear algebra. The only difference is that we do not work with real numbers but we deal with the real closed intervals $x^I : = \left[ {\underline{x}, \overline{x}} \right]$, where $\underline{x} \leq \overline{x}.$ An interval tensor is a tensor which every of its elements is interval. An $m$-order $n$-dimensional cubical interval tensor is denoted by $\mathcal{A}^I : = \left[{\underline{\mathcal{A}}, \overline{\mathcal{A}} } \right]$, where${\underline{ \mathcal{A}}}$ and ${\overline {\mathcal{A}}}$ are real tensors, and \[\mathcal{A}^I (i_1,\cdots,i_m ) = \left[ {\underline {\mathcal{A}} (i_1,\cdots,i_m), \overline {\mathcal{A}} (i_1,\cdots,i_m )} \right].\] The set of all interval tensors of size $ n_1 \times \cdots \times n_m$, is denoted by $\mathbb{I}\mathbb{R}^{n_1 \times \cdots \times n_m}. $ The parametric form of interval, interval vector and interval tensor can be expressed as follows, respectively. $${a^I=\left\{a(t) \in \mathbb{R}: a(t)=\underline{a}+t\left(\overline{a}-\underline{a}\right), \underline{a} \in \mathbb{R}, \overline{a} \in \mathbb{R}, t \in[0,1]\right\},}$$ $${x^I=\left\{x(t) \in \mathbb{R}^{n}: x(t)=\underline{x}+t\left(\overline{x}-\underline{x}\right), \underline{x} \in \mathbb{R}^{n}, \overline{x} \in \mathbb{R}^{n}, t \in[0,1]\right\},} $$ $${\mathcal{A}^I=\left\{\mathcal{A}(t) \in \mathbb{R}^{n \times n \cdots \times n}: \mathcal{A}(t)=\underline{\mathcal{A}}+t\left(\overline{\mathcal{A}}-\underline{\mathcal{A}}\right), \underline{\mathcal{A}} \in \mathbb{R}^{n \times n \cdots \times n}, \overline{\mathcal{A}} \in \mathbb{R}^{n \times n \cdots \times n}, t \in[0,1]\right\}.}$$ Definition 2.1. For $\mathcal{A}^I=[a_{i_1 \cdots i_m}] \in \mathbb{I R}^{n \times n \cdots \times n}$, we define the comparison tensor of $\mathcal{A}^I$ and it is represented as $\mathcal{M}(\mathcal{A}^I )=(m_{i_1 \cdots i_m}) \in \mathbb{R}^{n \times n \cdots \times n}$ by setting$$ m_{i_1 \cdots i_m}= \begin{cases}-\left|[a_{i_1 \cdots i_m}]\right|, & \text { if } (i_2,\cdots,i_m) \neq (i_1,\cdots,i_1) \\ \left|[a_{i_1 \cdots i_m}]\right|, & \text { if } (i_2,\cdots,i_m)=(i_1,\cdots,i_1)\end{cases}$$ Definition 2.2. An interval tensor $\mathcal{A}^I \in \mathbb{I R}^{n \times n \cdots \times n}$ is called an interval $p$-tensor, $\mathcal{Z}$-tensor, $\mathcal{M}$-tensor and $\mathcal{H}$-tensor, if all $\mathcal{A} \in\mathcal{A}^I$ are $p$-tensor, $\mathcal{Z}$-tensor, $\mathcal{M}$-tensor and $\mathcal{H}$-tensor, respectively. Let $\mathcal{A}^I $ be an $m$-order and $n$-dimensional interval tensor and $q^I \in \mathbb{I R}^{n}$ be an $n$ dimensional interval vector. Then we consider the family of $T CP(\mathcal{A}, q)$'s$$q+\mathcal{A} x^{m - 1} \geq 0, \quad x \geq 0, x^ T ( q+\mathcal{A} x^{m - 1} ) = 0, ~\text {where}~ \mathcal{A} \in\mathcal{A}^I, q^I$$This is equivalent to the following family of $T C P(\mathcal{A}, q)$'s$$w-\mathcal{A} x^{m - 1}=q, \quad x \geq 0, w \geq 0, x^ T w=0, \text { where } \mathcal{A} \in\mathcal{A}^I, q^I.$$The family of $T C P(\mathcal{A}, q)$'s is represented as interval tensor complementarity problem and it is denoted by $\operatorname{ITCP}(\mathcal{A}^I, q^I) \cdot \sum_{x}(\mathcal{A}^I,q^I)$ is denoted as solutions set of $\operatorname{ITCP}(\mathcal{A}^I, q^I)$ and it is defined as $$\left\{x \in \mathbb{R}^{n}: q+ \mathcal{A} x^{m - 1} \geq 0, x \geq 0, x^ T (q+ \mathcal{A} x^{m-1}) =0, \mathcal{A} \in\mathcal{A}^I, q^I\right\}$$ The parametric form of $\operatorname{ITCP}(\mathcal{A}^I,q^I)$ is represented as $T C P(\mathcal{A}(t), q(t)), t \in[0,1]$ and its solution set is defined as for some fixed $t,$$$\sum_{x}(\mathcal{A}(t), q(t))=\left\{x \in \mathbb{R}^{n}: q(t)+\mathcal{A}(t) x^{m - 1} \geq 0, x \geq 0,x^{T} (q(t)+\mathcal{A}(t) x^{m - 1}) =0\right\}$$ Lemma 2.3. For any $\operatorname{ITCP}(\mathcal{A}^I,q^I), \sum_{x}\left(\underline{\mathcal{A}}, \underline{q}\right)$ and $\sum_{x}\left(\overline{\mathcal{A}}, \overline{q}\right)$ are subsets of $\sum_{x}(\mathcal{A}^I,q^I)$. Theorem 2.4. Suppose that $T C P\left(\underline{\mathcal{A}}, \underline{q}\right)$ and $T C P\left(\overline{\mathcal{A}}, \overline{q}\right)$ have unique solutions, then $\sum_{x}(\mathcal{A}(t), q(t))$ is a singleton set, for every $t \in[0,1]$. Proof. Suppose that $T C P\left(\underline{\mathcal{A}}, \underline{q}\right)$ and $T C P\left(\overline{\mathcal{A}}, \overline{q}\right)$ have unique solutions, then from Theorem \ref{pp} we get that $\underline{\mathcal{A}}$ and $\overline{\mathcal{A}}$ are $P$-tensors. Since the positive convex combination of $P$-tensors is also a $P$-tensor, then $\mathcal{A}(t)=t \underline{\mathcal{A}}+(1-t) \overline{\mathcal{A}}$, $t \in[0,1]$, is a $P$-tensor. Hence $\operatorname{TCP}(\mathcal{A}(t), q(t))$ has unique solution for each $t$. Therefore, $\sum_{x}(\mathcal{A}(t), q(t))$ is a singleton set, for every $t \in[0,1]$.Theorem 2.5. The set $\sum_{(w, x)}(\mathcal{A}^I,q^I)$ is not convex.Proof. Let $\left(w^{1}, x^{1}\right)^{T},\left(w^{2}, x^{2}\right)^{T} \in \sum_{(w, x)}(\mathcal{A}^I,q^I)$. Then,(2.1)$$\begin{gathered}& w_{i}^{j}-\sum_{i_2 \cdots i_m=1}^{n} \overline{a}_{i i_2 \cdots i_m} x_{i_2}^{j} \cdots x_{i_m}^{j} \leq \overline{q}_{i}, w_{i}^{j}-\sum_{i_2 \cdots i_m=1}^{n} \underline{a}_{i i_2 \cdots i_m} x_{i_2}^{j} \cdots x_{i_m}^{j} \geq \underline{q}_{i},\\ & x_{i_2}^{j} \cdots x_{i_m}^{j} \geq 0, w_{i}^{j} \geq 0, w_{i}^{j} x_{i}^{j}=0, i_1, \cdots, i_m=1, 2,\ldots,n, ~ j=1,2.\end{gathered}$$Let $0 \leq \lambda \leq 1$. Then multiplying (2.1) by $\lambda$ for $j=1$, and multiplying (2.1) by $(1-\lambda)$ for $j=2$, and adding up these inequalities, we get$$\begin{gathered}\left(\lambda w_{i}^{1}+(1-\lambda) w_{i}^{2}\right)-\sum_{i_2 \cdots i_m=1}^{n} \overline{a}_{i i_2 \cdots i_m}\left(\lambda x_{i_2}^{1} \cdots x_{i_m}^{1}+(1-\lambda) x_{i_2}^{2} \cdots x_{i_m}^{2}\right) \leq \overline{q}_{i}, i=1,2, \ldots, n, \\\left(\lambda w_{i}^{1}+(1-\lambda) w_{i}^{2}\right)-\sum_{i_2 \cdots i_m=1}^{n} \underline{a}_{i i_2 \cdots i_m}\left(\lambda x_{i_2}^{1} \cdots x_{i_m}^{1}+(1-\lambda) x_{i_2}^{2} \cdots x_{i_m}^{2}\right) \geq \underline{q}_{i}, i=1,2, \ldots, n, \\\left(\lambda x_{i_2}^{1} \cdots x_{i_m}^{1}+(1-\lambda) x_{i_2}^{2} \cdots x_{i_m}^{2}\right) \geq 0,\left(\lambda w_{i}^{1}+(1-\lambda) w_{i}^{2}\right) \geq 0, i_1,\cdots,i_m=1, 2,\ldots,n.\end{gathered}$$On the other hand, $\left(\lambda w_{i}^{1}+(1-\lambda) w_{i}^{2}\right)\left(\lambda x_{i_2}^{1} \cdots x_{i_m}^{1}+(1-\lambda) x_{i_2}^{2} \cdots x_{i_m}^{2}\right)=0$ only for $t=0$ and $t=1$. Since convex combination of complementarity variables are not complementarity variables. This gives that $\left(\lambda w^{1}+(1-\lambda) w^{2}, \lambda x^{1}+(1-\lambda) x^{2}\right)^{T} \notin \sum_{(w,x)}(\mathcal{A}^I,q^I)$, and so $\sum_{(w, x)}(\mathcal{A}^I,q^I)$ is not a convex set. Theorem 2.6. Let $\mathcal{A}^I $ be an $m$-order and $n$-dimensional interval $H$-tensor. Then, $\operatorname{ITCP}(\mathcal{A}^I,q^I)$ has a solution for every $q^I \in \mathbb{I R}^{n}$, that is, $\sum_{x}(\mathcal{A}^I,q^I)$ is a non-empty set. Proof. Let $\mathcal{A}^I $ be an $m$-order and $n$-dimensional interval $H$-tensor. Then each $\mathcal{A} \in\mathcal{A}^I$ is an $H$-tensor, and so $T C P(\mathcal{A}, q)$ has a solution. Also, $\sum_{x}(\mathcal{A}, q) \subseteq \sum_{x}(\mathcal{A}^I,q^I)$, which yields that $\sum_{x}(\mathcal{A}^I,q^I)$ is non-empty. 3. ConclusionA methodology is developed to discuss the existence of the solution of tensor complementarity problem, where the parameters are closed intervals. We also proved that the solution set of the interval tensor complementarity problem is not necessarily convex.
Keywords
