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 & 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/. Google Scholar

[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.  Google Scholar

[3]

A. Beck, Introduction to Nonlinear Optimization Theory, Algorithms, and Applications with MATLAB, SIAM, Philadelphia, 2014. doi: 10.1137/1.9781611973655.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

Y. Chen and X. Ye, Projection onto a simplex, arXiv: 1101.6081. Google Scholar

[7]

Z. ChenQ. Yang and L. Ye, Generalized eigenvalue complementarity problem for tensors, Pac. J. Optim., 13 (2017), 527-545.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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). Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[16]

L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput., 40 (2005), 1302-1324.  doi: 10.1016/j.jsc.2005.05.007.  Google Scholar

[17]

L. Qi, Symmetric nonnegative tensors and copositive tensors, Linear Algebra Appl., 439 (2013), 228-238.  doi: 10.1016/j.laa.2013.03.015.  Google Scholar

[18]

L. Qi, H. Chen and Y. Chen, Tensor Eigenvalues and Their Applications, Springer, Singapore, 2018. doi: 10.1007/978-981-10-8058-6.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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/. Google Scholar

[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.  Google Scholar

[3]

A. Beck, Introduction to Nonlinear Optimization Theory, Algorithms, and Applications with MATLAB, SIAM, Philadelphia, 2014. doi: 10.1137/1.9781611973655.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

Y. Chen and X. Ye, Projection onto a simplex, arXiv: 1101.6081. Google Scholar

[7]

Z. ChenQ. Yang and L. Ye, Generalized eigenvalue complementarity problem for tensors, Pac. J. Optim., 13 (2017), 527-545.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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). Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[16]

L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput., 40 (2005), 1302-1324.  doi: 10.1016/j.jsc.2005.05.007.  Google Scholar

[17]

L. Qi, Symmetric nonnegative tensors and copositive tensors, Linear Algebra Appl., 439 (2013), 228-238.  doi: 10.1016/j.laa.2013.03.015.  Google Scholar

[18]

L. Qi, H. Chen and Y. Chen, Tensor Eigenvalues and Their Applications, Springer, Singapore, 2018. doi: 10.1007/978-981-10-8058-6.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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 & 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 & 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 & 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 & Management Optimization, 2020  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 & 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 & 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 & Imaging, 2019, 13 (4) : 745-754. doi: 10.3934/ipi.2019034

[9]

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

[10]

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

[11]

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 & Management Optimization, 2020  doi: 10.3934/jimo.2020016

[12]

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

[13]

Xiu Ye, Shangyou Zhang. A new weak gradient for the stabilizer free weak Galerkin method with polynomial reduction. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020277

[14]

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 & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[15]

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

[16]

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 & Applied Analysis, 2006, 5 (4) : 675-690. doi: 10.3934/cpaa.2006.5.675

[17]

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 & Management Optimization, 2015, 11 (1) : 171-183. doi: 10.3934/jimo.2015.11.171

[18]

Guanghui Zhou, Qin Ni, Meilan Zeng. A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 595-608. doi: 10.3934/jimo.2016034

[19]

El-Sayed M.E. Mostafa. A nonlinear conjugate gradient method for a special class of matrix optimization problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 883-903. doi: 10.3934/jimo.2014.10.883

[20]

Jueyou Li, Guoquan Li, Zhiyou Wu, Changzhi Wu, Xiangyu Wang, Jae-Myung Lee, Kwang-Hyo Jung. Incremental gradient-free method for nonsmooth distributed optimization. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1841-1857. doi: 10.3934/jimo.2017021

 Impact Factor: 

Metrics

  • PDF downloads (42)
  • HTML views (42)
  • Cited by (0)

Other articles
by authors

[Back to Top]