SDP relaxation method for detecting P-tensors
Abstract
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.References
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.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
