Modified spectral PRP conjugate gradient method for solving tensor eigenvalue complementarity problems

Ya Li; ShouQiang Du; YuanYuan Chen

doi:10.3934/jimo.2020147

Article Contents

2022, Volume 18, Issue 1: 157-172. Doi: 10.3934/jimo.2020147

This issue Previous Article An alternative tree method for calibration of the local volatility Next Article Effect of reliability on varying demand and holding cost on inventory system incorporating probabilistic deterioration

Modified spectral PRP conjugate gradient method for solving tensor eigenvalue complementarity problems

School of Mathematics and Statistics, Qingdao University, Qingdao, 266071, China

^* Corresponding author: ShouQiang Du
^* Corresponding author: ShouQiang Du

Received: January 2020

Revised: June 2020

Early access: September 2020

Published: January 2022

Abstract Full Text(HTML) Figure(2) / Table(4) Related Papers Cited by

Abstract

Tensor eigenvalue complementary problems, as a special class of complementary problems, are the generalization of matrix eigenvalue complementary problems in higher-order. In recent years, tensor eigenvalue complementarity problems have been studied extensively. The research fields of tensor eigenvalue complementarity problems mainly focus on analysis of the theory and algorithms. In this paper, we investigate the solution method for four kinds of tensor eigenvalue complementarity problems with different structures. By utilizing an equivalence relation to unconstrained optimization problems, we propose a modified spectral PRP conjugate gradient method to solve the tensor eigenvalue complementarity problems. Under mild conditions, the global convergence of the given method is also established. Finally, we give related numerical experiments and numerical results compared with inexact Levenberg-Marquardt method, numerical results show the efficiency of the proposed method and also verify our theoretical results.

Keywords:

Unconstrained optimization,
PRP conjugate gradient method,
tensor eigenvalue complementarity problem,
global convergence.

Mathematics Subject Classification: Primary: 90C30, 65K05; Secondary: 15A18.

Citation:

Full Text(HTML)

Figure 1. Numerical results of Example 4.1 with random initial points

Download: Full-size image PowerPoint slide

Figure 2. Numerical results of Example 4.5 with different initial points

Download: Full-size image PowerPoint slide

Table 1. The numerical results of Example 4.1

Eigvalue	Eigvector	No
1.9406	$ (0.4982, 0.5018)^T $	24
2.0469	$ (0.8817, 0.1183)^T $	5
2.6308	$ (0.0000, 1.0000)^T $	1

| Show Table

DownLoad: CSV

Table 2. The numerical results of Example 4.2

Alg.	Eigvalue	Eigvector	No.	K
Algorithm 3.1	0.3024	$ (0.5479, 1.0000, 0.4521)^T $	3	69
Algorithm 3.1	0.2356	$ (0.5037, 0.4963, 0.0000)^T $	2	56
Algorithm 3.1	0.2089	$ (0.0000, 0.4911, 0.5089)^T $	1	41
Algorithm 3.1	0.0771	$ (0.3328, 0.3372, 0.3301)^T $	3	183
Algorithm 3.1	$ failure $	$ - $	1	-
ILMM	0.2089	$ (0.0000, 0.4911, 0.5089)^T $	2	26
ILMM	0.2356	$ (0.5037, 0.4963, 0.0000)^T $	2	41
ILMM	0.3024	$ (0.5479, 1.0000, 0.4521)^T $	1	45
ILMM	0.9807	$ (0.0000, 1.0000, 0.0000)^T $	1	119
ILMM	$ failure $	-	4	-

| Show Table

DownLoad: CSV

Table 3. The numerical results of Example 4.3

Eigvalue	Eigvector	No
0.8867	$ (1.0000, 0.0000)^T $	2
0.9533	$ (0.0000, 1.0000)^T $	4
0.6	$ (0.6, 0.4)^T $	14

| Show Table

DownLoad: CSV

Table 4. The numerical results of Example 4.4

Eigvalue	Eigvector	No
2.9167	$ (0.0232, 0.0000, 0.9967)^T $	3
2.9865	$ (0.0712, 0.0252, 0.9971)^T $	2
0.3	$ (0.1, 0, 0.1)^T $	1
failure		4

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	S. Adly and H. Rammal, A new method for solving Pareto eigenvalue complementarity problems, Comput. Optim. Appl., 55 (2013), 703-731. doi: 10.1007/s10589-013-9534-y.
[2]	M. Al-Baali, Y. Narushima and H. Yabe, A family of three-term conjugate gradient methods with sufficient descent property for unconstrained optimization, Comput. Optim. Appl., 60 (2015), 89-110. doi: 10.1007/s10589-014-9662-z.
[3]	X. Bai, Z. Huang and Y. Wang, Global uniqueness and solvability for tensor complementarity problems, J. Optim. Theory Appl., 170 (2016), 72-84. doi: 10.1007/s10957-016-0903-4.
[4]	X. Bai, Z. Huang and X. Li, Stability of solutions and continuity of solution maps of tensor complementarity problems,, Asia-Pacific J. Oper. Res., 36 (2019), 1940002, 19 pp. doi: 10.1142/S0217595919400025.
[5]	E. Birgin and J. Martinez, A spectral conjugate gradient method for unconstrained optimization, Appl. Math. Optim., 43 (2001), 117-128. doi: 10.1007/s00245-001-0003-0.
[6]	S. Bojari and M. R. Eslahchi, Two families of scaled three-term conjugate gradient methods with sufficient descent property for nonconvex optimization, Numer. Algorithms, 83 (2020), 901-933. doi: 10.1007/s11075-019-00709-7.
[7]	K. Chang, K. Pearson and T. Zhang, On eigenvalue problems of real symmetric tensors, J. Math. Anal. Appl., 350 (2009), 416-422. doi: 10.1016/j.jmaa.2008.09.067.
[8]	M. Che, L. Qi and Y. Wei, Positive-defifinite tensors to nonlinear complementarity problems, J. Optim. Theory Appl., 168 (2016), 475-487. doi: 10.1007/s10957-015-0773-1.
[9]	Z. Chen, Q. Yang and L. Ye, Generalized eigenvalue complementarity problem for tensors, Pacific J. Optim., 13 (2017), 527-545.
[10]	Z. Chen and L. Qi, A semismooth Newton method for tensor eigenvalue complementarity problem, Comput. Optim. Appl., 65 (2016), 109-126. doi: 10.1007/s10589-016-9838-9.
[11]	Y. Dai and Y. Yuan, A nonlinear conjugate gradient method with a strong global convergence property, SIAM J. Optim., 10 (1999), 177-182. doi: 10.1137/S1052623497318992.
[12]	Y. Dai, L. Liao and D. Li, On restart procedures for the conjugate gradient method, Numer. Algor., 35 (2004), 249-260. doi: 10.1023/B:NUMA.0000021761.10993.6e.
[13]	W. Ding, L. Qi and Y. Wei, M-tensors and nonsingular M-tensors, Linear Algebra Appl., 439 (2013), 3264-3278. doi: 10.1016/j.laa.2013.08.038.
[14]	S. Du, M. Che and Y. Wei, Stochastic structured tensors to stochastic complementarity problems, Comput. Optim. Appl., 75 (2020), 649-668. doi: 10.1007/s10589-019-00144-3.
[15]	S. Du and L. Zhang, A mixed integer programming approach to the tensor complementarity problem, J. Global Optim., 39 (2019), 789-800. doi: 10.1007/s10898-018-00731-4.
[16]	J. Fan, J. Nie and A. Zhou, Tensor eigenvalue complementarity problems, Math. Program., 170 (2018), 507-539. doi: 10.1007/s10107-017-1167-y.
[17]	Z. Huang and L. Qi, Tensor complementarity problems-Part I: Basic theory, J. Optim. Theory Appl., 183 (2019), 1-23. doi: 10.1007/s10957-019-01566-z.
[18]	Z. Huang and L. Qi, Tensor complementarity problems-Part III: Applications, J. Optim. Theory Appl., 183 (2019), 771-791. doi: 10.1007/s10957-019-01573-0.
[19]	T. Kolda and J. Mayo, Shifted power method for computing tensor eigenpairs, SIAM J. Matrix Anal. Appl., 32 (2011), 1095-1124. doi: 10.1137/100801482.
[20]	H. Li, S. Du, Y. Wang and M. Chen, An inexact Levenberg-Marquardt method for tensor eigenvalue complementarity problem, Pacific J. Optim., 16 (2020), 87-99.
[21]	C. Ling, H. He and L. Qi, On the cone eigenvalue complementarity problem for higher-order tensors, Comput. Optim. Appl., 63 (2016), 143-168. doi: 10.1007/s10589-015-9767-z.
[22]	C. Ling, H. He and L. Qi, Higher-degree eigenvalue complementarity problems for tensors, Comput. Optim. Appl., 64 (2016), 149-176. doi: 10.1007/s10589-015-9805-x.
[23]	Y. Liu and Q. Yang, A New Eigenvalue Complementarity Problem for Tensor and Matrix, Nankai University, 2018.
[24]	G. Meurant, On prescribing the convergence behavior of the conjugate gradient algorithm, Numer. Algorithms, 84 (2020), 1353-1380. doi: 10.1007/s11075-019-00851-2.
[25]	M. Ng, L. Qi and G. Zhou, Finding the largest eigenvalue of a non-negative tensor, SIAM J. Matrix Anal. Appl., 31 (2009), 1090-1099. doi: 10.1137/09074838X.
[26]	Q. Ni and L. Qi, A quadratically convergent algorithm for finding the largest eigenvalue of a nonnegative homogeneous polynomial map, J. Global Optim., 61 (2015), 627-641. doi: 10.1007/s10898-014-0209-8.
[27]	L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symb. Comput., 40 (2005), 1302-1324. doi: 10.1016/j.jsc.2005.05.007.
[28]	L. Qi and Z. Luo, Tensor Analysis: Spectral Theory and Special Tensors, SIAM, Philadelphia, 2017. doi: 10.1137/1.9781611974751.ch1.
[29]	L. Qi, H. Chen and Y. Chen, Tensor Eigenvalues and Their Applications, Springer, Singapore, 2018. doi: 10.1007/978-981-10-8058-6.
[30]	L. Qi, Symmetric nonnegative tensors and copositive tensors, Linear Algebra Appl., 439 (2013), 228-238. doi: 10.1016/j.laa.2013.03.015.
[31]	L. Qi and Z. Huang, Tensor complementarity problems-Part II: Solution methods, J. Optim. Theory Appl., 183 (2019), 365-385. doi: 10.1007/s10957-019-01568-x.
[32]	A. Seeger, Quadratic eigenvalue problems under conic constraints, SIAM J. Matrix Anal. Appl., 32 (2011), 700-721. doi: 10.1137/100801780.
[33]	Y. Song and L. Qi, Properties of tensor complementarity problem and some classes of structured tensors, Ann. Appl. Math., 33 (2017), 308-323.
[34]	Y. Song and L. Qi, Properties of some classes of structured tensors, J. Optim. Theory Appl., 165 (2015), 854-873. doi: 10.1007/s10957-014-0616-5.
[35]	Y. Song and L. Qi, Tensor complementarity problem and semi-positive tensors, J. Optim. Theory Appl., 169 (2016), 1069-1078. doi: 10.1007/s10957-015-0800-2.
[36]	Y. Song and G. Yu, Properties of solution set of tensor complementarity problem, J. Optim. Theory Appl., 170 (2016), 85-96. doi: 10.1007/s10957-016-0907-0.
[37]	Z. Wan, Z. Yang and Y. Wang, New spectral PRP conjugate gradient method for unconstrained optimization, Appl. Math. Lett., 24 (2011), 16-22. doi: 10.1016/j.aml.2010.08.002.
[38]	X. Wang, M. Che and Y. Wei, Global uniqueness and solvability of tensor complementarity problems for $\mathcal {H}_{+}$-tensors, Numer. Algorithms, 84 (2020), 567-590. doi: 10.1007/s11075-019-00769-9.
[39]	Y. Wang, Z. Huang and X. Bai, Exceptionally regular tensors and tensor complementarity problems, Optim. Methods Softw., 31 (2016), 815-828. doi: 10.1080/10556788.2016.1180386.
[40]	Y. Wei and W. Ding, Theory and Computation of Tensors: Multi-Dimensional Arrays, Academic Press, London, 2016.
[41]	F. Xu and C. Ling, Some properties on Pareto-eigenvalues of higher-order tensors, Oper. Res. Trans., 19 (2015), 34-41.
[42]	W. Yan and C. Ling, Quadratic eigenvalue complememtarity problem for tensor on second-order cone, Journal of Hangzhou Dianzi University., 38 (2018), 90-93.
[43]	Y. Yang and Q. Yang, A Study on Eigenvalues of Higher-Order Tensors and Related Polynomial Optimization Problems, Science Press, Beijing, 2015.
[44]	G. Yu, Y. Song, Y. Xu and Z. Yu, Spectral projected gradient methods for generalized tensor eigenvalue complementarity problems, Numer. Algorithms, 80 (2019), 1181-1201. doi: 10.1007/s11075-018-0522-2.
[45]	G. Yuan, X. Wang and Z. Sheng, Family weak conjugate gradient algorithms and their convergence analysis for nonconvex functions, Numer. Algorithms, 84 (2020), 935-956. doi: 10.1007/s11075-019-00787-7.
[46]	L. Zhang, L. Qi and G. Zhou, M-tensors and some applications, SIAM J. Matrix Anal. Appl., 35 (2014), 437-452. doi: 10.1137/130915339.
[47]	K. Zhang, H. Chen and P. Zhao, A potential reduction method for tensor complementarity problems, J. Ind. Manag. Optim., 15 (2019), 429-443. doi: 10.3934/jimo.2018049.
[48]	L. Zhang and W. Zhou, On the global convergence of the Hager-Zhang conjugate gradient method with Armijo line search, Acta Mathematica Scientia., 28 (2008), 840-845.
[49]	L. Zhang, W. Zhou and D. Li, Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search, Numerische Mathematik., 104 (2006), 561–572. doi: 10.1007/s00211-006-0028-z.
[50]	M. Zheng, Y. Zhang and Z. Huang, Global error bounds for the tensor complementarity problem with a P-tensor, J. Ind. Manag. Optim., 15 (2019), 933-946. doi: 10.3934/jimo.2018078.