# SDP representation of ideal polynomials for positivstellensatz refutations

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.

Free decision variables $$a_i$$ can be represented in SDPs by the difference of two positive variables $$x_{i,1} - x_{i,2}$$, and positive variables $$x_{i,j}$$ can be incorporated by enlarging the positive semidefinite matrix with a diagonal block $$diag(x_{1,1},\dots,x_{t,2})$$