A new smoothing spectral conjugate gradient method for solving tensor complementarity problems

ShiChun Lv; Shou-Qiang Du

doi:10.3934/jimo.2021150

Article Contents

2022, Volume 18, Issue 6: 4111-4127. Doi: 10.3934/jimo.2021150

This issue Previous Article Human resources optimization with MARS and ANN: Innovation geolocation model for generation Z Next Article Lagrangian relaxation algorithm for the truck scheduling problem with products time window constraint in multi-door cross-dock

A new smoothing spectral conjugate gradient method for solving tensor complementarity problems

ShiChun Lv and
Shou-Qiang Du^,

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

^* Corresponding author: Shou-Qiang Du
^* Corresponding author: Shou-Qiang Du

Received: December 2020

Revised: May 2021

Early access: September 2021

Published: September 2022

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

Abstract

In recent years, the tensor complementarity problem has attracted widespread attention and has been extensively studied. The research work of tensor complementarity problem mainly focused on theory, solution methods and applications. In this paper, we study the solution method of tensor complementarity problem. Based on the equivalence relation of the tensor complementarity problem and unconstrained optimization problem, we propose a new smoothing spectral conjugate gradient method with Armijo line search. Under mild conditions, we establish the global convergence of the proposed method. Finally, some numerical results are given to show the effectiveness of the proposed method and verify our theoretical results.

Keywords:

Tensor complementarity problem,
Unconstrained optimization,
Smoothing spectral conjugate gradient method,
Global convergence.

Mathematics Subject Classification: Primary: 90C33, 65K05; Secondary: 15A69.

Citation:

Full Text(HTML)

Figure 1. Numerical results of Example 4.1 with different vector $ q $

Download: Full-size image PowerPoint slide

Figure 2. Numerical results of Example 4.2 with different vector $ q $

Download: Full-size image PowerPoint slide

Figure 3. Numerical results of Example 4.3 with different vector $ q $

Download: Full-size image PowerPoint slide

Figure 4. Numerical results of Example 4.4 with different initial points

Download: Full-size image PowerPoint slide

Figure 5. 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

x0	Sol	Val
$ (0.8333, 0.2037, 0.5444, 0.8749)^T $	$ (0.0000, 0.0000, 0.0000, 0.0000)^T $	1.9158e-15
$ (0.9460, 0.0916, 0.9084, 0.5100)^T $	$ (0.0000, 0.0000, 0.0000, 0.0000)^T $	2.9449e-14
$ (0.1445, 0.3705, 0.6224, 0.9976)^T $	$ (0.0000, 0.0000, 0.0000, 0.0000)^T $	2.1031e-15
$ (0.6966, 0.0646, 0.7477, 0.4204)^T $	$ (0.0000, 0.0000, 0.0000, 0.0000)^T $	8.9036e-14
$ (0.8113, 0.3796, 0.3191, 0.9861)^T $	$ (0.0000, 0.0000, 0.0000, 0.0000)^T $	4.1630e-14

| Show Table

DownLoad: CSV

Table 2. The numerical results of Example 4.2

q	Sol	K	Val
$ (1, 2, 3)^T $	$ (0.0000, 0.0000, 0.0000)^T $	7	2.8222e-13
$ (1, -2, 3)^T $	$ (0.0000, 1.0000, 0.0000)^T $	70	3.1532e-13
$ (3, 3, 3)^T $	$ (0.0000, 0.0000, 0.0000)^T $	6	2.1459e-14
$ (-3, -2, -3)^T $	$ (1.3161, 1.0000, 1.0000)^T $	16	1.0256e-15
$ (-3, -1, -2)^T $	$ (1.3161, 0.8409, 0.9036)^T $	19	1.1984e-14

| Show Table

DownLoad: CSV

Table 3. The numerical results of Example 4.3

q	Sol	K	Val
$ (5, 3)^T $	$ (0.0000, 0.0000)^T $	7	8.9458e-14
$ (2, -3)^T $	$ (0.0000, 1.7321)^T $	76	2.6588e-13
$ (-5, -3)^T $	$ (0.3127, 1.9233)^T $	30	9.4915e-14
$ (-5, 3)^T $	$ (1.5513, 0.6847)^T $	55	2.0370e-14
$ (0, -5)^T $	$ (0.0000, 2.2361)^T $	34	7.5750e-14

| Show Table

DownLoad: CSV

Table 4. The numerical results of Example 4.4

Alg.	x0	Sol	K	Val
Algorithm 3.1	$ (0.3804, 0.5678)^T $	$ (0.0000, 0.0000)^T $	7	2.9601e-13
Algorithm 3.1	$ (0.0759, 0.0540)^T $	$ (0.0000, 0.0000)^T $	7	2.9600e-13
Algorithm 3.1	$ (0.9340, 0.1299)^T $	$ (0.0000, 0.0000)^T $	6	9.5895e-15
Algorithm 3.1	$ (0.1622, 0.7943)^T $	$ (0.0000, 0.0000)^T $	6	4.5196e-13
Algorithm 3.1	$ (0.3112, 0.5285)^T $	$ (0.0000, 0.0000)^T $	7	2.9601e-13
MIP	-	$ (0.0000, 0.0000)^T $	39	-
MIP	-	$ (0.0000, 0.0000)^T $	29	-

| Show Table

DownLoad: CSV

Table 5. The numerical results of Example 4.5

x0	K	Val
$ (0.7655, 0.7951, 0.1868, 0.4897, 0.4455, 0.6463)^T $	10	3.0376e-13
$ (0.7094, 0.7547, 0.2760, 0.6797, 0.6551, 0.1626)^T $	12	2.7860e-15
$ (0.5472, 0.1386, 0.1493, 0.2575, 0.8407, 0.2543)^T $	10	1.9144e-13
$ (0.8143, 0.2435, 0.9293, 0.3500, 0.1966, 0.2511)^T $	10	1.7226e-13
$ (0.6160, 0.4733, 0.3517, 0.8308, 0.5853, 0.5497)^T $	9	1.2683e-14

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	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.
[2]	M. Aliyu, P. Kumam and B. Auwal, A modified conjugate gradient method for monotone nonlinear equations with convex constraints, Appl. Numer. Math., 145 (2019), 507-520. doi: 10.1016/j.apnum.2019.05.012.
[3]	S. Babaie-Kafaki, R. Ghanbari and N. Mahdavi-Amiri, Two new conjugate gradient methods based on modified secant equations, J. Comput. Appl. Math., 234 (2010), 1374-1386. doi: 10.1016/j.cam.2010.01.052.
[4]	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.
[5]	J. Barzilai and J. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal., 8 (1988), 141-148. doi: 10.1093/imanum/8.1.141.
[6]	E. Birgin and J. Martínez, A spectral conjugate gradient method for unconstrained optimization, Appl. Math. Optim., 43 (2001), 117-128. doi: 10.1007/s00245-001-0003-0.
[7]	S. Bojari and M. Eslahchi, Two families of scaled three-term conjugate gradient methods with sufficient descent property for nonconvex optimization, Numer. Algor., 83 (2020), 901-933. doi: 10.1007/s11075-019-00709-7.
[8]	K. Chang, K. Pearson and T. Zhang, Perron-Frobenius theorem for nonnegative tensors, Commun. Math. Sci., 6 (2008), 507-520. doi: 10.4310/CMS.2008.v6.n2.a12.
[9]	M. Che, L. Qi and Y. Wei, Positive-definite tensors to nonlinear complementarity problems, J. Optim. Theory Appl., 168 (2016), 475-487. doi: 10.1007/s10957-015-0773-1.
[10]	B. Chen and P. Harker, Smooth approximations to nonlinear complementarity problems, SIAM J. Optim., 7 (1997), 403-420. doi: 10.1137/S1052623495280615.
[11]	C. Chen and L. Zhang, Finding Nash equilibrium for a class of multi-person noncooperative games via solving tensor complementarity problem, Appl. Number. Math., 145 (2019), 458-468. doi: 10.1016/j.apnum.2019.05.013.
[12]	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.
[13]	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.
[14]	W. Ding, L. Qi and Y. Wei, $\mathcal M$-tensors and nonsingular $\mathcal M$-tensors, Linear Algebra Appl., 439 (2013), 3264-3278. doi: 10.1016/j.laa.2013.08.038.
[15]	W. Ding and Y. Wei, Solving multi-linear systems with $\mathcal M$-tensors, J. Sci. Comput., 68 (2016), 689-715. doi: 10.1007/s10915-015-0156-7.
[16]	W. Ding, Z. Luo and L. Qi, $\mathcal P$-tensors, $\mathcal P_0$-tensors, and their applications, Linear Algebra Appl., 555 (2018), 336-354. doi: 10.1016/j.laa.2018.06.028.
[17]	S. Du, L. Zhang, C. Chen and L. Qi, Tensor absolute value equations, Sci. China Math., 61 (2018), 1695-1710. doi: 10.1007/s11425-017-9238-6.
[18]	S. Du and L. Zhang, A mixed integer programming approach to the tensor complementarity problem, J. Glob. Optim., 73 (2019), 789-800. doi: 10.1007/s10898-018-00731-4.
[19]	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.
[20]	R. Fletcher and C. Reeves, Function minimization by conjugate gradients, Comput. J., 7 (1964), 149-154. doi: 10.1093/comjnl/7.2.149.
[21]	M. Gowda, Z. Luo, L. Qi and N. Xiu, $\mathcal Z$-tensors and complementarity problems, arXiv: 1510.07933v2
[22]	W. Hager and H. Zhang, A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM J. Optim., 16 (2005), 170-192. doi: 10.1137/030601880.
[23]	L. Han, A continuation method for tensor complementarity problems, J. Optim. Theory Appl., 180 (2019), 949-963. doi: 10.1007/s10957-018-1422-2.
[24]	M. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards, 49 (1952), 409-436. doi: 10.6028/jres.049.044.
[25]	S. Hu, Z. Huang, C. Ling and L. Qi, On determinants and eigenvalue theory of tensors, J. Symb. Comput., 50 (2013), 508-531. doi: 10.1016/j.jsc.2012.10.001.
[26]	Z. Huang and L. Qi, Formulating an n-person noncoorperative game as a tensor complementarity problem, Comput. Optim. Appl., 66 (2017), 557-576. doi: 10.1007/s10589-016-9872-7.
[27]	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.
[28]	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.
[29]	X. Jiang and J. Jian, Improved Fletcher-Reeves and Dai-Yuan conjugate gradient methods with the strong Wolfe line search, J. Comput. Appl. Math., 348 (2019), 525-534. doi: 10.1016/j.cam.2018.09.012.
[30]	Y. Li, S. Du and L. Zhang, Tensor quadratic eigenvalue complementarity problem, Pac. J. Optim., 17 (2021), 251-268.
[31]	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.
[32]	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.
[33]	C. Ling, W. Yan, H. He and L. Qi, Further study on tensor absolute value equations, Sci. China Math., 63 (2020), 2137-2156. doi: 10.1007/s11425-018-9560-3.
[34]	D. Liu, W. Li and S. Vong, Tensor complementarity problems: The GUS-property and an algorithm, Linear Multilinear A., 66 (2018), 1726-1749. doi: 10.1080/03081087.2017.1369929.
[35]	J. Liu, S. Du and Y. Chen, A sufficient descent nonlinear conjugate gradient method for solving $\mathcal M$-tensor equations, J. Comput. Appl., 371 (2020), 112709. doi: 10.1016/j.cam.2019.112709.
[36]	I. Livieris and P. Pintelas, A new class of spectral conjugate gradient methods based on a modified secant equation for unconstrained optimization, J. Comput. Appl. Math., 239 (2013), 396-405. doi: 10.1016/j.cam.2012.09.007.
[37]	Z. Luo, L. Qi and N. Xiu, The sparsest solutions to $\mathcal Z$-tensor complementarity problems, Optim. Lett., 11 (2017), 471-482. doi: 10.1007/s11590-016-1013-9.
[38]	G. Meurant, On prescribing the convergence behavior of the conjugate gradient algorithm, Numer. Algor., 84 (2020), 1353-1380. doi: 10.1007/s11075-019-00851-2.
[39]	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.
[40]	M. Powell, Restart procedures for the conjugate gradient method, Math. Program., 12 (1977), 241-254. doi: 10.1007/BF01593790.
[41]	L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symb. Comput., 40 (2005), 1302-1324. doi: 10.1016/j.jsc.2005.05.007.
[42]	L. Qi, Symmetric nonnegative tensors and copositive tensors, Linear Algebra Appl., 439 (2013), 228-238. doi: 10.1016/j.laa.2013.03.015.
[43]	L. Qi and Z. Luo, Tensor Analysis: Spectral Theory and Special Tensors, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2017. doi: 10.1137/1.9781611974751.ch1.
[44]	L. Qi, H. Chen and Y. Chen, Tensor Eigenvalues and Their Applications, Advances in Mechanics and Mathematics, 39. Springer, Singapore, 2018. doi: 10.1007/978-981-10-8058-6.
[45]	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.
[46]	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.
[47]	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.
[48]	Y. Song and L. Qi, Properties of tensor complementarity problem and some classes of structured tensors, Ann. Appl. Math., 33 (2017), 308-323.
[49]	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.
[50]	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.
[51]	X. Wang, M. Che and Y. Wei, Preconditioned tensor splitting AOR iterative methods for $\mathcal H$-tensor equations,, Numer. Linear Algebra Appl., 27 (2020), e2329. doi: 10.1002/nla.2329.
[52]	Y. Wei and W. Ding, Theory and Computation of Tensors: Multi-Dimensional Arrays, Academic Press, London, 2016.
[53]	S. Xie, D. Li and H. Xu, An iterative method for finding the least solution to the tensor complementarity problem, J. Optim. Theory Appl., 175 (2017), 119-136. doi: 10.1007/s10957-017-1157-5.
[54]	H. Xu, D. Li and S. Xie, An equivalent tensor equation to the tensor complementarity problem with positive semi-definite $\mathcal Z$-tensor, Optim. Lett., 13 (2019), 685-694. doi: 10.1007/s11590-018-1268-4.
[55]	Y. Yang and Q. Yang, Further results for Perron-Frobenius theorem for nonnegative tensors II, SIAM J. Matrix Anal. Appl., 32 (2011), 1236-1250. doi: 10.1137/100813671.
[56]	Y. Yang and Q. Yang, A Study on Eigenvalues of Higher-Order Tensors and Related Polynomial Optimization Problems, Science Press, Beijing, 2015.
[57]	G. Yu, L. Guan and W. Chen, Spectral conjugate gradient methods with sufficient descent property for large-scale unconstrained optimization, Optim. Methods Softw., 23 (2008), 275-293. doi: 10.1080/10556780701661344.
[58]	G. Yuan, X. Wang and Z. Sheng, Family weak conjugate gradient algorithms and their convergence analysis for nonconvex functions, Numer. Algor., 84 (2020), 935-956. doi: 10.1007/s11075-019-00787-7.
[59]	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.
[60]	L. Zhang, W. Zhou and D. Li, Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search, Numer. Math., 104 (2006), 561-572. doi: 10.1007/s00211-006-0028-z.
[61]	L. Zhang and W. Zhou, On the global convergence of the Hager-Zhang conjugate gradient method with the Armijo line search, Acta Math. Sci., 28 (2008), 840-845.
[62]	L. Zhang, L. Qi and G. Zhou, $\mathcal M$-tensors and some applications, SIAM J. Matrix Anal. Appl., 35 (2014), 437-452. doi: 10.1137/130915339.
[63]	G. Zhou, L. Qi and S. Wu, On the largest eigenvalue of a symmetric nonnegative tensor, Numer. Linear Algebra Appl., 20 (2013), 913-928. doi: 10.1002/nla.1885.