×

zbMATH — the first resource for mathematics

A semidefinite relaxation method for second-order cone polynomial complementarity problems. (English) Zbl 1441.15015
Summary: This paper discusses how to compute all real solutions of the second-order cone tensor complementarity problem when there are finitely many ones. For this goal, we first formulate the second-order cone tensor complementarity problem as two polynomial optimization problems. Based on the reformulation, a semidefinite relaxation method is proposed by solving a finite number of semidefinite relaxations with some assumptions. Numerical experiments are given to show the efficiency of the method.
MSC:
15A69 Multilinear algebra, tensor calculus
15A18 Eigenvalues, singular values, and eigenvectors
90C22 Semidefinite programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
Software:
GloptiPoly; SeDuMi
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bochnak, J.; Coste, M.; Roy, M-F, Real Algebraic Geometry (1998), Berlin: Springer, Berlin · Zbl 0633.14016
[2] Cui, C.; Dai, Y.; Nie, J., All real eigenvalues of symmetric tensors, SIAM J. Matrix Anal. Appl., 35, 1582-1601 (2014) · Zbl 1312.65053
[3] Curto, R.; Fialkow, L., Truncated K-moment problems in several variable, J. Oper. Theory, 54, 189-226 (2005) · Zbl 1119.47304
[4] Chen, H.; Qi, L.; Song, Y., Column sufficient tensors and tensor complementarity problems, Front. Math. China, 13, 255-276 (2018) · Zbl 1418.90253
[5] Che, M.; Qi, L.; Wei, Y., Stochastic \(R_0\) tensors to stochastic tensor complementarity problems, Optim. Lett., 13, 261-279 (2019) · Zbl 1417.90108
[6] Chen, J.; Tseng, P., An unconstrained smooth minimization reformulation of the secondorder cone complementarity problem, Math. Program., 104, 293-327 (2005) · Zbl 1093.90063
[7] Ding, W.; Luo, Z.; Qi, L., \(P\)-tensors, \(P_0\)-tensors, and their applications, Linear Algebra Appl., 555, 336-354 (2018) · Zbl 1396.15020
[8] Fan, J.; Nie, J.; Zhao, R., The maximum tensor complementarity eigenvalues, Optim. Methods Softw. (2018)
[9] Fukushima, M.; Luo, Z.; Tseng, P., Smoothing functions for second-order-cone complementarity problems, SIAM J. Optim., 12, 436-460 (2002) · Zbl 0995.90094
[10] Fan, J.; Nie, J.; Zhou, A., Tensor eigenvalue complementarity problems, Math. Program., 170, 507-539 (2018) · Zbl 1427.65096
[11] Facchinei, F.; Pang, J., Finite-Dimensional Variational Inequalities and Complementarity Problems (2003), Berlin: Springer, Berlin · Zbl 1062.90001
[12] Guo, Q.; Zheng, M.; Huang, Z-H, Properties of S-tensors, Linear and Multilinear Algebra, 67, 685-696 (2019) · Zbl 1411.90336
[13] Henrion, D.; Lasserre, J.; Lofberg, Y., GloptiPoly 3: moments, optimization and semidfinite programming, Optim. Methods Softw., 24, 761-779 (2009) · Zbl 1178.90277
[14] Helton, J.; Nie, J., A semidefinite approach for truncated K-moment problems, Found. Comput. Math., 12, 851-881 (2012) · Zbl 1259.44005
[15] Huang, Z-H; Qi, L., Tensor complementarity problems \(-\) Part I: basic theory, J. Optim. Theory Appl., 183, 1-23 (2019) · Zbl 1434.90203
[16] Hayashi, S.; Yamashita, N.; Fukushima, M., Robust Nash equilibria and second-order cone complementarity problems, J. Nonlinear Convex Anal., 6, 283-296 (2005) · Zbl 1137.91310
[17] Lasserre, J., Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 796-817 (2001) · Zbl 1010.90061
[18] Lasserre, J., Jean Bernard Lasserre: moments, positive polynomials and their applications, Found. Comput. Math., 11, 489-497 (2011)
[19] Lasserre, J., An Introduction to Polynomial and Semi-Algebraic Optimization (2015), Cambridge: Cambridge University Press, Cambridge · Zbl 1320.90003
[20] Laurent, M.; Putinar, M.; Sullivant, S., “Sums of squares, moment matrices and optimization over polynomials”, Emerging Applications of Algebraic Geometry, IMA Volumes in Mathematics and its Applications, 157-270 (2009), Berlin: Springer, Berlin · Zbl 1163.13021
[21] Laurent, M.: “Optimization over polynomials: selected topics”. In: Proceedings of the International Congress of Mathematicians, Seoul (2014) · Zbl 1373.90097
[22] Nie, J., Certifying convergence of Lasserre’s hierarchy via flat truncation, Math. Program., 142, 485-510 (2013) · Zbl 1305.65151
[23] Nie, J., Polynomial optimization with real varieties, SIAM J. Optim., 23, 1634-1646 (2013) · Zbl 1286.65079
[24] Nie, J.; Yang, Z.; Zhang, X., A complete semidefinite algorithm for detecting copositive matrices and tensors, SIAM J. Optim., 28, 2902-2921 (2018) · Zbl 1406.15026
[25] Nie, J.; Zhang, X., Real eigenvalues of nonsymmetric tensors, Comp. Optim. Appl., 70, 1-32 (2018) · Zbl 1397.65057
[26] Qi, L., The best rank-one approximation ratio of a tensor space, SIAM J. Matrix Anal. Appl., 32, 430-442 (2011) · Zbl 1228.15010
[27] Qi, L.; Huang, Z-H, Tensor complementarity problems \(-\) Part II: solution methods, J. Optim. Theory Appl., 183, 365-385 (2019) · Zbl 1429.90082
[28] Sturm, J., Sedumi 1.02: a matlab toolbox for optimization over symmetric cones, Optim. Methods Softw., 11-12, 625-653 (1999) · Zbl 0973.90526
[29] Song, Y.; Qi, L., Properties of tensor complementarity problem and some classes of structured tensors, Ann. Appl. Math., 3, 308-323 (2017) · Zbl 1399.15036
[30] Wang, X.; Zhang, X.; Zhou, G., SDP relaxation algorithms for \(P(P0)\)- tensor detection, Comput. Optim. Appl. (2019)
[31] Zhang, L.; Yang, W., An effective matrix splitting method for the second-order cone complementarity problem, SIAM J. Optim., 24, 1178-1205 (2014) · Zbl 1309.90113
[32] Zheng, M.; Zhang, Y.; Huang, Z-H, Global error bounds for the tensor complementarity problem with a P-tensor, J. Ind. Manag. optim., 15, 933-946 (2019) · Zbl 1438.90372
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.