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.



SDP representation of ideal polynomials for positivstellensatz refutations
As I guessed, I was missing a fairly trivial piece (and most of my question is not even relevant to the answer).


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})$


