Extension of Completely Positive Cone Relaxation to Polynomial Optimization

We propose the moment cone relaxation for a class of polynomial optimization problems (POPs) to extend the results on the completely positive cone programming relaxation for the quadratic optimization (QOP) model by Arima, Kim and Kojima. The moment cone relaxation is constructed to take advantage of sparsity of the POPs, so that efficient numerical methods can be developed in the future. We establish the equivalence between the optimal value of the POP and that of the moment cone relaxation under conditions similar to the ones assumed in the QOP model. The proposed method is compared with the canonical convexification procedure recently proposed by Pe$\tilde{\mbox{n}}$a, Vera and Zuluaga for POPs. The moment cone relaxation is theoretically powerful, but numerically intractable. For tractable numerical methods, the doubly nonnegative cone relaxation is derived from the moment cone relaxation. Exploiting sparsity in the doubly nonnegative cone relaxation and its incorporation into Lasserre's semidefinite relaxation are briefly discussed.

Citation

B-471, Dept. of Math. and Comp. Sciences, Tokyo Institute of Technology, Tokyo 152-8552, February 2013.

Article

Download

View Extension of Completely Positive Cone Relaxation to Polynomial Optimization