December  2020, 10(4): 425-437. doi: 10.3934/naco.2020042

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

Received  March 2020 Revised  September 2020 Published  September 2020

Fund Project: 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)

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.

Citation: Wanbin Tong, Hongjin He, Chen Ling, Liqun Qi. A nonmonotone spectral projected gradient method for tensor eigenvalue complementarity problems. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 425-437. doi: 10.3934/naco.2020042
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. BirginJ. 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. ChangK. 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. ChenQ. 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. FanJ. 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. GrippoF. 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. HeC. LingL. 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. LingH. 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. YuY. SongY. 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.

show all references

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. BirginJ. 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. ChangK. 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. ChenQ. 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. FanJ. 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. GrippoF. 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. HeC. LingL. 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. LingH. 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. YuY. SongY. 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.

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
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
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
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.
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.
Table 1.  Computational results for Examples 1-10
Exam (m, n) NSPG(M=1) NSPG(M=5) NSPG(M=15) SPG1 SPP
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.
Exam (m, n) NSPG(M=1) NSPG(M=5) NSPG(M=15) SPG1 SPP
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.
[1]

Huan Gao, Yu-Hong Dai, Xiao-Jiao Tong. Barzilai-Borwein-like methods for the extreme eigenvalue problem. Journal of Industrial and Management Optimization, 2015, 11 (3) : 999-1019. doi: 10.3934/jimo.2015.11.999

[2]

Xing Li, Chungen Shen, Lei-Hong Zhang. A projected preconditioned conjugate gradient method for the linear response eigenvalue problem. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 389-412. doi: 10.3934/naco.2018025

[3]

Rouhollah Tavakoli, Hongchao Zhang. A nonmonotone spectral projected gradient method for large-scale topology optimization problems. Numerical Algebra, Control and Optimization, 2012, 2 (2) : 395-412. doi: 10.3934/naco.2012.2.395

[4]

Nora Merabet. Global convergence of a memory gradient method with closed-form step size formula. Conference Publications, 2007, 2007 (Special) : 721-730. doi: 10.3934/proc.2007.2007.721

[5]

Ya Li, ShouQiang Du, YuanYuan Chen. Modified spectral PRP conjugate gradient method for solving tensor eigenvalue complementarity problems. Journal of Industrial and Management Optimization, 2022, 18 (1) : 157-172. doi: 10.3934/jimo.2020147

[6]

Yu-Ning Yang, Su Zhang. On linear convergence of projected gradient method for a class of affine rank minimization problems. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1507-1519. doi: 10.3934/jimo.2016.12.1507

[7]

Miriam Kiessling, Sascha Kurz, Jörg Rambau. The integrated size and price optimization problem. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 669-693. doi: 10.3934/naco.2012.2.669

[8]

Yanfei Wang, Dmitry Lukyanenko, Anatoly Yagola. Magnetic parameters inversion method with full tensor gradient data. Inverse Problems and Imaging, 2019, 13 (4) : 745-754. doi: 10.3934/ipi.2019034

[9]

ShiChun Lv, Shou-Qiang Du. A new smoothing spectral conjugate gradient method for solving tensor complementarity problems. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021150

[10]

Yanfei Wang, Qinghua Ma. A gradient method for regularizing retrieval of aerosol particle size distribution function. Journal of Industrial and Management Optimization, 2009, 5 (1) : 115-126. doi: 10.3934/jimo.2009.5.115

[11]

Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control and Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011

[12]

Yanmei Sun, Yakui Huang. An alternate gradient method for optimization problems with orthogonality constraints. Numerical Algebra, Control and Optimization, 2021, 11 (4) : 665-676. doi: 10.3934/naco.2021003

[13]

Feng Ma, Jiansheng Shu, Yaxiong Li, Jian Wu. The dual step size of the alternating direction method can be larger than 1.618 when one function is strongly convex. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1173-1185. doi: 10.3934/jimo.2020016

[14]

David Yang Gao, Changzhi Wu. On the triality theory for a quartic polynomial optimization problem. Journal of Industrial and Management Optimization, 2012, 8 (1) : 229-242. doi: 10.3934/jimo.2012.8.229

[15]

Xiu Ye, Shangyou Zhang. A new weak gradient for the stabilizer free weak Galerkin method with polynomial reduction. Discrete and Continuous Dynamical Systems - B, 2021, 26 (8) : 4131-4145. doi: 10.3934/dcdsb.2020277

[16]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control and Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[17]

Huan Gao, Zhibao Li, Haibin Zhang. A fast continuous method for the extreme eigenvalue problem. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1587-1599. doi: 10.3934/jimo.2017008

[18]

Ruixue Zhao, Jinyan Fan. Quadratic tensor eigenvalue complementarity problems. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022073

[19]

Li-Fang Dai, Mao-Lin Liang, Wei-Yuan Ma. Optimization problems on the rank of the solution to left and right inverse eigenvalue problem. Journal of Industrial and Management Optimization, 2015, 11 (1) : 171-183. doi: 10.3934/jimo.2015.11.171

[20]

Julián Fernández Bonder, Leandro M. Del Pezzo. An optimization problem for the first eigenvalue of the $p-$Laplacian plus a potential. Communications on Pure and Applied Analysis, 2006, 5 (4) : 675-690. doi: 10.3934/cpaa.2006.5.675

 Impact Factor: 

Metrics

  • PDF downloads (308)
  • HTML views (239)
  • Cited by (0)

Other articles
by authors

[Back to Top]