If we want to certify the nonexistence of real solutions to a polynomial system of equations, i.e.

$$ S = \{ x\in \mathbb{R}^n \ | \ h_i (x) = 0, \ i=1,\dots,t \} = \emptyset, $$

we can produce a Positivstellensatz refutation by writing $-1$ as a Sum of Squares (SOS) polynomial $s$ modulo the ideal generated by the $h_i$:

$$ -1 = \sum_i \alpha_i h_i + s $$

with $\alpha_i \in \mathbb{R}[x_1,\dots,x_n]$ and $ s = \sum_j f_j^2 $ (see, for example, Section 4 of http://www.mit.edu/~parrilo/pubs/files/SDPrelaxations.pdf).

The above paper proceeds in Section 5 by claiming that we can produce this refutation by relaxing it to a hierarchy of SDP feasibility problems, by bounding the degree of the unknown polynomials $s, \alpha_i$. My question is on the explicit way to represent the polynomials.

Now, we can use the result:

$$ \text{s is SOS} \iff \exists\, Q\geq0, \ s=m^TQm $$

where $m$ is the vector of monomials up to a suitable degree $d$ (of which there are $N = {n+d \choose d}$). As $Q$ is required to be positive semidefinite, it is a suitable decision variable for the SDP.

Now I want to represent an element of the ideal. We don't have any *a priori* restriction on the $\alpha_i$, so (and here I start to guess) I would parametrize them by, say, vectors $a_i\in\mathbb{R}^N$ — recovering $\alpha_i $ as $ a_i \cdot m$. But I don't understand how I can incorporate the decision variables $a_i$ into the SDP, as they should be in principle allowed to take any value.

My guesses are that I can somehow embed them into the semidefinite matrix, or that I can just avoid the problem altogether by imposing that they too are SOS. But such a procedure is never mentioned in any reference I looked into, and I start to wonder if I'm missing a piece, as I have little to no experience with SDPs.