A nonmonotone spectral projected gradient method for tensor eigenvalue complementarity problems

Wanbin Tong; Hongjin He; Chen Ling; Liqun Qi

doi:10.3934/naco.2020042

Article Contents

2020, Volume 10, Issue 4: 425-437. Doi: 10.3934/naco.2020042

This issue Previous Article Preface Next Article On box-constrained total least squares problem

A nonmonotone spectral projected gradient method for tensor eigenvalue complementarity problems

Department of Mathematics, School of Science, Hangzhou Dianzi University, Hangzhou, 310018, China

^* Corresponding author: Chen Ling
^* Corresponding author: Chen Ling

Received: February 29, 2020

Revised: August 31, 2020

Published: September 2020

H. He and C. Ling were supported in part by National Natural Science Foundation of China (Nos. 11771113 and 11971138) and Natural Science Foundation of Zhejiang Province (Nos. LY20A010018, LY19A010019, and LD19A010002)

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

Abstract

The tensor eigenvalue complementarity problem (TEiCP) is a higher order extension model of the classical matrix eigenvalue complementarity problem (EiCP), which has been studied extensively in the literature from theoretical perspective to algorithmic design. Due to the high nonlinearity resulted by tensors, the corresponding TEiCPs are often not easy to be solved directly by the algorithms tailored for EiCPs. In this paper, we introduce a nonmonotone spectral projected gradient (NSPG) method equipped with a positive Barzilai-Borwein step size to find a solution of TEiCPs. A series of numerical experiments show that the proposed NSPG method can greatly improve the efficiency of solving TEiCPs in terms of taking much less computing time for higher dimensional cases. Moreover, computational results show that our NSPG method is less sensitive to choices of starting points than some state-of-the-art algorithms.

Keywords:

Tensor eigenvalue complementatrity problem,
Projected gradient method,
Barzilai-Borwein step size,
Polynomial optimization.

Mathematics Subject Classification: Primary: 15A68, 90C30; Secondary: 90C33.

Citation:

Full Text(HTML)

Figure 1. Mean and standard deviation of iterations and computing time of ten trials with random starting points for the case of computing Pareto $ H $-eigenpairs. From top to bottom corresponding to Example 4, 5, and 6, respectively

Download: Full-size image PowerPoint slide

Figure 2. Mean and standard deviation of iterations and computing time of ten trials with random starting points for the case of computing Pareto $ B $-eigenpairs. The first and second rows correspond to Example 7 and 8, respectively

Download: Full-size image PowerPoint slide

Figure 3. Mean and standard deviation of iterations and computing time of ten trials with random starting points for the case of computing Pareto $ Z $- and $ H $-eigenpairs, respectively. The first and second rows correspond to Example 9 and 10, respectively

Download: Full-size image PowerPoint slide

Algorithm 1: The nonmonotone SPG method for TEiCPs

1: Let $ \varepsilon>0 $ be a tolerance of termination, $ \sigma,\rho\in(0,1) $, $ M\ge1 $ be an integer, $ 0<\beta_{\rm min}<\beta_{\rm max} $, and $ x_0\ge0 $ be an initial point. Set $ \beta_0=1/||\varphi(x_0)|| $ and $ k=0 $.
2: Compute $ z_k=P_{{\Delta}^n}(x_k+\beta_k \varphi(x_k)) $, and the direction $ d_{\beta_k}(x_k)=z_k-x_k $.
3: If $ ||d_{\beta_k}(x_k)||\leq\varepsilon $ then stop, the output $ \lambda=\frac{{{\mathcal A}} x_k^m}{{{\mathcal B}} x_k^m} $ is a Pareto-eigenvalue and $ x_k $ is the corresponding Preto-eigenvector of TEiCP.
4: Set $ \alpha_k=\rho^i $, where $ i\ge 0 $ is the smallest integer, such that
$\begin{equation} \Phi(x_k+\alpha_k d_{\beta_k}(x_k))\ge \min_{0\le j\le {\min\{k, M-1\}}}\Phi(x_{k-j})+ \sigma\alpha_k \varphi(x_k)^\top d_{\beta_k}(x_k), \;\;\;\;(7)\end{equation}$
and let $ x_{k+1}=x_k+\alpha_k d_{\beta_k}(x_k) $.
5: Let $ s_k=x_{k+1}-x_k $ and $ y_k=\varphi(x_{k+1})-\varphi(x_{k}) $. Update
$\beta_{k+1} = \max \left\{\beta_{\min},\min\left\{\beta_{\max},\left|\frac{\langle s_k,s_k\rangle}{\langle s_k,y_k\rangle}\right|\right\}\right\}.$
Go to Step 2.

| Show Table

DownLoad: CSV

Table 1. Computational results for Examples 1-10

Exam	(m, n)	NSPG(M=1)	NSPG(M=5)	NSPG(M=15)	SPG1	SPP
Exam	(m, n)	its / iits / time / err	its / iits / time / err	its / iits / time / err	its / iits / time / err	its / time / err
1	(4, 3)	9 / 3 / 0.06 / 2.4$ \times 10^{-7} $	9 / 3 / 0.05 / 2.4$ \times 10^{-7} $	9 / 3 / 0.05 / 2.4$ \times 10^{-7} $	31 / 78 / 0.28 / 5.6$ \times 10^{-7} $	19 / 0.08 / 9.0$ \times 10^{-7} $
2	(4, 5)	2 / 0 / 0.02 / 0	2 / 0 / 0.00 / 0	2 / 0 / 0.02 / 0	2 / 2 / 0.02 / 0	7 / 0.03 / 2.3$ \times 10^{-11} $
3	(4, 3)	8 / 1 / 0.03 / 1.0$ \times 10^{-6} $	8 / 0 / 0.03 / 1.1$ \times 10^{-8} $	8 / 0 / 0.03 / 1.1$ \times 10^{-8} $	11 / 26 / 0.09 / 2.9$ \times 10^{-7} $	5 / 0.02 / 3.9$ \times 10^{-7} $
	(4, 50)	35 / 22 / 1.08 / 7.0$ \times 10^{-7} $	35 / 2 / 0.69 / 5.7$ \times 10^{-7} $	32 / 1 / 0.63 / 5.8$ \times 10^{-7} $	83 / 172 / 3.19 / 9.8$ \times 10^{-7} $	147 / 2.78 / 9.9$ \times 10^{-7} $
4	(4, 75)	31 / 16 / 3.84 / 7.1$ \times 10^{-7} $	31 / 4 / 2.77 / 3.9$ \times 10^{-7} $	32 / 3 / 2.75 / 1.2$ \times 10^{-7} $	101 / 209 / 16.08 / 4.5$ \times 10^{-10} $	136 / 10.66 / 9.9$ \times 10^{-7} $
	(4,100)	34 / 30 / 15.75 / 5.9$ \times 10^{-7} $	32 / 17 / 11.78 / 5.9$ \times 10^{-7} $	32 / 17 / 12.14 / 5.9$ \times 10^{-7} $	87 / 180 / 42.50 / 9.5$ \times 10^{-7} $	134 / 548.48 / 9.4$ \times 10^{-7} $
	(4, 50)	19 / 6 / 0.50 / 8.0$ \times 10^{-7} $	21 / 0 / 0.41 / 3.4$ \times 10^{-7} $	21 / 0 / 0.41 / 3.4$ \times 10^{-7} $	21 / 31 / 0.59 / 4.2$ \times 10^{-7} $	250 / 4.64 / 9.9$ \times 10^{-7} $
5	(4, 75)	22 / 5 / 2.31 / 3.3$ \times 10^{-7} $	19 / 0 / 1.53 / 3.2$ \times 10^{-7} $	19 / 0 / 1.53 / 3.2$ \times 10^{-7} $	35 / 66 / 5.41 / 3.4$ \times 10^{-8} $	236 / 18.81 / 9.9$ \times 10^{-7} $
	(4,100)	21 / 8 / 7.58 / 2.2$ \times 10^{-7} $	24 / 1 / 6.47 / 6.9$ \times 10^{-7} $	25 / 0 / 6.11 / 7.1$ \times 10^{-7} $	29 / 56 / 13.47 / 5.1$ \times 10^{-7} $	323 / 1348.98 / 9.7$ \times 10^{-7} $
	(4, 50)	38 / 16 / 1.03 / 2.9$ \times 10^{-7} $	41 / 2 / 0.80 / 1.7$ \times 10^{-7} $	41 / 1 / 0.78 / 8.0$ \times 10^{-7} $	79 / 169 / 3.14 / 8.2$ \times 10^{-7} $	114 / 2.14 / 9.9$ \times 10^{-7} $
6	(4, 75)	58 / 43 / 7.94 / 6.2$ \times 10^{-7} $	48 / 16 / 5.20 / 6.7$ \times 10^{-7} $	50 / 1 / 4.31 / 8.9$ \times 10^{-7} $	186 / 385 / 29.63 / 9.7$ \times 10^{-7} $	369 / 28.98 / 1.0$ \times 10^{-6} $
	(4,100)	32 / 14 / 11.56 / 8.8$ \times 10^{-7} $	37 / 2 / 10.16 / 3.9$ \times 10^{-7} $	37 / 2 / 10.42 / 3.9$ \times 10^{-7} $	70 / 157 / 37.42 / 9.6$ \times 10^{-7} $	195 / 842.20 / 9.5$ \times 10^{-7} $
	(4, 50)	291 / 390 / 12.41 / 9.3$ \times 10^{-7} $	204 / 147 / 6.42 / 8.2$ \times 10^{-7} $	163 / 59 / 4.31 / 5.2$ \times 10^{-7} $	- / - / - / 1.7$ \times 10^{-5} $	- / - / 2.4$ \times 10^{-5} $
7	(4, 75)	156 / 176 / 27.72 / 9.0$ \times 10^{-7} $	178 / 113 / 24.14 / 5.3$ \times 10^{-7} $	155 / 30 / 15.41 / 3.5$ \times 10^{-7} $	567 / 1160 / 90.89 / 9.9$ \times 10^{-7} $	- / - / 4.0$ \times 10^{-5} $
	(4,100)	117 / 131 / 59.53 / 5.8$ \times 10^{-7} $	125 / 106 / 54.86 / 7.3$ \times 10^{-7} $	114 / 34 / 37.16 / 6.7$ \times 10^{-7} $	325 / 680 / 162.83 / 1.0$ \times 10^{-6} $	- / - / 4.3$ \times 10^{-5} $
	(4, 50)	21 / 20 / 0.75 / 1.7$ \times 10^{-8} $	21 / 20 / 0.75 / 1.7$ \times 10^{-8} $	21 / 20 / 0.77 / 1.7$ \times 10^{-8} $	645 / 650 / 11.78 / 1.0$ \times 10^{-6} $	- / - / 1.2$ \times 10^{-4} $
8	(4, 75)	22 / 23 / 3.50 / 7.8$ \times 10^{-8} $	34 / 23 / 4.41 / 2.0$ \times 10^{-8} $	38 / 22 / 4.63 / 1.2$ \times 10^{-10} $	738 / 741 / 59.89 / 9.9$ \times 10^{-7} $	- / - / 4.8$ \times 10^{-4} $
	(4,100)	26 / 27 / 14.19 / 3.4$ \times 10^{-9} $	26 / 23 / 13.02 / 3.4$ \times 10^{-9} $	26 / 23 / 12.50 / 3.4$ \times 10^{-9} $	916 / 942 / 236.67 / 1.0$ \times 10^{-6} $	- / - / 3.5$ \times 10^{-4} $
9	(4, 50)	43 / 25 / 1.28 / 1.4$ \times 10^{-7} $	38 / 3 / 0.77 / 2.9$ \times 10^{-7} $	35 / 2 / 0.72 / 3.7$ \times 10^{-7} $	390 / 787 / 14.39 / 9.3$ \times 10^{-7} $	194 / 3.61 / 9.7$ \times 10^{-7} $
Z-eig	(4, 75)	71 / 55 / 9.80 / 8.3$ \times 10^{-7} $	63 / 18 / 6.23 / 6.2$ \times 10^{-7} $	74 / 1 / 5.78 / 7.3$ \times 10^{-7} $	328 / 697 / 52.91 / 2.9$ \times 10^{-7} $	496 / 36.58 / 1.0$ \times 10^{-6} $
	(4,100)	238 / 297 / 131.00 / 9.4$ \times 10^{-7} $	120 / 61 / 42.97 / 5.1$ \times 10^{-7} $	138 / 27 / 39.31 / 8.3$ \times 10^{-7} $	231 / 470 / 112.47 / 6.1$ \times 10^{-7} $	295 / 1235.41 / 9.8$ \times 10^{-7} $
10	(3, 50)	55 / 31 / 0.33 / 9.7$ \times 10^{-7} $	50 / 7 / 0.22 / 1.0$ \times 10^{-6} $	58 / 0 / 0.22 / 1.2$ \times 10^{-7} $	133 / 284 / 1.08 / 3.8$ \times 10^{-7} $	121 / 0.48 / 9.7$ \times 10^{-7} $
H-eig	(3, 75)	61 / 34 / 0.38 / 4.0$ \times 10^{-7} $	45 / 6 / 0.20 / 4.8$ \times 10^{-8} $	45 / 2 / 0.20 / 1.0$ \times 10^{-7} $	288 / 593 / 2.39 / 1.9$ \times 10^{-8} $	158 / 0.72 / 9.9$ \times 10^{-7} $
	(3,100)	51 / 34 / 0.41 / 5.4$ \times 10^{-7} $	52 / 19 / 0.33 / 3.9$ \times 10^{-7} $	56 / 8 / 0.31 / 5.3$ \times 10^{-7} $	320 / 726 / 3.38 / 2.7$ \times 10^{-8} $	407 / 45.97 / 9.5$ \times 10^{-7} $
10	(4, 50)	106 / 84 / 3.47 / 1.4$ \times 10^{-7} $	64 / 16 / 1.45 / 6.2$ \times 10^{-7} $	53 / 4 / 1.08 / 9.9$ \times 10^{-7} $	330 / 768 / 14.19 / 1.7$ \times 10^{-7} $	173 / 3.45 / 9.5$ \times 10^{-7} $
H-eig	(4, 75)	82 / 57 / 10.81 / 1.1$ \times 10^{-7} $	64 / 10 / 5.70 / 6.8$ \times 10^{-7} $	68 / 1 / 5.31 / 5.8$ \times 10^{-7} $	576 / 1325 / 102.00 / 3.5$ \times 10^{-7} $	581 / 45.23 / 9.9$ \times 10^{-7} $
	(4,100)	70 / 40 / 27.61 / 8.7$ \times 10^{-7} $	114 / 57 / 40.80 / 5.1$ \times 10^{-7} $	97 / 4 / 25.73 / 3.5$ \times 10^{-7} $	218 / 518 / 124.77 / 7.1$ \times 10^{-7} $	372 / 1573.88 / 9.9$ \times 10^{-7} $
10	(5, 40)	32 / 17 / 15.00 / 5.9$ \times 10^{-7} $	36 / 4 / 12.47 / 6.1$ \times 10^{-7} $	35 / 2 / 11.08 / 5.8$ \times 10^{-7} $	615 / 1394 / 411.41 / 7.4$ \times 10^{-7} $	562 / 166.73 / 9.7$ \times 10^{-7} $
H-eig	(5, 50)	137 / 164 / 251.84 / 6.7$ \times 10^{-7} $	97 / 61 / 136.81 / 3.8$ \times 10^{-7} $	58 / 7 / 57.98 / 8.8$ \times 10^{-7} $	320 / 889 / 750.80 / 9.7$ \times 10^{-7} $	572 / 501.31 / 9.7$ \times 10^{-7} $
	(5, 60)	67 / 52 / 248.39 / 3.3$ \times 10^{-7} $	92 / 40 / 279.64 / 6.8$ \times 10^{-7} $	93 / 24 / 242.63 / 5.1$ \times 10^{-7} $	265 / 669 / 1365.61 / 7.6$ \times 10^{-7} $	347 / 724.52 / 9.9$ \times 10^{-7} $
The symbol '-' here means that the number of iterations exceeds 1000.

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	B. W. Bader, T. G. Kolda et al., MATLAB Tensor Toolbox Version 2.6, Available online, 2015, URL http://www.sandia.gov/ tgkolda/TensorToolbox/.
[2]	J. Barzilai and J. M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal., 8 (1988), 141-148. doi: 10.1093/imanum/8.1.141.
[3]	A. Beck, Introduction to Nonlinear Optimization Theory, Algorithms, and Applications with MATLAB, SIAM, Philadelphia, 2014. doi: 10.1137/1.9781611973655.
[4]	E. Birgin, J. Martinez and M. Raydan, Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim., 10 (2000), 1196-1211. doi: 10.1137/S1052623497330963.
[5]	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.
[6]	Y. Chen and X. Ye, Projection onto a simplex, arXiv: 1101.6081.
[7]	Z. Chen, Q. Yang and L. Ye, Generalized eigenvalue complementarity problem for tensors, Pac. J. Optim., 13 (2017), 527-545.
[8]	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.
[9]	J. Fan, J. Nie and A. Zhou, Tensor eigenvalue complementarity problems, Math. Program. Ser. A, 170 (2018), 507-539. doi: 10.1007/s10107-017-1167-y.
[10]	L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique for Newton's method, SIAM J. Numer. Anal., 23 (1986), 707-716. doi: 10.1137/0723046.
[11]	H. He, C. Ling, L. Qi and G. Zhou, A globally and quadratically convergent algorithm for solving multilinear systems with $\mathcal M$-tensors, J. Sci. Comput., 76 (2018), 1718-1741. doi: 10.1007/s10915-018-0689-7.
[12]	E. Kofidis and P. Regalia, On the best rank-1 approximation of higher-order supersymmetric tensors, SIAM J. Matrix Anal. Appl., 23 (2002), 863-884. doi: 10.1137/S0895479801387413.
[13]	L. Lim, Singular values and eigenvalues of tensors: A variational approach, in IEEE CAMSAP 2005: First International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CINVESTAV; IEEE Signal Proc Soc, 2005,129–132, (1st IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, Puerto Vallarta, MEXICO, DEC 13-15, 2005).
[14]	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.
[15]	J. Nie and L. Wang, Semidefinite relaxations for best rank-1 tensor approximations, SIAM J. Matrix Anal. Appl., 35 (2014), 1155-1179. doi: 10.1137/130935112.
[16]	L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput., 40 (2005), 1302-1324. doi: 10.1016/j.jsc.2005.05.007.
[17]	L. Qi, Symmetric nonnegative tensors and copositive tensors, Linear Algebra Appl., 439 (2013), 228-238. doi: 10.1016/j.laa.2013.03.015.
[18]	L. Qi, H. Chen and Y. Chen, Tensor Eigenvalues and Their Applications, Springer, Singapore, 2018. doi: 10.1007/978-981-10-8058-6.
[19]	G. Yu, Y. Song, Y. Xu and Z. Yu, Spectral projected gradient methods for generalized tensor eigenvalue complementarity problem, Numer. Algor., 80 (2019), 1181-1201. doi: 10.1007/s11075-018-0522-2.
[20]	H. Zhang and W. Hager, A nonmonotone line search technique and its application to unconstrained optimization, SIAM J. Optim., 14 (2004), 1043-1056. doi: 10.1137/S1052623403428208.