ABSTRACT

In this paper, we discuss the nonemptyness and boundedness of the solution set for $P_{\mathrm{<mo>\; *\; </mo>}}$ -semidefinite complementarity problem by using the concept of exceptional family of elements for complementarity problems over the cone of semidefinite matrices, and obtain a main result that if the corresponding problem has a strict feasible point, then its solution set is nonemptyness and boundedness.

Keywords:

Semidefinite Complementarity Problem, $P_{\mathrm{<mo>\; *\; </mo>}}$ -Mapping, Nonemptyness, Boundedness

1. Introduction

This paper deals with semidefinite complementarity problem (SDCP). Let $\chi$ denote the space of $n\times n$ block-diagonal real matrices with m blocks of sizes $n_1,n_2,\cdots ,n_m\left(n={\displaystyle {\sum }_{i=1}^m}{n}_i\right)$ . We endow $\chi$ with the inner product and norm:

$\langle X,Y\rangle =tr\left[X^{\text{T}}Y\right],\Vert X\Vert =\sqrt{\langle X,X\rangle }=\sqrt{{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{\lambda }_i{\left(X\right)}^2},$ (1.1)

where $X\mathrm{,}Y\in \chi$ and $tr[\cdot ]$ denotes the matrix trace, $\Vert X\Vert$ is the Frobenius-norm of X and ${\lambda }_i\left(X\right)$ stands for the i-eigenvalue of X. Let $\mathbb{S}$ denote the subspace comprising those $X\in \chi$ that are symmetric, i.e., $X^{\text{T}}=X$ . We denote by $S_{+}\left(S_{++}\right)$ the cone of symmetric positive semidefinite (positive definite) matrices in $\mathbb{S}$ , We use the symbol $X\succcurlyeq (\succ )0$ to say that $X\in S_{+}\left(S_{++}\right)$ . To facilitate the presentation, let $X_j\mathrm{,}{Y}_j$ is the j-th block of $X\mathrm{,}Y\in \chi$ , respectively. The SDCP is to find, for given mapping $F\mathrm{<mo>\; :\; </mo>}\mathbb{S}\to \mathbb{S}$ , an $\left(X\mathrm{,}Y\right)\in \mathbb{S}\times \mathbb{S}$ satisfying

$\begin{array}{l}X\succcurlyeq \mathrm{0,}Y\succcurlyeq \mathrm{0,}\langle X,Y\rangle =\mathrm{0,}Y=F\left(X\right)\mathrm{.}\hfill \end{array}$ (1.2)

The problem was firstly introduced in a slightly different form by Kojima, Shindoh and Hara [1] as a model unifying various problems arising from system and control theory and combinatorial optimization. It can be regarded as a generalization of standard complementarity problem (CP).

Recently, there has been growing interest in searching for solutions methods for SDCP [1] [2] [3] , but the assumption that SDCP has a solution is necessary for these solutions methods. It follows that the research of solution conditions for SDCP has played a very important role in both theory and practical applications. Among them, the concept of exceptional family is a powerful tool to study existence of the solution to CP. The concept of exceptional family of elements for a continuous function was first introduced by Smith [4] . Subsequently, Isac et al. [5] introdued a more general notion of exceptional family of elements. Using this notation, some existence theorems of a solution to nonlinear complementarity problems were presented in [5] [6] [7] . Zhao, Han et al. extended it to study existence conditions of a solution to variational inequality problems [8] [9] [10] [11] . Recently, this notation was extended to study existence conditions of a solution to semidefinite complementarity problems and copositive cone complementarity problem [12] [13] [14] .

In this paper, Motivated by the previous researches, we discuss the nonemptyness and boundedness of the solution set for $P_{\mathrm{<mo>\; *\; </mo>}}$ -semidefinite complementarity problem by using the concept of exceptional family of elements for complementarity problems over the cone of semidefinite matrices, and we prove that if the corresponding problem has a strict feasible point, then its solution set is nonemptyness and boundedness.

The remainder of this paper is organized as follows. The preliminary results which will be used in this paper are stated in Section 2. In Section 3, we discuss the nonemptyness and boundedness of the solution set for $P_{\mathrm{<mo>\; *\; </mo>}}$ -semidefinite complementarity problem by using the concept of exceptional family of elements for complementarity problems over the cone of semidefinite matrices. Conclusions are drawn in Section 4.

2. Preliminaries

In this section, we firstly recall some matrix properties that we shall employ throughout this paper. Their proofs and mores details can be found for instance in [15] [16] .

Proposition 2.1 (Von Neumman-Theobald’s inequality) For any $X\mathrm{,}Y\in S_{+}^n$ , it holds that $\langle X,Y\rangle \le \lambda {\left(X\right)}^{\text{T}}\lambda \left(Y\right)$ , with equality if and only if $X$ and $Y$ are simultaneously diagonalizable, where $\lambda \left(X\right)\mathrm{,}\lambda \left(Y\right)$ is the eigenvalue vector of $X$ and $Y$ , respectively.

Proposition 2.2 Let $X\mathrm{,}Y\in S_{+}^n$ , if $\langle X,Y\rangle =0$ , then $X$ and $Y$ commute, i.e., $X$ and $Y$ are simultaneously diagonalizable.

Proposition 2.3 (Fejer’s theorem) Let $X\in S^n$ , it holds that $\langle X,Y\rangle \ge 0$ for all $Y\succcurlyeq 0$ if and only if $X\succcurlyeq 0$ . Moreover, $\langle X,Y\rangle >0$ for all $Y\succ 0$ if and only if $X\succ 0$ .

Now, we present the definition and the property of $P_{\mathrm{<mo>\; *\; </mo>}}$ -mapping and exceptional family of elements for SDCP on the subspace $\mathbb{S}$ .

Definition 2.1 A mapping $F\mathrm{<mo>\; :\; </mo>}\mathbb{S}\to \mathbb{S}$ is said to be a $P_{\mathrm{<mo>\; *\; </mo>}}$ -mapping, if there exists a nonnegative constant $\gamma$ such that the following inequality holds for any distinct $X\mathrm{,}Y\in \mathbb{S}$ ,

$\begin{array}{l}\left(1+\gamma \right){\displaystyle \underset{j\in I_{+}\left(X,Y,F\right)}{\sum }}\langle X_j-Y_j,F_j\left(X\right)-F_j\left(Y\right)\rangle \\ +{\displaystyle \underset{j\in I_{-}\left(X,Y,F\right)}{\sum }}\langle X_j-Y_j,F_j\left(X\right)-F_j\left(Y\right)\rangle \ge 0,\end{array}$ (2.1)

where $I_{+}\left(X,Y,F\right)=\left\{j\in I:\langle X_j-Y_j,F_j\left(X\right)-F_j\left(Y\right)\rangle >0\right\}$ , $I_{-}\left(X,Y,F\right)=\left\{j\in I:\langle X_j-Y_j,F_j\left(X\right)-F_j\left(Y\right)\rangle \le 0\right\}$ and $I=\left\{1,2,\cdots ,m\right\}$ .

Definition 2.2 [2] A sequence ${\left\{X^r\right\}}_{r>0}={\left\{diag\left(X_1^r,X_2^r,\cdots ,X_m^r\right)\right\}}_{r>0}\subseteq S_{+}$ is

said to an exceptional family of elements for SDCP if and only if for any $r$ and every $i\in I$ , there exists a real number ${\mu }_i^r>0$ such that

$F_i\left(X^r\right)+{\mu }_i^r{X}_i^r\succcurlyeq 0,\langle F_i\left(X^r\right)+{\mu }_i^r{X}_i^r,X_i^r\rangle =0,$ (2.2)

${\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\Vert X_i^r\Vert }^2\to +\infty ,r\to +\infty .$ (2.3)

Theorem 2.1 [12] If $F\mathrm{<mo>\; :\; </mo>}\mathbb{S}\to \mathbb{S}$ is a continuous mapping, then SDCP has either a solution or an exceptional family.

3. Main Result

To obtain our main results, we firstly present the following three lemmas in this section.

Lemma 3.1 If $X_i^r\succcurlyeq 0$ , $C_i\succ 0$ is a matrix of size $n_i\times n_i$ and $\underset{r\to +\infty }{lim}\Vert X_i^r\Vert \to +\infty$ , then there exists a subsequence $\left\{X_i^{r_n}\right\}$ such that $\left\{\langle X_i^{r_n}\mathrm{,}{C}_i\rangle \right\}$ has no a upper boundedness.

Proof. Suppose that the spectral decomposition of $X_i^r$ and $C_i$ is as follows, respectively.

$X_i^r={\displaystyle \underset{j=1}{\overset{n_i}{\sum }}}{\lambda }_j^r{\xi }_j^r{\xi }_j^r{}^{\text{T}},C_i={\displaystyle \underset{l=1}{\overset{n_i}{\sum }}}{\gamma }_l{\eta }_l{\eta }_l^{\text{T}},$ (3.1)

where ${\lambda }_j^r\mathrm{,}{\gamma }_l$ is the eigenvalue of $X_i^r\mathrm{,}{C}_i$ , respectively. ${\xi }_j^r\mathrm{,}{\eta }_l$ is the corresponding eigenvector, respectively. Noting that $X_i^r\succcurlyeq \mathrm{0,}{C}_i\succ 0$ , we have that

${\lambda }_j^r\ge 0,{\gamma }_l>0.$ (3.2)

In view of $\underset{r\to +\infty }{lim}\Vert X_i^r\Vert \to +\infty$ and $\Vert X_i^r\Vert =\sqrt{{\displaystyle \underset{j=1}{\overset{n_i}{\sum }}{\left({\lambda }_j^r\right)}^2}}$ , thus, there exists a $j_0$

such that $\left\{{\lambda }_{j_0}^r\right\}$ is unbounded. The above relation also show that there exists a

subsequence $\left\{r_k\right\}$ such that $\underset{r_k\to +\infty }{lim}\Vert {\lambda }_{j_0}^{r_k}\Vert \to +\infty$ .

The next object is to show that there exists $l_{\mathrm{<mo>\; *\; </mo>}}$ such that ${\xi }_{j_0}^{r\text{T}}{\eta }_{l_{*}}\ne 0$ .

Assume that ${\xi }_{j_0}^{r\text{T}}{\eta }_l=0$ for any $l$ , one gets

$A{\xi }_{j_0}=0,A=\left[\begin{array}{c}{\eta }_1^{\text{T}}\\ {\eta }_2^{\text{T}}\\ ⋮\\ {\eta }_{n_i}^{\text{T}}\end{array}\right].$ (3.3)

Since A is a nonsingular, then we have ${\xi }_{j_0}^r=0$ . This is a contradiction. Combining the above relations, we have

${\lambda }_{j_0}^{r_k}{\gamma }_{l_{\mathrm{<mo>\; *\; </mo>}}}{\left({\xi }_{j_0}^{r_k}{}^{\text{T}}{\eta }_{l_{\mathrm{<mo>\; *\; </mo>}}}\right)}^2\to +\infty \mathrm{,}\text{as}{r}_k\to +\infty \mathrm{.}$ (3.4)

Hence

$\begin{array}{c}\langle X_i^r,C_i\rangle ={\displaystyle \underset{j=1}{\overset{n_i}{\sum }}}{\displaystyle \underset{l=1}{\overset{n_i}{\sum }}}{\lambda }_j^r{\gamma }_l{\left({\xi }_j^r{}^{\text{T}}{\eta }_l\right)}^2\\ ={\lambda }_{j_0}^{r_k}{\gamma }_{l_{*}}{\left({\xi }_{j_0}^{r_k}{}^{\text{T}}{\eta }_{l_{*}}\right)}^2+{\displaystyle \underset{j=1,j\ne j_0}{\overset{n_i}{\sum }}}{\displaystyle \underset{l=1,l\ne l_{*}}{\overset{n_i}{\sum }}}{\lambda }_j^r{\gamma }_l{\left({\xi }_j^r{}^{\text{T}}{\eta }_l\right)}^2\\ \ge {\lambda }_{j_0}^{r_k}{\gamma }_{l_{*}}{\left({\xi }_{j_0}^{r_k}{}^{\text{T}}{\eta }_{l_{*}}\right)}^2\to +\infty ,\text{as}{r}_k\to +\infty .\end{array}$ (3.5)

The proof is complete.

From Proposition 2.1 and Proposition 2.2, we can get the following lemma.

Lemma 3.2 If $U\succ 0$ , $V\succcurlyeq 0$ and $\langle U,V\rangle =0$ , then $V=0$ .

The proof of the following lemma is elementary, and omitted.

Lemma 3.3 If $\left\{U^r\right\}\in S_{+}$ and $\underset{r\to +\infty }{lim}\Vert U^r\Vert \to +\infty$ , and $\hat{U}$ is a cluster point of $\left\{\frac{U^r}{\Vert U^r\Vert }\right\}$ , then $\hat{U}\in S_{+}$ and $\Vert \hat{U}\Vert =1$ .

Now, we present our main results as follows.

Theorem 3.1 If $F\mathrm{<mo>\; :\; </mo>}\mathbb{S}\to \mathbb{S}$ is a continuous $P_{\mathrm{<mo>\; *\; </mo>}}$ mapping and there exists a strict feasible point for SDCP, i.e., $X^0\succcurlyeq \mathrm{0,}F\left(X^0\right)\succ 0$ , then the solution set of SDCP is nonempty.

Proof. Suppose that there exists no solution for SDCP, then from Theorem 2.1, we have that there exists an exceptional family of elements

${\left\{X^r\right\}}_{r>0}={\left\{diag\left(X_1^r,X_2^r,\cdots ,X_m^r\right)\right\}}_{r>0}\subseteq S_{+}$ for SDCP, and for every $i\in I$ , there exists a real number ${\mu }_i^r>0$ such that

$F_i\left(X^r\right)+{\mu }_i^r{X}_i^r\succcurlyeq \mathrm{0,}\langle F_i\left(X^r\right)+{\mu }_i^r{X}_i^r\mathrm{,}{X}_i^r\rangle =\mathrm{0,}$ (3.6)

${\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\Vert X_i^r\Vert }^2\to +\infty ,r\to +\infty .$ (3.7)

Let $U_i^r=F_i\left(X^r\right)+{\mu }_i^r{X}_i^r$ . From the above first equation, one gets $U_i^r\succcurlyeq 0$ . Thus, for any $i\in I$ , taking into account the above second equation and Proposition 2.3, we have

$\begin{array}{l}\langle X_i^r-X_i^0\mathrm{,}{F}_i\left(X^r\right)-F_i\left(X^0\right)\rangle \\ =\langle X_i^r-X_i^0\mathrm{,}{U}_i^r-{\mu }_i^r{X}_i^r-F_i\left(X^0\right)\rangle \\ =-{\mu }_i^r{\Vert X_i^r\Vert }^2-\langle X_i^0\mathrm{,}{U}_i^r\rangle -{\mu }_i^r\langle X_i^r\mathrm{,}-X_i^0\rangle -\langle X_i^r-X_i^0\mathrm{,}{F}_i\left(X^0\right)\rangle \\ \le -{\mu }_i^r{\Vert X_i^r\Vert }^2-{\mu }_i^r\langle X_i^r\mathrm{,}-X_i^0\rangle -\langle X_i^r-X_i^0\mathrm{,}{F}_i\left(X^0\right)\rangle \\ \le -{\mu }_i^r\Vert X_i^r\Vert \left(\Vert X_i^r\Vert -\Vert X_i^0\Vert \right)-\langle X_i^r-X_i^0\mathrm{,}{F}_i\left(X^0\right)\rangle \mathrm{.}\end{array}$ (3.8)

Denote by $I^1=\left\{i\in I:\Vert X_i^r\Vert \to +\infty ,r\to +\infty \right\}$ , $I^2=I\backslash I^1$ . Obviously, $I^1\ne \varnothing$ and

$\begin{array}{l}\langle X^r-X^0,F\left(X^r\right)-F\left(X^0\right)\rangle \\ ={\displaystyle \underset{i\in I^1}{\sum }}\langle X_i^r-X_i^0,F_i\left(X^r\right)-F_i\left(X^0\right)\rangle +{\displaystyle \underset{i\in I^2}{\sum }}\langle X_i^r-X_i^0,F_i\left(X^r\right)-F_i\left(X^0\right)\rangle .\end{array}$ (3.9)

When $i\in I^2$ , we have that there exists a upper boundedness for $\left\{\langle X_i^r-X_i^0\mathrm{,}{F}_i\left(X^r\right)-F_i\left(X^0\right)\rangle \right\}$ from the formula (3.8).

When $i\in I^1$ , one gets $\Vert X_i^r\Vert >\Vert X_i^0\Vert$ for sufficient large k. Noticing that $X^r\succcurlyeq \mathrm{0,}{F}_i\left(X^0\right)\succ 0$ , from Lemma 3.1, we have that for any $i\in I^1$ , there exists a subsequence $\left\{X_i^{r_n}\right\}$ such that $\underset{r_n\to +\infty }{lim}\langle X_i^{r_n}\mathrm{,}{F}_i\left(X^0\right)\rangle \to +\infty$ . Thus, $\underset{r_n\to +\infty }{lim}\langle X_i^{r_n}-X_i^0\mathrm{,}{F}_i\left(X^0\right)\rangle \to +\infty$ . In view of the formula (3.8), one gets

$\underset{r_n\to +\infty }{lim}\langle X_i^{r_n}-X_i^0\mathrm{,}{F}_i\left(X^r\right)-F_i\left(X^0\right)\rangle \to -\infty \mathrm{,}$ (3.10)

which implies that

$\underset{r_n\to +\infty }{lim}\langle X^{r_n}-X^0\mathrm{,}F\left(X^r\right)-F\left(X^0\right)\rangle \to -\infty \mathrm{.}$ (3.11)

This is a contradiction with F being a $P_{\mathrm{<mo>\; *\; </mo>}}$ -mapping. The proof is complete.

Theorem 3.2 If $F\mathrm{<mo>\; :\; </mo>}\mathbb{S}\to \mathbb{S}$ is a continuous $P_{\mathrm{<mo>\; *\; </mo>}}$ -mapping and there exists a strict feasible point for SDCP, i.e., $X^0\succcurlyeq \mathrm{0,}F\left(X^0\right)\succ 0$ , then the solution set of SDCP is bounded.

Proof. Suppose that the solution set of SDCP is unbounded, i.e., there exists a

solution sequence $\left\{X^k\right\}$ such that $\underset{k\to +\infty }{lim}\Vert X^k\Vert \to +\infty$ . Obviously,

$X^k\succcurlyeq \mathrm{0,}F\left(X^k\right)\succcurlyeq \mathrm{0,}\langle X^k\mathrm{,}F\left(X^k\right)\rangle =\mathrm{0,}\forall k\mathrm{.}$ (3.12)

Noting that F is a $P_{\mathrm{<mo>\; *\; </mo>}}$ mapping, we have that for any k,

$\begin{array}{l}\left(1+\gamma \right){\displaystyle \underset{j\in I_{+}\left(X^0,X^k,F\right)}{\sum }}\langle X_j^0-X_j^k,F_j\left(X^0\right)-F_j\left(X^k\right)\rangle \\ +{\displaystyle \underset{j\in I_{-}\left(X^0,X^k,F\right)}{\sum }}\langle X_j^0-X_j^k,F_j\left(X^0\right)-F_j\left(X^k\right)\rangle \ge 0,\end{array}$ (3.13)

i.e.,

$\begin{array}{l}\langle X^0-X^k\mathrm{,}F\left(X^0\right)-F\left(X^k\right)\rangle \\ \ge -\gamma {\displaystyle \underset{j\in I_{+}\left(X^0\mathrm{,}{X}^k\mathrm{,}F\right)}{\sum }}\langle X_j^0-X_j^k\mathrm{,}{F}_j\left(X^0\right)-F_j\left(X^k\right)\rangle \mathrm{.}\end{array}$ (3.14)

From the formula (3.12), one gets

$\begin{array}{l}\langle X^0,F\left(X^k\right)\rangle +\langle F\left(X^0\right),X^k\rangle \\ +\gamma {\displaystyle \underset{j\in I_{+}\left(X^0,X^k,F\right)}{\sum }}\left[\langle X_j^0,F_j\left(X^k\right)\rangle +\langle X_j^k,F_j\left(X^0\right)\rangle \right]\\ \le \langle X^0,F\left(X^0\right)\rangle +\gamma {\displaystyle \underset{j\in I_{+}\left(X^0,X^k,F\right)}{\sum }}\langle X_j^0,F_j\left(X^0\right)\rangle .\end{array}$ (3.15)

Taking into account Proposition 2.3 and the formula (3.15), we get

$\langle F\left(X^0\right)\mathrm{,}{X}^k\rangle \le \langle X^0\mathrm{,}F\left(X^0\right)\rangle +\gamma {\displaystyle \underset{j\in I_{+}\left(X^0\mathrm{,}{X}^k\mathrm{,}F\right)}{\sum }}\langle X_j^0\mathrm{,}{F}_j\left(X^0\right)\rangle \mathrm{.}$ (3.16)

Noting that $\mathrm{<mo>\; \{\; </mo>}\frac{X^k}{�X^k�}\mathrm{<mo>\; \}\; </mo>}$ is bounded. Hence, there exists a subsequence $\left\{X^{k_n}\right\}$ such that

$\underset{k_n\to +\infty }{\lim }\frac{X^{k_n}}{\Vert X^{k_n}\Vert }=\bar{X}.$ (3.17)

From Lemma 3.3, we have that $\bar{X}\pm 0,\Vert \bar{X}\Vert =1$ .

On the other hand, from (3.16), one gets for any $k_n$

$\begin{array}{c}\langle F\left(X^0\right),\frac{X^{k_n}}{\Vert X^{k_n}\Vert }\rangle =\frac{\langle F\left(X^0\right),X^{k_n}\rangle }{\Vert X^{k_n}\Vert }\\ \le \frac{\langle X^0,F\left(X^0\right)\rangle +\gamma {\displaystyle \underset{j\in I_{+}\left(X^0,X^k,F\right)}{\sum }}\langle X_j^0,F_j\left(X^0\right)\rangle }{\Vert X^{k_n}\Vert }.\end{array}$ (3.18)

Since $\underset{k_n\to +\infty }{\lim }\Vert X^{k_n}\Vert \to +\infty$ , then

$\langle F\left(X^0\right)\mathrm{,}\bar{X}\rangle \le 0.$ (3.19)

Obviously, $\langle F\left(X^0\right)\mathrm{,}\bar{X}\rangle \ge 0$ . Thus, $\langle F\left(X^0\right)\mathrm{,}\bar{X}\rangle =0$ , which implies that $\bar{X}=0$ from Lemma 3.2. This is a contradiction with $\Vert \bar{X}\Vert =1$ . The proof is complete.

4. Conclusion

In this paper, the nonemptyness and boundedness of the solution set for $P_{\mathrm{<mo>\; *\; </mo>}}$ -semidefinite complementarity problem have been discussed by using the concept of exceptional family of elements for complementarity problems over the cone of semidefinite matrices, and a main result has been shown that if the corresponding problem has a strict feasible point, then its solution set is nonemptyness and boundedness.

Acknowledgements

This work is supported by National Natural Science Foundation of China (No.11761014, 11461015), Guangxi Natural Science Foundation (No. 2015GXNSFAA139010, 2017GXNSFAA198243) and Guangxi Colleges and Universities Key Laboratory of Mathematical and Statistical Model (No. 2016GXKLMS010), Guangxi basic ability improvement project for the Middle-aged and young teachers of colleges and universities (2017KY0068, KY2016YB069).

Cite this paper

Chen, Y., Chen, C.L. and Han, C.H. (2018) Some Properties of Solution to Semidefinite Complementarity Problem. Journal of Applied Mathematics and Physics, 6, 122-129. https://doi.org/10.4236/jamp.2018.61012

References