Re: SOS with integrality constraints

[Johan Löfberg]

Runs here, but I think you mean

sol = solvesos(F,[],[],[-t;-l]);

However, this leads to a nonconvex problem, as the resulting relaxation is expressed in t^2. YALMIP reduces the initial 2x2 nonlinear SDP to a nonlinear scalar program, and uses fmincon.

Nonlinear model makes no sense though. If you want to impose that the parameter t is non-negative, just add the constraint t>=0

Further, I don't see the algebraic logic in the model. You want p(x) to be psd when x^2 = x. Hence, postivstellensatz says you want to find a some polynomial s(x) such that p(x) - s(x)*(x^2-x)>=0

[s,coeffs] = polynomial(x,2);
solvesos(sos(p - s*(x^2-x)),[],[],coeffs)

[Noah]

Thank you, yes that's a good point. I had just realized that which is why I deleted the post. We would also have to constrain s(x) to be SOS as well, right? 

[Noah]

When I run this on the example

p = 1 +2*x+x^2;

[s,coeffs] = polynomial(x,0);

solvesos(sos(p - s*(x^2-x)),[],[],coeffs)

I get -1-1.0000*x for sdisplay(sosd(F)) and   -1.1333 for value(coeffs). If I'm not mistaken, implies that 
-1.1333*(x^2-x) + 1 + 2x+x^2 = (-1-x)^2.
Am I missing something?
Thank you very much for the help.

[Noah]

Never mind, I fixed it! Thank you for the help.

[Johan Löfberg]

No, it means p >= s(x)*(x^2-x), i.e., that p(x) is larger than zero when x^2=x

s(x) is an arbitrary expression, does not have to be psd