A trust region algorithm for computing extreme eigenvalues of tensors

Yannan Chen; Jingya Chang

doi:10.3934/naco.2020046

Article Contents

2020, Volume 10, Issue 4: 475-485. Doi: 10.3934/naco.2020046

This issue Previous Article Convergence of a randomized Douglas-Rachford method for linear system Next Article Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization

A trust region algorithm for computing extreme eigenvalues of tensors

Yannan Chen^1, and
Jingya Chang^2, ,

1.
School of Mathematical Sciences, South China Normal University, Guangzhou 510631, China
2.
School of Applied Mathematics, Guangdong University of Technology, Guangzhou 510520, China

^* Corresponding author: Jingya Chang
^* Corresponding author: Jingya Chang

Received: April 2020

Revised: September 2020

Published: September 2020

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

Abstract Full Text(HTML) Figure(0) / Table(4) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

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