SDP relaxation method for detecting P-tensors

  • Li Li Tianjin University
  • Xiao Wang Tianjin University
Keywords: P-tensor, P_0-tensor, Lasserre's hierarchy, SDP relaxation


P-tensor and P_0-tensor are introduced in tensor complementarity problem, which have wide applications in many fields such as game theory, tensor complementarity problem. In this paper, we discuss how to check whether a given symmetric tensor is P(P_0)-tensor or not.  For a symmetric tensor, it is a P(P_0)-tensor is equivalent to the positivity(nonnegativity) of a polynomial optimization problem. For such polynomial optimization problem, a SDP relaxation method is proposed. By the proposed method, the P(P_0)-tensor can be detected by solving a finite number of SDP relaxations. Furthermore, numerical examples are reported to show the efficiency of the proposed algorithm.


C. Cui, Y. Dai and J. Nie, All real eigenvalues of symmetric tensors, SIAM Journal on Matrix Analysis and Applications, vol. 35, no. 4, pp. 1582–1601, 2014.

D. Cartwright and B. Sturmfels, The number of eigenvalues of a tensor, Linear Algebra and Its Applications, vol. 438, no. 2, pp. 942–952, 2013.

H. Chen, Y. Chen, G. Li and L. Qi, Positive semi-definiteness and extremal H-eigenvalues of extended essentially nonnegative tensors, arXiv: 1511. 02328v1.

R.W. Cottle, J.S. Pang and R.E. Stone, The linear complementarity problem, Academic Press, Boston 1992.

W. Ding, Z. Luo and L. Qi, P-tensor, P0-tensor, and tensor complementarity problem, arXiv: 1507. 06731v1.

F. Facchinei and J.S. Pang, Finite dimensionl variatioal inequalities and complementarity problems, Springer, New York 2003.

D. Henrion, J.B. Lasserre and Y. Lofberg, GloptiPoly 3: Moments, Optimization and Semidfinite Programming, Optimization, Methods and Softwares, vol. 24, no. 4-5, pp. 761–779, 2009.

T.G. Kolda and J.R. Mayo, Shifted power mthod for computing tensor eigenpairs, SIAM Journal on Matrix Analysis and Applications, vol. 32, no. 4, pp. 1095–1124, 2011.

J.B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM Journal on Optimization, vol. 11, no. 3, pp. 796–817, 2001.

J.B. Lasserre, Moments, positive polynomials and their applications, Imperial College Press, 2009.

M. Laurent, Sums of squares, moment matrices and optimization over polynomials, Emerging Applications of Algebraic Geometry, IMA Volumes in Mathematics and its Applications (Eds. M. Putinar and S. Sullivant), Springer, vol. 149, pp. 157–270, 2009.

J. Nie, The hierarchy of local minimums in polynomial optimizaion, Mathematical Programming, to appear.

J. Nie and X. Zhang, Real eigenvalues of nonsymmetric tensors, arXiv:1503.06881.

L. Qi, D. Sun, and G. Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities, Mathematical Programming, vol. 87, no. 1, pp. 1–35, 2000.

L. Qi, Eigenvalues of a real supersymmetric tensor, Journal of Symbolic Computation, vol. 40, no. 6, pp. 1302–1324, 2005.

L. Qi, Eigenvalues and invariants of tensors, Journal of Mathematics Analysis and Applications, vol. 325, no. 2, pp. 1363–1377,2007.

L. Qi, F.Wang and Y.Wang, Z-eigenvalue methods for a global polynomial optimization problem, Mathematical Programming, vol.118, no. 2, pp. 301–316, 2009.

Y. Song and L. Qi, Properties of some classes of structured tensors, Journal of Optimization Theory and Applications, vol. 165, no.3, pp. 854–873, 2015.

X. Zhang, L. Qi and Y. Ye, The cubic spherical optimization problems, Mathematics of Computation, vol. 81, pp. 1513–1525, 2012.

How to Cite
Li, L., & Wang, X. (2017). SDP relaxation method for detecting P-tensors. Statistics, Optimization & Information Computing, 5(4), 295-301.
Research Articles