• 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  April 2019 Early access  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 and 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.

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

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

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

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

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

[7]

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

[8]

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

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

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

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

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

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

[14]

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

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

[16]

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

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

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

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

[20]

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

[21]

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

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

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

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

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

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

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

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

[29]

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

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.

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

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

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

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

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

[7]

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

[8]

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

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

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

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

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

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

[14]

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

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

[16]

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

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

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

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

[20]

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

[21]

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

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

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

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

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

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

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

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

[29]

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

[1]

Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1505-1517. doi: 10.3934/jimo.2021030

[2]

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

[3]

Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2087-2102. doi: 10.3934/jimo.2019044

[4]

Zhong Wan, Chunhua Yang. New approach to global minimization of normal multivariate polynomial based on tensor. Journal of Industrial and Management Optimization, 2008, 4 (2) : 271-285. doi: 10.3934/jimo.2008.4.271

[5]

Venkateswaran P. Krishnan, Plamen Stefanov. A support theorem for the geodesic ray transform of symmetric tensor fields. Inverse Problems and Imaging, 2009, 3 (3) : 453-464. doi: 10.3934/ipi.2009.3.453

[6]

David Yang Gao, Changzhi Wu. On the triality theory for a quartic polynomial optimization problem. Journal of Industrial and Management Optimization, 2012, 8 (1) : 229-242. doi: 10.3934/jimo.2012.8.229

[7]

Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185

[8]

Xinmin Yang. On symmetric and self duality in vector optimization problem. Journal of Industrial and Management Optimization, 2011, 7 (3) : 523-529. doi: 10.3934/jimo.2011.7.523

[9]

Venkateswaran P. Krishnan, Vladimir A. Sharafutdinov. Ray transform on Sobolev spaces of symmetric tensor fields, I: Higher order Reshetnyak formulas. Inverse Problems and Imaging, , () : -. doi: 10.3934/ipi.2021076

[10]

Shenggui Zhang. A sufficient condition of Euclidean rings given by polynomial optimization over a box. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 93-101. doi: 10.3934/naco.2014.4.93

[11]

Reza Kamyar, Matthew M. Peet. Polynomial optimization with applications to stability analysis and control - Alternatives to sum of squares. Discrete and Continuous Dynamical Systems - B, 2015, 20 (8) : 2383-2417. doi: 10.3934/dcdsb.2015.20.2383

[12]

Zehui Jia, Xue Gao, Xingju Cai, Deren Han. The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1943-1971. doi: 10.3934/jimo.2020053

[13]

Lixing Han. An unconstrained optimization approach for finding real eigenvalues of even order symmetric tensors. Numerical Algebra, Control and Optimization, 2013, 3 (3) : 583-599. doi: 10.3934/naco.2013.3.583

[14]

Meng Xue, Yun Shi, Hailin Sun. Portfolio optimization with relaxation of stochastic second order dominance constraints via conditional value at risk. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2581-2602. doi: 10.3934/jimo.2019071

[15]

Lunji Song, Zhimin Zhang. Polynomial preserving recovery of an over-penalized symmetric interior penalty Galerkin method for elliptic problems. Discrete and Continuous Dynamical Systems - B, 2015, 20 (5) : 1405-1426. doi: 10.3934/dcdsb.2015.20.1405

[16]

Jaume Llibre, Y. Paulina Martínez, Claudio Vidal. Linear type centers of polynomial Hamiltonian systems with nonlinearities of degree 4 symmetric with respect to the y-axis. Discrete and Continuous Dynamical Systems - B, 2018, 23 (2) : 887-912. doi: 10.3934/dcdsb.2018047

[17]

Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control and Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601

[18]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial and Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891

[19]

Hong Seng Sim, Chuei Yee Chen, Wah June Leong, Jiao Li. Nonmonotone spectral gradient method based on memoryless symmetric rank-one update for large-scale unconstrained optimization. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021143

[20]

Jan Boman, Vladimir Sharafutdinov. Stability estimates in tensor tomography. Inverse Problems and Imaging, 2018, 12 (5) : 1245-1262. doi: 10.3934/ipi.2018052

2020 Impact Factor: 1.801

Metrics

  • PDF downloads (401)
  • HTML views (978)
  • Cited by (3)

Other articles
by authors

[Back to Top]