Completely positive and completely positive semidefinite tensor relaxations for polynomial optimization (Q1704915)

This paper deals with completely positive (CP) and completely positive semidefinite (CPSD) tensor relaxations for a polynomial optimization problem (POP). The results for quadratic programs (QP) are extended to general POPs by using CP and CPSD tensor cones. \textit{I. M. Bomze} shows that a completely positive matrix relaxation beats Lagrangian relaxations for quadratic programs with both linear and quadratic constraints [SIAM J. Optim. 25, No. 3, 1249--1275 (2015; Zbl 1317.90224)]. A natural question is whether similar results hold for general POPs that are not necessarily quadratic. The authors show that CP tensor relaxations provide better bounds than Lagrangian relaxations for general POPs and provide tractable approximations for CP and CPSD tensor cones that can be used to globally approximate general POPs. Further, it is observed that CP and CPSD tensor relaxations yield better bounds than completely positive and positive semidefinite matrix relaxations for quadratic reformulations of some class of POPs. Linear matrix inequality (LMI) approximation strategies for the completely positive and completely positive semidefinite tensor cones are also developed and a comparison of tensor relaxations with matrix relaxations obtained using the quadratic approach is done by obtaining numerical results on several POPs. Preliminary numerical results are provided on more general cases of POPs and it is shown that the approximation of CP tensor cone programs can yield tighter bounds than relaxations based on doubly nonnegative (DNN) matrices for completely positive matrix relaxation to the reformulated quadratic programs. Finally, future research directions are also provided.