Back
 JAMP  Vol.6 No.1 , January 2018
Some Properties of Solution to Semidefinite Complementarity Problem
Abstract: In this paper, we discuss the nonemptyness and boundedness of the solution set for P*-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.

1. Introduction

This paper deals with semidefinite complementarity problem (SDCP). Let χ denote the space of n × n block-diagonal real matrices with m blocks of sizes n 1 , n 2 , , n m ( n = i = 1 m n i ) . We endow χ with the inner product and norm:

X , Y = t r [ X T Y ] , X = X , X = i = 1 n λ i ( X ) 2 , (1.1)

where X , Y χ and t r [ ] denotes the matrix trace, X is the Frobenius-norm of X and λ i ( X ) stands for the i-eigenvalue of X. Let S denote the subspace comprising those X χ that are symmetric, i.e., X T = X . We denote by S + ( S + + ) the cone of symmetric positive semidefinite (positive definite) matrices in S , We use the symbol X ( ) 0 to say that X S + ( S + + ) . To facilitate the presentation, let X j , Y j is the j-th block of X , Y χ , respectively. The SDCP is to find, for given mapping F : S S , an ( X , Y ) S × S satisfying

X 0, Y 0, X , Y = 0, Y = F ( X ) . (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 * -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 * -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 , Y S + n , it holds that X , Y λ ( X ) T λ ( Y ) , with equality if and only if X and Y are simultaneously diagonalizable, where λ ( X ) , λ ( Y ) is the eigenvalue vector of X and Y , respectively.

Proposition 2.2 Let X , Y S + n , if X , Y = 0 , then X and Y commute, i.e., X and Y are simultaneously diagonalizable.

Proposition 2.3 (Fejer’s theorem) Let X S n , it holds that X , Y 0 for all Y 0 if and only if X 0 . Moreover, X , Y > 0 for all Y 0 if and only if X 0 .

Now, we present the definition and the property of P * -mapping and exceptional family of elements for SDCP on the subspace S .

Definition 2.1 A mapping F : S S is said to be a P * -mapping, if there exists a nonnegative constant γ such that the following inequality holds for any distinct X , Y S ,

( 1 + γ ) j I + ( X , Y , F ) X j Y j , F j ( X ) F j ( Y ) + j I ( X , Y , F ) X j Y j , F j ( X ) F j ( Y ) 0 , (2.1)

where I + ( X , Y , F ) = { j I : X j Y j , F j ( X ) F j ( Y ) > 0 } , I ( X , Y , F ) = { j I : X j Y j , F j ( X ) F j ( Y ) 0 } and I = { 1 , 2 , , m } .

Definition 2.2 [2] A sequence { X r } r > 0 = { d i a g ( X 1 r , X 2 r , , X m r ) } r > 0 S + is

said to an exceptional family of elements for SDCP if and only if for any r and every i I , there exists a real number μ i r > 0 such that

F i ( X r ) + μ i r X i r 0 , F i ( X r ) + μ i r X i r , X i r = 0 , (2.2)

i = 1 m X i r 2 + , r + . (2.3)

Theorem 2.1 [12] If F : S 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 0 , C i 0 is a matrix of size n i × n i and l i m r + X i r + , then there exists a subsequence { X i r n } such that { X i r n , C i } 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 = j = 1 n i λ j r ξ j r ξ j r T , C i = l = 1 n i γ l η l η l T , (3.1)

where λ j r , γ l is the eigenvalue of X i r , C i , respectively. ξ j r , η l is the corresponding eigenvector, respectively. Noting that X i r 0, C i 0 , we have that

λ j r 0 , γ l > 0. (3.2)

In view of l i m r + X i r + and X i r = j = 1 n i ( λ j r ) 2 , thus, there exists a j 0

such that { λ j 0 r } is unbounded. The above relation also show that there exists a

subsequence { r k } such that l i m r k + λ j 0 r k + .

The next object is to show that there exists l * such that ξ j 0 r T η l * 0 .

Assume that ξ j 0 r T η l = 0 for any l , one gets

A ξ j 0 = 0 , A = [ η 1 T η 2 T η n i T ] . (3.3)

Since A is a nonsingular, then we have ξ j 0 r = 0 . This is a contradiction. Combining the above relations, we have

λ j 0 r k γ l * ( ξ j 0 r k T η l * ) 2 + , as r k + . (3.4)

Hence

X i r , C i = j = 1 n i l = 1 n i λ j r γ l ( ξ j r T η l ) 2 = λ j 0 r k γ l * ( ξ j 0 r k T η l * ) 2 + j = 1 , j j 0 n i l = 1 , l l * n i λ j r γ l ( ξ j r T η l ) 2 λ j 0 r k γ l * ( ξ j 0 r k T η l * ) 2 + , as r k + . (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 0 , V 0 and U , V = 0 , then V = 0 .

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

Lemma 3.3 If { U r } S + and l i m r + U r + , and U ^ is a cluster point of { U r U r } , then U ^ S + and U ^ = 1 .

Now, we present our main results as follows.

Theorem 3.1 If F : S S is a continuous P * mapping and there exists a strict feasible point for SDCP, i.e., X 0 0, F ( X 0 ) 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

{ X r } r > 0 = { d i a g ( X 1 r , X 2 r , , X m r ) } r > 0 S + for SDCP, and for every i I , there exists a real number μ i r > 0 such that

F i ( X r ) + μ i r X i r 0, F i ( X r ) + μ i r X i r , X i r = 0, (3.6)

i = 1 m X i r 2 + , r + . (3.7)

Let U i r = F i ( X r ) + μ i r X i r . From the above first equation, one gets U i r 0 . Thus, for any i I , taking into account the above second equation and Proposition 2.3, we have

X i r X i 0 , F i ( X r ) F i ( X 0 ) = X i r X i 0 , U i r μ i r X i r F i ( X 0 ) = μ i r X i r 2 X i 0 , U i r μ i r X i r , X i 0 X i r X i 0 , F i ( X 0 ) μ i r X i r 2 μ i r X i r , X i 0 X i r X i 0 , F i ( X 0 ) μ i r X i r ( X i r X i 0 ) X i r X i 0 , F i ( X 0 ) . (3.8)

Denote by I 1 = { i I : X i r + , r + } , I 2 = I \ I 1 . Obviously, I 1 and

X r X 0 , F ( X r ) F ( X 0 ) = i I 1 X i r X i 0 , F i ( X r ) F i ( X 0 ) + i I 2 X i r X i 0 , F i ( X r ) F i ( X 0 ) . (3.9)

When i I 2 , we have that there exists a upper boundedness for { X i r X i 0 , F i ( X r ) F i ( X 0 ) } from the formula (3.8).

When i I 1 , one gets X i r > X i 0 for sufficient large k. Noticing that X r 0, F i ( X 0 ) 0 , from Lemma 3.1, we have that for any i I 1 , there exists a subsequence { X i r n } such that l i m r n + X i r n , F i ( X 0 ) + . Thus, l i m r n + X i r n X i 0 , F i ( X 0 ) + . In view of the formula (3.8), one gets

l i m r n + X i r n X i 0 , F i ( X r ) F i ( X 0 ) , (3.10)

which implies that

l i m r n + X r n X 0 , F ( X r ) F ( X 0 ) . (3.11)

This is a contradiction with F being a P * -mapping. The proof is complete.

Theorem 3.2 If F : S S is a continuous P * -mapping and there exists a strict feasible point for SDCP, i.e., X 0 0, F ( X 0 ) 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 { X k } such that l i m k + X k + . Obviously,

X k 0, F ( X k ) 0, X k , F ( X k ) = 0, k . (3.12)

Noting that F is a P * mapping, we have that for any k,

( 1 + γ ) j I + ( X 0 , X k , F ) X j 0 X j k , F j ( X 0 ) F j ( X k ) + j I ( X 0 , X k , F ) X j 0 X j k , F j ( X 0 ) F j ( X k ) 0 , (3.13)

i.e.,

X 0 X k , F ( X 0 ) F ( X k ) γ j I + ( X 0 , X k , F ) X j 0 X j k , F j ( X 0 ) F j ( X k ) . (3.14)

From the formula (3.12), one gets

X 0 , F ( X k ) + F ( X 0 ) , X k + γ j I + ( X 0 , X k , F ) [ X j 0 , F j ( X k ) + X j k , F j ( X 0 ) ] X 0 , F ( X 0 ) + γ j I + ( X 0 , X k , F ) X j 0 , F j ( X 0 ) . (3.15)

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

F ( X 0 ) , X k X 0 , F ( X 0 ) + γ j I + ( X 0 , X k , F ) X j 0 , F j ( X 0 ) . (3.16)

Noting that { X k X k } is bounded. Hence, there exists a subsequence { X k n } such that

lim k n + X k n X k n = X ¯ . (3.17)

From Lemma 3.3, we have that X ¯ ± 0 , X ¯ = 1 .

On the other hand, from (3.16), one gets for any k n

F ( X 0 ) , X k n X k n = F ( X 0 ) , X k n X k n X 0 , F ( X 0 ) + γ j I + ( X 0 , X k , F ) X j 0 , F j ( X 0 ) X k n . (3.18)

Since lim k n + X k n + , then

F ( X 0 ) , X ¯ 0. (3.19)

Obviously, F ( X 0 ) , X ¯ 0 . Thus, F ( X 0 ) , X ¯ = 0 , which implies that X ¯ = 0 from Lemma 3.2. This is a contradiction with X ¯ = 1 . The proof is complete.

4. Conclusion

In this paper, the nonemptyness and boundedness of the solution set for P * -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. and Han, C. (2018) Some Properties of Solution to Semidefinite Complementarity Problem. Journal of Applied Mathematics and Physics, 6, 122-129. doi: 10.4236/jamp.2018.61012.
References

[1]   Kojima, M., Shindoh, S. and Hara, S. (1997) Interior Point Methods for The Monotone Semidefinite Linear Complementarity Problem. SIAM Journal on Optimization, 7, 86-125.
https://doi.org/10.1137/S1052623494269035

[2]   Chen, X. and Tseng, P. (2003) Noninterior Point Continuation Methods for Solving Semidefinite Complementarity Problem. Mathematical Programming, 95, 431-474.
https://doi.org/10.1007/s10107-002-0306-1

[3]   Tseng, P. (1998) Merit Functions for Semidefinite Complementarity Problem. Mathematical Programming, 83, 159-185.
https://doi.org/10.1007/BF02680556

[4]   Smith, T.E. (1984) A Solution Condition for Complementarity Problems: With an Application to Spatial Price Equilibrium. Applied Mathematics and Computation, 15, 61-69.
https://doi.org/10.1016/0096-3003(84)90053-5

[5]   Isac, G., Bulavaski, V. and Kalashnikov, V. (1997) Exceptional Families, Topological Degree and Complementarity Problems. Journal of Global Optimization, 10, 207-225.
https://doi.org/10.1023/A:1008284330108

[6]   Isac, G. and Carbone, A. (1999) Exceptional Families of Elements for Continous Functions: Some Applications to Complementarity Theory. Journal of Global Optimization, 15, 181-196.
https://doi.org/10.1023/A:1008376709933

[7]   Isac, G. Obuchowska, W.T. (1998) Functions without Exceptional Family of Elements and Complementarity Problems. Journal of Optimization Theory and Applications, 99, 147-163.
https://doi.org/10.1023/A:1021704311867

[8]   Zhao, Y.B. Han, J.Y. and Qi, H.D. (1999) Exceptional Families and Existence Theorems for Variational Inequality Problems. Journal of Optimization Theory and Applications, 101, 475-495.
https://doi.org/10.1023/A:1021701913337

[9]   Zhao, Y.B. and Han, J.Y. (1999) Exceptional Families of Elements for a Variational Inequality Problem and Its Applications. Journal of Global Optimization, 14, 313-330.
https://doi.org/10.1023/A:1008202323884

[10]   Zhang, L.P., Han, J.Y. and Xu, D.C. (2001) Existence Theorems of Solution to Variational Inequality Problems. Science in China Series A: Mathematics, 44, 212-219.
https://doi.org/10.1007/BF02874423

[11]   Zhao, Y.B. (1997) Exceptional Families and Finite Dimensional Variational Inequalities over Polyhedral Convex Sets. Applied Mathematics and Computation, 87, 111-126.
https://doi.org/10.1016/S0096-3003(96)00224-X

[12]   Zhang, L.P. (2008) Solvability of Semidefinite Complementarity Problems. Applied Mathematics and Computation, 196, 86-93.
https://doi.org/10.1016/j.amc.2007.05.052

[13]   Hu, Q.J., Ouyang, Z.S. and Wang, Z.M. (2012) Exceptional Family and Solvability of Copositive Complementarity Problems. Journal of Mathematical Analysis and Applications, 388, 519-524.
https://doi.org/10.1016/j.jmaa.2011.10.028

[14]   Hu, Q.J., Chen, Y., Wang, J.T. and Ouyang, Z.S. (2013) Generalization of an Existence Theorem for Complementarity Problems. Journal of Computational and Applied Mathematics, 253, 158-162.
https://doi.org/10.1016/j.cam.2013.04.017

[15]   Horn, R.A. and Johnson, C.R. (1985) Matrix Analysis. Cambridge University Press, Cambridge.
https://doi.org/10.1017/CBO9780511810817

[16]   Horn, R.A. and Johnson, C.R. (1991) Topics in Matrix Analysis. Cambridge University Press, Cambridge.
https://doi.org/10.1017/CBO9780511840371

 
 
Top