  We devise a scheme for solving an iterative sequence of linear programs (LPs)
or second order cone programs (SOCPs) to approximate the optimal value of any
semidefinite program (SDP) or sum of squares (SOS) program. The first LP and
SOCP-based bounds in the sequence come from the recent work of Ahmadi and
Majumdar on diagonally dominant sum of squares (DSOS) and scaled diagonally
dominant sum of squares (SDSOS) polynomials. We then iteratively improve on
these bounds by pursuing better bases in which more relevant SOS polynomials
admit a DSOS or SDSOS representation. Different interpretations of the
procedure from primal and dual perspectives are given. While the approach is
applicable to SDP relaxations of general polynomial programs, we apply it to
two problems of discrete optimization: the maximum independent set problem and
the partition problem. We further show that some completely trivial instances
of the partition problem lead to strictly positive polynomials on the boundary
of the sum of squares cone and hence make the SOS relaxation fail.
