Article Contents
Article Contents

# A trust region algorithm for computing extreme eigenvalues of tensors

• * Corresponding author: Jingya Chang

The first author is supported by the National Natural Science Foundation of China grant 11771405 and Guangdong Basic and Applied Basic Research Foundation 2020A1515010489. The second author is supported by the National Natural Science Foundation of China grant 11901118 and Guangdong Basic and Applied Basic Research Foundation 2020B1515310001

• Eigenvalues and eigenvectors of high order tensors have crucial applications in sciences and engineering. For computing H-eigenvalues and Z-eigenvalues of even order tensors, we transform the tensor eigenvalue problem to a nonlinear optimization with a spherical constraint. Then, a trust region algorithm for the spherically constrained optimization is proposed in this paper. At each iteration, an unconstrained quadratic model function is solved inexactly to produce a trial step. The Cayley transform maps the trial step onto the unit sphere. If the trial step generates a satisfactory actual decrease of the objective function, we accept the trial step as a new iterate. Otherwise, a second order line search process is performed to exploit valuable information contained in the trial step. Global convergence of the proposed trust region algorithm is analyzed. Preliminary numerical experiments illustrate that the novel trust region algorithm is efficient and promising.

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

 Citation:

•  Algorithm 1: A trust region algorithm for computing an eigenvalue of a tensor. 1: Set $\mathcal{B}= \mathcal{I}$ and $\mathcal{B}= \mathcal{E}$ if an H-eigenvalue and a Z-eigenvalue are in purpose, respectively. 2: Set parameters $0<\eta_1<\eta_2<1/2$, $0<\gamma_1<\gamma_2<1<\gamma_3$, and $0<\Delta_0\le\bar{\Delta}$. Choose an initial point $\mathbf{x}_0\in\mathbb{S}^{{n-1}}$ and set $k\gets0$.3: while$\nabla f( \mathbf{x}_k)\ne0$ 4: Calculate $\mathcal{A} \mathbf{x}^m, \mathcal{B} \mathbf{x}^m, \mathcal{A} \mathbf{x}^{m-1}, \mathcal{B} \mathbf{x}^{m-1}, \mathcal{A} \mathbf{x}^{m-2}$, and $\mathcal{B} \mathbf{x}^{m-2}$. 5: Solve the trust region subproblem: \begin{equation*} \begin{aligned} \min\; & \frac{1}{2} \mathbf{d}^T H_k \mathbf{d} + \mathbf{g}_k^T \mathbf{d} + f_k \mathrm{s.t.}\; \; \| \mathbf{d}\|\le\Delta_k, \end{aligned} \end{equation*} $\mathrm{s.t.}\; \; \| \mathbf{d}\|\le\Delta_k,$ inexactly for a trial step $\mathbf{d}_k$ satisfying (7) and (8). 6: Backtracking search on $\mathbb{S}^{{n-1}}$. Find a smallest nonnegative integer $j$ such that the step size $\alpha=\gamma_2^j$ satisfies: $\begin{equation*} \rho_k = \frac{f_k-f( \mathbf{x}_k^+(\alpha))}{q_k(0)-q_k(\alpha \mathbf{d}_k)} \ge \eta_1, \end{equation*}$ where $\mathbf{x}_k^+(\alpha)$ is defined by (9). 7: Update an iterate. Set $\alpha_k=\gamma_2^j$ and $\mathbf{x}_{k+1}= \mathbf{x}_k^+(\alpha_k)$. 8: Update a trust region radius. If $\alpha_k=1$, we choose \begin{equation*} \Delta_{k+1}\in\left\{\begin{aligned} & [\gamma_2\Delta_k, \Delta_k] && \text{ if }\rho_k\in[\eta_1,\eta_2), & [\Delta_k, \min\{\gamma_3\Delta_k,\bar{\Delta}\}] && \text{ if }\rho_k\ge\eta_2, \end{aligned}\right. \end{equation*} else $\begin{equation*} \Delta_{k+1}\in[\max\{\gamma_1\Delta_k,\alpha_k\| \mathbf{d}_k\|\},\gamma_2\Delta_k]. \end{equation*}$ 9: Set $k\gets k+1$. 10: end while

Table 1.  Numerical results on Example 1

 Solvers PM BBGA QNA TRA $\lambda^Z_{\max}$ 0.8893 0.8893 0.8893 0.8893 #Iter'n 3699 1697 1142 450 CPU time 12.55 0.56 0.46 0.37 $\lambda^Z_{\min}$ $-1.0953$ $-1.0953$ $-1.0953$ $-1.0953$ #Iter'n 1725 1121 808 333 CPU time 5.65 0.23 0.30 0.24

Table 2.  Numerical results on Example 2

 Solvers PM BBGA QNA TRA $\lambda^H_{\min}$ of $\mathcal{A}(1)$ 1.2268 1.2268 1.2268 1.2268 #Iter'n 16713 1423 1159 482 CPU time 38.12 0.31 0.43 0.29 $\lambda^H_{\max}$ of $\mathcal{A}(1)$ 5.1812 5.1812 5.1812 5.1812 #Iter'n 23632 1336 1159 753 CPU time 53.06 0.30 0.43 0.37 $\lambda^H_{\min}$ of $\mathcal{A}(3)$ $-1.3952$ $-1.3952$ $-1.3952$ $-1.3952$ #Iter'n 21214 1127 986 429 CPU time 48.92 0.29 0.40 0.28 $\lambda^H_{\max}$ of $\mathcal{A}(3)$ 7.4505 7.4505 7.4505 7.4505 #Iter'n 21711 1263 1152 711 CPU time 50.09 0.30 0.45 0.36

Table 3.  Numerical results on Hilbert tensors

 Order Dimension $\lambda^Z_{\max}$ BBGA QNA TRA 4 10 $6.5289$ 0.04 0.06 0.11 100 $6.0499\times10^1$ 0.09 0.09 0.11 1,000 $6.0050\times10^2$ 0.32 0.31 0.29 10,000 $6.0006\times10^3$ 3.99 3.50 2.63 100,000 $6.0001\times10^4$ 31.23 30.23 23.72 1,000,000 $6.0001\times10^5$ 425.05 452.17 371.71 6 10 $4.0427\times10^1$ 0.14 0.29 0.09 100 $3.7308\times10^3$ 0.14 0.13 0.13 1,000 $3.7023\times10^5$ 0.73 0.58 0.55 10,000 $3.6994\times10^7$ 7.36 6.84 7.12 100,000 $3.6991\times10^9$ 113.75 112.62 75.49 1,000,000 $3.6991\times10^{11}$ 3091.54 3186.61 1439.50
•  [1] J. Chang, Y. Chen and L. Qi, Computing eigenvalues of large scale sparse tensors arising from a hypergraph, SIAM Journal on Scientific Computing, 38 (2016), A3618–A3643. doi: 10.1137/16M1060224. [2] L. Chen, L. Han and L. Zhou, Computing tensor eigenvalues via homotopy methods, SIAM Journal on Matrix Analysis and Applications, 37 (2016), 290-319.  doi: 10.1137/15M1010725. [3] Y. Chen, Y. Dai, D. Han and W. Sun, Positive semidefinite generalized diffusion tensor imaging via quadratic semidefinite programming, SIAM Journal on Imaging Sciences, 6 (2013), 1531-1552.  doi: 10.1137/110843526. [4] Y. Chen, L. Qi and E. G. Virga, Octupolar tensors for liquid crystals, Journal of Physics A: Mathematical and Theoretical, 51 (2018), 025206. doi: 10.1088/1751-8121/aa98a8. [5] Y. Chen, Li qun Qi and Qu n Wang, Computing extreme eigenvalues of large scale Hankel tensors, Journal of Scientific Computing, 68 (2016), 716-738.  doi: 10.1007/s10915-015-0155-8. [6] Y. Chen, L. Qi and X. Zhang, The Fiedler vector of a Laplacian tensor for hypergraph partitioning, SIAM Journal on Scientific Computing, 39 (2017), A2508–A2537. doi: 10.1137/16M1094828. [7] J. Cooper and A. Dutle, Spectra of uniform hypergraphs, Linear Algebra and Its Applications, 436 (2012), 3268-3292.  doi: 10.1016/j.laa.2011.11.018. [8] C. Cui, Y. Dai and J. Nie, All real eigenvalues of symmetric tensors, SIAM Journal on Matrix Analysis and Applications, 35 (2014), 1582-1601.  doi: 10.1137/140962292. [9] G. Gaeta and E. G. Virga, Octupolar order in three dimensions, The European Physical Journal E, 39 (2016), 113. [10] G. H. Golub and  C. F. Van Loan,  Matrix Computations, 4$^th$ edition, The Johns Hopkins University Press, Baltimore, Maryland, 2013. [11] L. Han, An unconstrained optimization approach for finding real eigenvalues of even order symmetric tensors, Numerical Algebra, Control and Optimization, 3 (2013), 583-599.  doi: 10.3934/naco.2013.3.583. [12] T. G. Kolda and J. R. Mayo, Shifted power method for computing tensor eigenpairs, SIAM Journal on Matrix Analysis and Applications, 32 (2011), 1095-1124.  doi: 10.1137/100801482. [13] T. G. Kolda and J. R. Mayo, An adaptive shifted power method for computing generalized tensor eigenpairs, SIAM Journal on Matrix Analysis and Applications, 35 (2014), 1563-1581.  doi: 10.1137/140951758. [14] W. Li and M. K. Ng, On the limiting probability distribution of a transition probability tensor, Linear and Multilinear Algebra, 62 (2014), 362-385.  doi: 10.1080/03081087.2013.777436. [15] L. Lim, Singular values and eigenvalues of tensors: a variational approach, in 1st IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, Piscataway, NJ, (2005), 129–132. [16] L. Qi, Eigenvalues of a real supersymmetric tensor, Journal of Symbolic Computation, 40 (2005), 1302-1324.  doi: 10.1016/j.jsc.2005.05.007. [17] L. Qi, W. Sun and Y. Wang, Numerical multilinear algebra and its applications, Frontiers of Mathematics in China, 2 (2007), 501-526.  doi: 10.1007/s11464-007-0031-4. [18] L. Qi and Z. Luo, Tensor Analysis: Spectral Theory and Special Tensors, SIAM, Philadelphia, 2017. doi: 10.1137/1.9781611974751.ch1. [19] Y. Song and L. Qi, Infinite and finite dimensional Hilbert tensors, Linear Algebra and its Applications, 451 (2014), 1-14.  doi: 10.1016/j.laa.2014.03.023. [20] W. Sun, Nonmonotone trust region method for solving optimization problems, Applied Mathematics and Computation, 156 (2004), 159-174.  doi: 10.1016/j.amc.2003.07.008. [21] W. Sun and Y.-X. Yuan, Optimization Theory and Methods: Nonlinear Programming, Springer, New York, 2006. [22] W. Sun, L. Hou and C. Dang, A modified trust region method with Beale's PCG technique for optimization, Computational Optimization and Applications, 40 (2008), 59-72.  doi: 10.1007/s10589-007-9078-0.

Tables(4)