-
Previous Article
Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization
- NACO Home
- This Issue
-
Next Article
Convergence of a randomized Douglas-Rachford method for linear system
A trust region algorithm for computing extreme eigenvalues of tensors
1. | School of Mathematical Sciences, South China Normal University, Guangzhou 510631, China |
2. | School of Applied Mathematics, Guangdong University of Technology, Guangzhou 510520, China |
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.
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. |
show all references
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. |
Algorithm 1: A trust region algorithm for computing an eigenvalue of a tensor. |
1: Set 2: Set parameters 3: while 4: Calculate 5: Solve the trust region subproblem: inexactly for a trial step 6: Backtracking search on where 7: Update an iterate. Set 8: Update a trust region radius. If else 9: Set 10: end while |
Algorithm 1: A trust region algorithm for computing an eigenvalue of a tensor. |
1: Set 2: Set parameters 3: while 4: Calculate 5: Solve the trust region subproblem: inexactly for a trial step 6: Backtracking search on where 7: Update an iterate. Set 8: Update a trust region radius. If else 9: Set 10: end while |
Solvers | PM | BBGA | QNA | TRA |
0.8893 | 0.8893 | 0.8893 | 0.8893 | |
#Iter'n | 3699 | 1697 | 1142 | 450 |
CPU time | 12.55 | 0.56 | 0.46 | 0.37 |
#Iter'n | 1725 | 1121 | 808 | 333 |
CPU time | 5.65 | 0.23 | 0.30 | 0.24 |
Solvers | PM | BBGA | QNA | TRA |
0.8893 | 0.8893 | 0.8893 | 0.8893 | |
#Iter'n | 3699 | 1697 | 1142 | 450 |
CPU time | 12.55 | 0.56 | 0.46 | 0.37 |
#Iter'n | 1725 | 1121 | 808 | 333 |
CPU time | 5.65 | 0.23 | 0.30 | 0.24 |
Solvers | PM | BBGA | QNA | TRA |
1.2268 | 1.2268 | 1.2268 | 1.2268 | |
#Iter'n | 16713 | 1423 | 1159 | 482 |
CPU time | 38.12 | 0.31 | 0.43 | 0.29 |
5.1812 | 5.1812 | 5.1812 | 5.1812 | |
#Iter'n | 23632 | 1336 | 1159 | 753 |
CPU time | 53.06 | 0.30 | 0.43 | 0.37 |
#Iter'n | 21214 | 1127 | 986 | 429 |
CPU time | 48.92 | 0.29 | 0.40 | 0.28 |
7.4505 | 7.4505 | 7.4505 | 7.4505 | |
#Iter'n | 21711 | 1263 | 1152 | 711 |
CPU time | 50.09 | 0.30 | 0.45 | 0.36 |
Solvers | PM | BBGA | QNA | TRA |
1.2268 | 1.2268 | 1.2268 | 1.2268 | |
#Iter'n | 16713 | 1423 | 1159 | 482 |
CPU time | 38.12 | 0.31 | 0.43 | 0.29 |
5.1812 | 5.1812 | 5.1812 | 5.1812 | |
#Iter'n | 23632 | 1336 | 1159 | 753 |
CPU time | 53.06 | 0.30 | 0.43 | 0.37 |
#Iter'n | 21214 | 1127 | 986 | 429 |
CPU time | 48.92 | 0.29 | 0.40 | 0.28 |
7.4505 | 7.4505 | 7.4505 | 7.4505 | |
#Iter'n | 21711 | 1263 | 1152 | 711 |
CPU time | 50.09 | 0.30 | 0.45 | 0.36 |
Order | Dimension | BBGA | QNA | TRA | |
4 | 10 | 0.04 | 0.06 | 0.11 | |
100 | 0.09 | 0.09 | 0.11 | ||
1,000 | 0.32 | 0.31 | 0.29 | ||
10,000 | 3.99 | 3.50 | 2.63 | ||
100,000 | 31.23 | 30.23 | 23.72 | ||
1,000,000 | 425.05 | 452.17 | 371.71 | ||
6 | 10 | 0.14 | 0.29 | 0.09 | |
100 | 0.14 | 0.13 | 0.13 | ||
1,000 | 0.73 | 0.58 | 0.55 | ||
10,000 | 7.36 | 6.84 | 7.12 | ||
100,000 | 113.75 | 112.62 | 75.49 | ||
1,000,000 | 3091.54 | 3186.61 | 1439.50 |
Order | Dimension | BBGA | QNA | TRA | |
4 | 10 | 0.04 | 0.06 | 0.11 | |
100 | 0.09 | 0.09 | 0.11 | ||
1,000 | 0.32 | 0.31 | 0.29 | ||
10,000 | 3.99 | 3.50 | 2.63 | ||
100,000 | 31.23 | 30.23 | 23.72 | ||
1,000,000 | 425.05 | 452.17 | 371.71 | ||
6 | 10 | 0.14 | 0.29 | 0.09 | |
100 | 0.14 | 0.13 | 0.13 | ||
1,000 | 0.73 | 0.58 | 0.55 | ||
10,000 | 7.36 | 6.84 | 7.12 | ||
100,000 | 113.75 | 112.62 | 75.49 | ||
1,000,000 | 3091.54 | 3186.61 | 1439.50 |
[1] |
Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171 |
[2] |
Jun Chen, Wenyu Sun, Zhenghao Yang. A non-monotone retrospective trust-region method for unconstrained optimization. Journal of Industrial and Management Optimization, 2013, 9 (4) : 919-944. doi: 10.3934/jimo.2013.9.919 |
[3] |
Lijuan Zhao, Wenyu Sun. Nonmonotone retrospective conic trust region method for unconstrained optimization. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 309-325. doi: 10.3934/naco.2013.3.309 |
[4] |
Bülent Karasözen. Survey of trust-region derivative free optimization methods. Journal of Industrial and Management Optimization, 2007, 3 (2) : 321-334. doi: 10.3934/jimo.2007.3.321 |
[5] |
Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223 |
[6] |
Rola Kiwan, Ahmad El Soufi. Where to place a spherical obstacle so as to maximize the second Dirichlet eigenvalue. Communications on Pure and Applied Analysis, 2008, 7 (5) : 1193-1201. doi: 10.3934/cpaa.2008.7.1193 |
[7] |
Liang Zhang, Wenyu Sun, Raimundo J. B. de Sampaio, Jinyun Yuan. A wedge trust region method with self-correcting geometry for derivative-free optimization. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169 |
[8] |
Jun Takaki, Nobuo Yamashita. A derivative-free trust-region algorithm for unconstrained optimization with controlled error. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 117-145. doi: 10.3934/naco.2011.1.117 |
[9] |
Sen Zhang, Guo Zhou, Yongquan Zhou, Qifang Luo. Quantum-inspired satin bowerbird algorithm with Bloch spherical search for constrained structural optimization. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3509-3523. doi: 10.3934/jimo.2020130 |
[10] |
M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control and Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014 |
[11] |
Zhong Wan, Chaoming Hu, Zhanlu Yang. A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search. Discrete and Continuous Dynamical Systems - B, 2011, 16 (4) : 1157-1169. doi: 10.3934/dcdsb.2011.16.1157 |
[12] |
Linh V. Nguyen. Spherical mean transform: A PDE approach. Inverse Problems and Imaging, 2013, 7 (1) : 243-252. doi: 10.3934/ipi.2013.7.243 |
[13] |
Mark Agranovsky, David Finch, Peter Kuchment. Range conditions for a spherical mean transform. Inverse Problems and Imaging, 2009, 3 (3) : 373-382. doi: 10.3934/ipi.2009.3.373 |
[14] |
Venkateswaran P. Krishnan, Vladimir A. Sharafutdinov. Ray transform on Sobolev spaces of symmetric tensor fields, I: Higher order Reshetnyak formulas. Inverse Problems and Imaging, 2022, 16 (4) : 787-826. doi: 10.3934/ipi.2021076 |
[15] |
Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control and Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237 |
[16] |
Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283 |
[17] |
Ruixue Zhao, Jinyan Fan. Quadratic tensor eigenvalue complementarity problems. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022073 |
[18] |
Jinyu Dai, Shu-Cherng Fang, Wenxun Xing. Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1677-1699. doi: 10.3934/jimo.2018117 |
[19] |
Zhou Sheng, Gonglin Yuan, Zengru Cui, Xiabin Duan, Xiaoliang Wang. An adaptive trust region algorithm for large-residual nonsmooth least squares problems. Journal of Industrial and Management Optimization, 2018, 14 (2) : 707-718. doi: 10.3934/jimo.2017070 |
[20] |
Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]