• Previous Article
    A semidefinite relaxation algorithm for checking completely positive separable matrices
  • JIMO Home
  • This Issue
  • Next Article
    An integrated Principal Component Analysis and multi-objective mathematical programming approach to agile supply chain network design under uncertainty
April  2019, 15(2): 881-891. doi: 10.3934/jimo.2018075

Test of copositive tensors

a. 

School of Mathematics, Tianjin University, 135 Yaguan Road, Tianjin 300350, China

b. 

Department of Mathematics, Taiyuan Normal University, 319 University Street, Jinzhong, Shanxi 030619, China

c. 

Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, China

* Corresponding author: Xinzhen Zhang

Received  June 2017 Revised  January 2018 Published  June 2018

Fund Project: The second author is supported by the National Natural Science Foundation of China(Grant No. 11471242). The third author is supported by the National Natural Science Foundation of China(Grant No.11431002) and the fourth author is supported by the Hong Kong Research Grant Council (Grant No. PolyU 501913, 15302114, 15300715 and 15301716).

In this paper, an SDP relaxation algorithm is proposed to test the copositivity of higher order tensors. By solving finitely many SDP relaxations, the proposed algorithm can determine the copositivity of higher order tensors. Furthermore, for any copositive but not strictly copositive tensor, the algorithm can also check it exactly. Some numerical results are reported to show the efficiency of the proposed algorithm.

Citation: Li Li, Xinzhen Zhang, Zheng-Hai Huang, Liqun Qi. Test of copositive tensors. Journal of Industrial & Management Optimization, 2019, 15 (2) : 881-891. doi: 10.3934/jimo.2018075
References:
[1]

X. BaiZ. Huang and Y. Wang, Global uniqueness and solvability for tensor complementarity problems, Journal of Optimization Theory and Applications, 170 (2016), 72-84.  doi: 10.1007/s10957-016-0903-4.  Google Scholar

[2]

M. CheL. Qi and Y. Wei, Positive definite tensors to nonlinear complymentarity problems, Journal of Optimization Theory and Applications, 168 (2016), 475-487.  doi: 10.1007/s10957-015-0773-1.  Google Scholar

[3]

H. Chen, Y. Chen, G. Li and L. Qi, A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test, Numerical Linear Algebra with applications, 25 (2018), e2125. doi: 10.1002/nla.212.  Google Scholar

[4]

H. ChenZ. Huang and L. Qi, Copositive tensor detection and its applications in physics and hypergraphs, Computational Optimization and Applications, 69 (2018), 133-158.  doi: 10.1007/s10589-017-9938-1.  Google Scholar

[5]

H. ChenZ. Huang and L. Qi, Copositivity detection of tensors: Theory and algorithm, Journal of Optimization Theory and Applications, 174 (2017), 746-761.  doi: 10.1007/s10957-017-1131-2.  Google Scholar

[6]

H. ChenL. Qi and Y. Song, Column sufficient tensors and tensor complementarity problems, Fronterior of Mathematics in China, 13 (2018), 255-276.  doi: 10.1007/s11464-018-0681-4.  Google Scholar

[7]

W. Ding, Z. Luo and L. Qi, P-Tensors, P0-Tensors, and tensor complementarity problem, arXiv: 1507.06731. Google Scholar

[8]

J. FanJ. Nie and A. Zhou, Tensor eigenvalue complementarity problems, Mathematical Programming, (2017), 1-33.  doi: 10.1007/s10107-017-1167-y.  Google Scholar

[9]

D. Henrion and J. B. Lasserre, Detecting global optimality and extracting solutions in GloptiPoly, in Positive Polynomials in Control, Lecture Notes in Control and Information Science, 312, Springer, Berlin, 2005, 293-310. doi: 10.1007/10997703_15.  Google Scholar

[10]

D. HenrionJ. Lasserre and J. Loefberg, GloptiPoty 3: Moments, optimization and semidefinite programming, Optimization Methods and Software, 24 (2009), 761-779.  doi: 10.1080/10556780802699201.  Google Scholar

[11]

Z. H. Huang and L. Qi, Formulating an n-person noncooperative game as a tensor complementarity problem, Computational Optimization and Applications, 66 (2017), 557-576.  doi: 10.1007/s10589-016-9872-7.  Google Scholar

[12]

K. Kannike, Vacuum stability of a general scalar potential of a few fields, European Physical Journal C, 76 (2016), 324. doi: 10.1140/epjc/s10052-016-4160-3.  Google Scholar

[13]

T. Kolda and J. Mayo, Shifted power method for computing tensor eigenpairs, SIAM Journal on Matrix Analysis and Applications, 32 (2011), 1095-1124.  doi: 10.1137/100801482.  Google Scholar

[14]

J. Lasserre, Moments, positive polynomials and their applications, Series on Optimization and Its Applications, 1 (2009). doi: 10.1142/p665.  Google Scholar

[15]

J. LasserreM. Laurent and P. Rostalski, Semidefinite characterization and computation of zero-dimensional real radical ideals, Foundations of Computational Mathematics, 8 (2008), 607-647.  doi: 10.1007/s10208-007-9004-y.  Google Scholar

[16]

J. Lasserre, Global optimization with polynomial and the problem of moments, SIAM Journal on Optimization, 11 (2001), 796-817.  doi: 10.1137/S1052623400366802.  Google Scholar

[17]

M. Laurent, Sums of squares, moment matrices and optimization over polynomial, in Emerging Applications of Algebraic Geometry (eds. M. Putinar, S. Sullivant), Part of the The IMA Volumes in Mathematics and its Applications book series (IMA, volume 149), Springer, 2009, 157-270. doi: 10.1007/978-0-387-09686-5_7.  Google Scholar

[18]

C. LingH. He and L. Qi, Improved approximation results on standard quatric polynomial optimization, Optimization Letters, 11 (2017), 1767-1782.  doi: 10.1007/s11590-016-1094-5.  Google Scholar

[19]

C. LingH. He and L. Qi, On the cone eigenvalue complementarity problem for higher-order tensors, Computational Optimization and Applications, 63 (2016), 143-168.  doi: 10.1007/s10589-015-9767-z.  Google Scholar

[20]

T. Motzkin, Quadratic forms, National Bureau of Standards Report, 1818 (1952), 11-12.   Google Scholar

[21]

J. Nie, Polynomial optimization with real varieties, SIAM Journal on Optimization, 23 (2013), 1634-1646.  doi: 10.1137/120898772.  Google Scholar

[22]

J. Nie, Certifying convergence of Lasserre's hierachy via flat truncation, Mathematical Programming, 142 (2013), 485-510.  doi: 10.1007/s10107-012-0589-9.  Google Scholar

[23]

J. PeñaJ. Vera and L. Zuluaga, Completely positive reformulations for polynomial optimization, Mathematical Programming, 151 (2015), 405-431.  doi: 10.1007/s10107-014-0822-9.  Google Scholar

[24]

L. Qi, Symmetric nonegative tensors and copositive tensors, Linear Algebra and its Applications, 439 (2013), 228-238.  doi: 10.1016/j.laa.2013.03.015.  Google Scholar

[25]

Y. Song and L. Qi, Eigenvalue analysis of constrained minimization problem for homogeneous polynomial, Journal of Global Optimization, 64 (2016), 563-575.  doi: 10.1007/s10898-015-0343-y.  Google Scholar

[26]

Y. Song and L. Qi, Tensor complementarity problem and semi-positive tensors, Journal of Optimization Theory and Applications, 169 (2016), 1069-1078.  doi: 10.1007/s10957-015-0800-2.  Google Scholar

[27]

J. Sturm, SeDuMi 1.02: a matlab toolbox for optimizatoin over symmertic cones, Optimization Methods and Softwar, 11 (1999), 625-653.  doi: 10.1080/10556789908805766.  Google Scholar

[28]

X. ZhangC. Ling and L. Qi, The best rank-1 approximation of a symmetric tensor and related spherical optimization problems, SIAM Journal on Matrix Analysis and Applications, 33 (2012), 806-821.  doi: 10.1137/110835335.  Google Scholar

[29]

J. Zeng and D. Li, Convergence of multigrid iterative solutions for symmetric copositive linear complementarity problems, Mathematical Numerica Sinica, 16 (1994), 25-30.   Google Scholar

show all references

References:
[1]

X. BaiZ. Huang and Y. Wang, Global uniqueness and solvability for tensor complementarity problems, Journal of Optimization Theory and Applications, 170 (2016), 72-84.  doi: 10.1007/s10957-016-0903-4.  Google Scholar

[2]

M. CheL. Qi and Y. Wei, Positive definite tensors to nonlinear complymentarity problems, Journal of Optimization Theory and Applications, 168 (2016), 475-487.  doi: 10.1007/s10957-015-0773-1.  Google Scholar

[3]

H. Chen, Y. Chen, G. Li and L. Qi, A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test, Numerical Linear Algebra with applications, 25 (2018), e2125. doi: 10.1002/nla.212.  Google Scholar

[4]

H. ChenZ. Huang and L. Qi, Copositive tensor detection and its applications in physics and hypergraphs, Computational Optimization and Applications, 69 (2018), 133-158.  doi: 10.1007/s10589-017-9938-1.  Google Scholar

[5]

H. ChenZ. Huang and L. Qi, Copositivity detection of tensors: Theory and algorithm, Journal of Optimization Theory and Applications, 174 (2017), 746-761.  doi: 10.1007/s10957-017-1131-2.  Google Scholar

[6]

H. ChenL. Qi and Y. Song, Column sufficient tensors and tensor complementarity problems, Fronterior of Mathematics in China, 13 (2018), 255-276.  doi: 10.1007/s11464-018-0681-4.  Google Scholar

[7]

W. Ding, Z. Luo and L. Qi, P-Tensors, P0-Tensors, and tensor complementarity problem, arXiv: 1507.06731. Google Scholar

[8]

J. FanJ. Nie and A. Zhou, Tensor eigenvalue complementarity problems, Mathematical Programming, (2017), 1-33.  doi: 10.1007/s10107-017-1167-y.  Google Scholar

[9]

D. Henrion and J. B. Lasserre, Detecting global optimality and extracting solutions in GloptiPoly, in Positive Polynomials in Control, Lecture Notes in Control and Information Science, 312, Springer, Berlin, 2005, 293-310. doi: 10.1007/10997703_15.  Google Scholar

[10]

D. HenrionJ. Lasserre and J. Loefberg, GloptiPoty 3: Moments, optimization and semidefinite programming, Optimization Methods and Software, 24 (2009), 761-779.  doi: 10.1080/10556780802699201.  Google Scholar

[11]

Z. H. Huang and L. Qi, Formulating an n-person noncooperative game as a tensor complementarity problem, Computational Optimization and Applications, 66 (2017), 557-576.  doi: 10.1007/s10589-016-9872-7.  Google Scholar

[12]

K. Kannike, Vacuum stability of a general scalar potential of a few fields, European Physical Journal C, 76 (2016), 324. doi: 10.1140/epjc/s10052-016-4160-3.  Google Scholar

[13]

T. Kolda and J. Mayo, Shifted power method for computing tensor eigenpairs, SIAM Journal on Matrix Analysis and Applications, 32 (2011), 1095-1124.  doi: 10.1137/100801482.  Google Scholar

[14]

J. Lasserre, Moments, positive polynomials and their applications, Series on Optimization and Its Applications, 1 (2009). doi: 10.1142/p665.  Google Scholar

[15]

J. LasserreM. Laurent and P. Rostalski, Semidefinite characterization and computation of zero-dimensional real radical ideals, Foundations of Computational Mathematics, 8 (2008), 607-647.  doi: 10.1007/s10208-007-9004-y.  Google Scholar

[16]

J. Lasserre, Global optimization with polynomial and the problem of moments, SIAM Journal on Optimization, 11 (2001), 796-817.  doi: 10.1137/S1052623400366802.  Google Scholar

[17]

M. Laurent, Sums of squares, moment matrices and optimization over polynomial, in Emerging Applications of Algebraic Geometry (eds. M. Putinar, S. Sullivant), Part of the The IMA Volumes in Mathematics and its Applications book series (IMA, volume 149), Springer, 2009, 157-270. doi: 10.1007/978-0-387-09686-5_7.  Google Scholar

[18]

C. LingH. He and L. Qi, Improved approximation results on standard quatric polynomial optimization, Optimization Letters, 11 (2017), 1767-1782.  doi: 10.1007/s11590-016-1094-5.  Google Scholar

[19]

C. LingH. He and L. Qi, On the cone eigenvalue complementarity problem for higher-order tensors, Computational Optimization and Applications, 63 (2016), 143-168.  doi: 10.1007/s10589-015-9767-z.  Google Scholar

[20]

T. Motzkin, Quadratic forms, National Bureau of Standards Report, 1818 (1952), 11-12.   Google Scholar

[21]

J. Nie, Polynomial optimization with real varieties, SIAM Journal on Optimization, 23 (2013), 1634-1646.  doi: 10.1137/120898772.  Google Scholar

[22]

J. Nie, Certifying convergence of Lasserre's hierachy via flat truncation, Mathematical Programming, 142 (2013), 485-510.  doi: 10.1007/s10107-012-0589-9.  Google Scholar

[23]

J. PeñaJ. Vera and L. Zuluaga, Completely positive reformulations for polynomial optimization, Mathematical Programming, 151 (2015), 405-431.  doi: 10.1007/s10107-014-0822-9.  Google Scholar

[24]

L. Qi, Symmetric nonegative tensors and copositive tensors, Linear Algebra and its Applications, 439 (2013), 228-238.  doi: 10.1016/j.laa.2013.03.015.  Google Scholar

[25]

Y. Song and L. Qi, Eigenvalue analysis of constrained minimization problem for homogeneous polynomial, Journal of Global Optimization, 64 (2016), 563-575.  doi: 10.1007/s10898-015-0343-y.  Google Scholar

[26]

Y. Song and L. Qi, Tensor complementarity problem and semi-positive tensors, Journal of Optimization Theory and Applications, 169 (2016), 1069-1078.  doi: 10.1007/s10957-015-0800-2.  Google Scholar

[27]

J. Sturm, SeDuMi 1.02: a matlab toolbox for optimizatoin over symmertic cones, Optimization Methods and Softwar, 11 (1999), 625-653.  doi: 10.1080/10556789908805766.  Google Scholar

[28]

X. ZhangC. Ling and L. Qi, The best rank-1 approximation of a symmetric tensor and related spherical optimization problems, SIAM Journal on Matrix Analysis and Applications, 33 (2012), 806-821.  doi: 10.1137/110835335.  Google Scholar

[29]

J. Zeng and D. Li, Convergence of multigrid iterative solutions for symmetric copositive linear complementarity problems, Mathematical Numerica Sinica, 16 (1994), 25-30.   Google Scholar

[1]

Francisco Braun, Jaume Llibre, Ana Cristina Mereu. Isochronicity for trivial quintic and septic planar polynomial Hamiltonian systems. Discrete & Continuous Dynamical Systems - A, 2016, 36 (10) : 5245-5255. doi: 10.3934/dcds.2016029

[2]

Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79

[3]

Eduardo Casas, Christian Clason, Arnd Rösch. Preface special issue on system modeling and optimization. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021008

[4]

Hirofumi Notsu, Masato Kimura. Symmetry and positive definiteness of the tensor-valued spring constant derived from P1-FEM for the equations of linear elasticity. Networks & Heterogeneous Media, 2014, 9 (4) : 617-634. doi: 10.3934/nhm.2014.9.617

[5]

Mao Okada. Local rigidity of certain actions of solvable groups on the boundaries of rank-one symmetric spaces. Journal of Modern Dynamics, 2021, 17: 111-143. doi: 10.3934/jmd.2021004

[6]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[7]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[8]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378

[9]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[10]

Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021008

[11]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028

[12]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (232)
  • HTML views (961)
  • Cited by (3)

Other articles
by authors

[Back to Top]