  In theory, hierarchies of semidefinite programming (SDP) relaxations based on
sum of squares (SOS) polynomials have been shown to provide arbitrarily close
approximations for a general polynomial optimization problem (POP). However,
due to the computational challenge of solving SDPs, it becomes difficult to use
SDP hierarchies for large-scale problems. To address this, hierarchies of
second-order cone programming (SOCP) relaxations resulting from a restriction
of the SOS polynomial condition have been recently proposed to approximate
POPs. Here, we consider alternative ways to use this SOCP restrictions of the
SOS condition. In particular, we show that SOCP hierarchies can be effectively
used to strengthen hierarchies of linear programming (LP) relaxations for POPs.
Specifically, we show that this solution approach is substantially more
effective in finding solutions of certain POPs for which the more common
hierarchies of SDP relaxations are known to perform poorly. Furthermore, when
the feasible set of the POP is compact, these SOCP hierarchies converge to the
POP's optimal value.
