@Denis: For polynomials with all roots real, Descartes' rule gives the exact number of roots.

@Rudi: Okay, sorry, I rather should get a coffee, too.

@Rudi: Okay, but with the new notation, wouldn't you have to minimize $\log(\det(B))$ now? So after all, it can still not be done with semidefinite programming, right?

@Rudi: Can you explain further. You want p to be of a certain shape, right? On the other hand, this shape seems to contradict the positive semidefiniteness constraint you put on $B$, doesn't it? By the way there seems to be a little typo in the shape you specify for $p$. Anyway, I guess something must be wrong for in the equation $p=s_1q_1+s_2q_2+t+(y-1)u$ you could always choose $s_1=s_2=u=0$ so that $p$ can be any positive semidefinite quadratic form in $x$ and $y$. So maximizing $\log(\det(B))$ is un unbounded problem.

@Rudi: This won't give a semidefinite program (at least not in an obvious way) since $p$ depends in a cubic way on the entries of $A$ and $z$. To have a semidefinite program you can only afford linear dependence. The other problem is that the "technical condition" for the "only if" part is not so clear. This would be worth investigating. What I know immediately is that if the two original ellipsoids are compact (which is not always the case in the problem as it is posed), then it is true that $p+\varepsilon$ for each $\varepsilon>0$ (instead of $p$) has such a sums of squares representation.

@Patricia: Sums of squares don't necessarily have all coefficients nonnegative.

I am so sorry, you are again right. But if you take a pentagon instead of a square, then it works. Not all of the $L_i L_j$ were strictly positive on at least one of the vertices of the square but for the pentagon this works.

You are right, I am sorry for suggesting this counterexample. However, I think that I have now a valid counterexample, see above.