We present the moment cone (MC) relaxation and a hierarchy of sparse Lagrangian-SDP relaxations of polynomial optimization problems (POPs) using the unified framework established in Part I. The MC relaxation is derived for a POP of minimizing a polynomial subject to a nonconvex cone constraint and polynomial equality constraints. It is an extension of the completely positive programming relaxation for QOPs. Under a copositivity condition, we characterize the equivalence of the optimal values between the POP and its MC relaxation. A hierarchy of sparse Lagrangian-SDP relaxations, which is parameterized by a positive integer $\omega$ called the relaxation order, is proposed for an equality constrained POP. It is obtained by combining a sparse variant of Lasserre’s hierarchy of SDP relaxation of POPs and the basic idea behind the conic and Lagrangian-conic relaxations from the unified framework. We prove under a certain assumption that the optimal value of the Lagrangian-SDP relaxation with the Lagrangian multiplier $\lambda$ and the relaxation order $\omega$ in the hierarchy converges to that of the POP as $\lambda \rightarrow \infty$ and $\omega \rightarrow \infty$. The hierarchy of sparse Lagrangian-SDP relaxations is designed to be used in combination with the bisection and $1$-dimensional Newton methods, which was proposed in Part I, for solving large-scale POPs efficiently and effectively.
Citation
Research Report B-476, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro-ku, Tokyo 152-8552, January (2014).