×

Tighter bound estimation for efficient biquadratic optimization over unit spheres. (English) Zbl 07925620

Summary: Bi-quadratic programming over unit spheres is a fundamental problem in quantum mechanics introduced by pioneer work of Einstein, Schrödinger, and others. It has been shown to be NP-hard; so it must be solve by efficient heuristic algorithms such as the block improvement method (BIM). This paper focuses on the maximization of bi-quadratic forms with nonnegative coefficient tensors, which leads to a rank-one approximation problem that is equivalent to computing the M-spectral radius and its corresponding eigenvectors. Specifically, we propose a tight upper bound of the M-spectral radius for nonnegative fourth-order partially symmetric (PS) tensors. This bound, serving as an improved shift parameter, significantly enhances the convergence speed of BIM while maintaining computational complexity aligned with the initial shift parameter of BIM. Moreover, we elucidate that the computation cost of such upper bound can be further simplified for certain sets and delve into the nature of these sets. Building on the insights gained from the proposed bounds, we derive the exact solutions of the M-spectral radius and its corresponding M-eigenvectors for certain classes of fourth-order PS-tensors and discuss the nature of this specific category. Lastly, as a practical application, we introduce a testable sufficient condition for the strong ellipticity in the field of solid mechanics. Numerical experiments demonstrate the utility of the proposed results.

MSC:

90Cxx Mathematical programming

References:

[1] Ling, C.; Nie, J.; Qi, L.; Ye, Y., bi-quadratic optimization over unit spheres and semidefinite programming relaxations, SIAM J. Optim., 20, 1286-1310, 2010 · Zbl 1221.90074 · doi:10.1137/080729104
[2] He, S.; Li, Z.; Zhang, S., Approximation algorithms for homogeneous polynomial optimization with quadratic constraints, Math. Program., 125, 353-383, 2010 · Zbl 1206.90124 · doi:10.1007/s10107-010-0409-z
[3] Wang, Y.; Qi, L.; Zhang, X., A practical method for computing the largest M-eigenvalue of a fourth-order partially symmetric tensor, Numer. Linear Algebra Appl., 16, 589-601, 2009 · Zbl 1224.65101 · doi:10.1002/nla.633
[4] Zhang, X.; Ling, C.; Qi, L., Semidefinite relaxation bounds for bi-quadratic optimization problems with quadratic constraints, J. Global Optim., 49, 293-311, 2011 · Zbl 1237.90180 · doi:10.1007/s10898-010-9545-5
[5] Hu, SL; Huang, ZH, Alternating direction method for bi-quadratic programming, J. Global Optim., 51, 429-446, 2011 · Zbl 1248.65061 · doi:10.1007/s10898-010-9635-4
[6] Yang, Y.; Yang, Q., On solving bi-quadratic optimization via semidefinite relaxation, Comput. Optim. Appl., 53, 845-867, 2012 · Zbl 1285.90070 · doi:10.1007/s10589-012-9462-2
[7] Yang, Y.; Yang, Q.; Qi, L., Approximation bounds for trilinear and bi-quadratic optimization problems over nonconvex constraints, J. Optim. Theory Appl., 163, 841-858, 2014 · Zbl 1335.90076 · doi:10.1007/s10957-014-0538-2
[8] Wang, Y.; Caccetta, L.; Zhou, G., Convergence analysis of a block improvement method for polynomial optimization over unit spheres, Numer. Linear Algebra Appl., 22, 1059-1076, 2015 · Zbl 1374.65105 · doi:10.1002/nla.1996
[9] Qi, L.; Hu, S.; Zhang, X.; Xu, Y., Bi-quadratic tensors, bi-quadratic decompositions, and norms of bi-quadratic tensors, Front. Math. China, 16, 1-15, 2021 · Zbl 1469.15030 · doi:10.1007/s11464-021-0895-8
[10] Einstein, A.; Podolsky, B.; Rosen, N., Can quantum-mechanical description of physical reality be considered complete?, Phys. Rev., 47, 777-780, 1935 · Zbl 0012.04201 · doi:10.1103/PhysRev.47.777
[11] Schrödinger, E.: Die gegenwärtige situation in der quantenmechanik, Naturwissenschaften. 23, 807-812, 823-828, 844-849 (1935) · Zbl 0012.42703
[12] Doherty, AC; Parrilo, PA; Spedalieri, FM, Distinguishing separable and entangled states, Phys. Rev. Lett., 2002 · doi:10.1103/PhysRevLett.88.187904
[13] Dahl, G.; Leinaas, JM; Myrheim, J.; Ovrum, E., A tensor product matrix approximation problem in quantum physics, Linear Algebra Appl., 420, 711-725, 2007 · Zbl 1118.15027 · doi:10.1016/j.laa.2006.08.026
[14] Leordeanu, M., Hebert, M.: A spectral technique for correspondence problems using pairwise constraints. In: Proceedings of 10th IEEE International Conference of Computer Vision, vol. 2, pp. 1482-1489 (2005)
[15] Cour, T., Srinivasan, P., Shi, J.: Balanced graph matching. In: Proceedings of Advances in Neural Information Processing Systems, pp. 313-320 (2006)
[16] Egozi, A.; Keller, Y.; Guterman, H., A probabilistic approach to spectral graph matching, IEEE Trans. Pattern Anal., 35, 18-27, 2012 · doi:10.1109/TPAMI.2012.51
[17] Chiriţă, S.; Danescu, A.; Ciarletta, M., On the strong ellipticity of the anisotropic linearly elastic materials, J. Elast., 87, 1-27, 2007 · Zbl 1109.74008 · doi:10.1007/s10659-006-9096-7
[18] Han, D.; Dai, H.; Qi, L., Conditions for strong ellipticity of anisotropic elastic materials, J. Elast., 97, 1-13, 2009 · Zbl 1252.74006 · doi:10.1007/s10659-009-9205-5
[19] Li, S.; Li, C.; Li, Y., M-eigenvalue inclusion intervals for a fourth-order partially symmetric tensor, J. Comput. Appl. Math., 356, 391-401, 2019 · Zbl 1470.65060 · doi:10.1016/j.cam.2019.01.013
[20] Wang, X.; Che, M.; Wei, Y., Best rank-one approximation of fourth-order partially symmetric tensors by neural network, Numer. Math. Theory Methods Appl., 11, 673-700, 2018 · Zbl 1438.65088 · doi:10.4208/nmtma.2018.s01
[21] Miao, Y.; Wei, Y.; Chen, Z., Fourth-order tensor Riccati equations with the Einstein product, Linear Multilinear Algebra, 2020 · Zbl 1492.15011 · doi:10.1080/03081087.2020.1777248
[22] Qi, L.; Dai, H.; Han, D., Conditions for strong ellipticity and M-eigenvalues, Front. Math. China, 4, 349-364, 2009 · Zbl 1233.74004 · doi:10.1007/s11464-009-0016-6
[23] Waki, H.; Kim, S.; Kojima, M.; Muramatsu, M., Sums of squares and semidefinite program relaxations for polynomial optimization problems with constructed sparsity, SIAM J. Optim., 17, 218-242, 2006 · Zbl 1109.65058 · doi:10.1137/050623802
[24] Luo, ZQ; Zhang, S., A semidefinite relaxation scheme for multivariate quartic polynomial optimization with quadratic constraints, SIAM J. Optim., 20, 1716-1736, 2010 · Zbl 1201.90147 · doi:10.1137/090772952
[25] Ng, M.; Qi, L.; Zhou, G., Finding the largest eigenvalue of a nonnegative tensor, SIAM J. Matrix Anal. Appl., 31, 1090-1099, 2010 · Zbl 1197.65036 · doi:10.1137/09074838X
[26] Gloub, GH; Van Loan, CF, Matrix Computations, 1996, Baltimore: Johns Hopkins Universtiy Press, Baltimore · Zbl 0865.65009
[27] Kolda, TG; Mayo, JR, Shifted power method for computing tensor eigenpairs, SIAM J. Matrix Anal. Appl., 32, 1095-1124, 2012 · Zbl 1247.65048 · doi:10.1137/100801482
[28] Che, H.; Chen, H.; Wang, Y., On the M-eigenvalue estimation of fourth-order partially symmetric tensors, J. Ind. Manag. Optim., 16, 309-324, 2020 · Zbl 1438.15019 · doi:10.3934/jimo.2018153
[29] He, J.; Li, C.; Wei, Y., M-eigenvalue intervals and checkable sufficient conditions for the strong ellipticity, Appl. Math. Lett., 2019 · Zbl 1524.74060 · doi:10.1016/j.aml.2019.106137
[30] Li, S.; Chen, Z.; Li, C.; Zhao, J., Eigenvalue bounds of third-order tensors via the minimax eigenvalue of symmetric matrices, Comput. Appl. Math., 2020 · Zbl 1463.15025 · doi:10.1007/s40314-020-01245-0
[31] Li, S.; Chen, Z.; Liu, Q.; Lu, L., Bounds of M-eigenvalues and strong ellipticity conditions for elasticity tensors, Linear Multilinear Algebra, 2021 · Zbl 1512.15019 · doi:10.1080/03081087.2021.1885600
[32] Ling, C.; He, H.; Qi, L., Improved approximation results on standard quartic polynomial optimization, Optim. Lett., 11, 1767-1782, 2017 · Zbl 1410.90167 · doi:10.1007/s11590-016-1094-5
[33] Chen, H.; He, H.; Wang, Y.; Zhou, G., An efficient alternating minimization method for fourth degree polynomial optimization, J. Global Optim., 82, 83-103, 2022 · Zbl 1481.65088 · doi:10.1007/s10898-021-01060-9
[34] Ding, W.; Liu, J.; Qi, L.; Yan, H., Elasticity M-tensors and the strong ellipticity condition, Appl. Math. Comput., 2020 · Zbl 1433.74028 · doi:10.1016/j.amc.2019.124982
[35] Bhatia, R., Matrix Analysis, 2013, Springer
[36] Dong, X.; Thanou, D.; Frossard, P.; Vandergheynst, P., Learning Laplacian matrix in smooth graph signal representations, IEEE Trans. Signal Process., 64, 6160-6173, 2016 · Zbl 1414.94172 · doi:10.1109/TSP.2016.2602809
[37] Ye, K.; Lim, LH, Every matrix is a product of Toeplitz matrices, Found. Comput. Math., 16, 577-598, 2016 · Zbl 1342.15024 · doi:10.1007/s10208-015-9254-z
[38] Kriegeskorte, N.; Mur, M.; Bandettini, PA, Representational similarity analysis-connecting the branches of systems neuroscience, Front. Syst. Neurosci., 2008 · doi:10.3389/neuro.06.004.2008
[39] Feng, H., Qiu, X., Miao, H.L.: Hypothesis Testing for Two Sample Comparison of Network Data (2021). doi:10.48550/arXiv.2106.13931
[40] Zubov, L.; Rudev, A., A criterion for the strong ellipticity of the equilibrium equations of an isotropic non-linearly elastic material, J. Appl. Math. Mech., 75, 432-446, 2011 · Zbl 1272.74050 · doi:10.1016/j.jappmathmech.2011.09.008
[41] Li, S.; Li, Y., Checkable criteria for the M-positive definiteness of fourth-order partially symmetric tensors, Bull. Iran. Math. Soc., 46, 1455-1463, 2020 · Zbl 1447.15024 · doi:10.1007/s41980-019-00335-y
[42] Huang, Z.; Qi, L., Positive definiteness of paired symmetric tensors and elasticity tensors, J. Comput. Appl. Math., 338, 22-43, 2018 · Zbl 1392.74015 · doi:10.1016/j.cam.2018.01.025
[43] Qi, L.; Chen, H.; Chen, Y., Tensor Eigenvalues and Their Applications, 2018, Singapore: Springer, Singapore · Zbl 1398.15001 · doi:10.1007/978-981-10-8058-6
[44] Li, S.; Li, Y., Programmable sufficient conditions for the strong ellipticity of partially symmetric tensors, Appl. Math. Comput., 2021 · Zbl 1510.74010 · doi:10.1016/j.amc.2021.126134
[45] Gurtin, M., The linear theory of elasticity, Linear Theories of Elasticity and Thermoelasticity, 1-295, 1973, Berlin, Heidelberg: Springer, Berlin, Heidelberg
[46] Knowles, JK; Sternberg, E., On the ellipticity of the equations of nonlinear elastostatics for a special material, J. Elast., 5, 341-361, 1975 · Zbl 0323.73010 · doi:10.1007/BF00126996
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.