\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

A nonmonotone spectral projected gradient method for tensor eigenvalue complementarity problems

  • * Corresponding author: Chen Ling

    * Corresponding author: Chen Ling 

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
  • 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.

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

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • 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.
     | 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
    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
  • [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.
  • 加载中

Figures(3)

Tables(2)

SHARE

Article Metrics

HTML views(493) PDF downloads(332) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return