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.


1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.