Some questions regarding to Sum of Squares Tools in YALMIP.

[SRB]

Hello,

I have small doubt. The doubt is as follows: 

Let P(x,y) be the polynomial whose certificate of positivity is to be determined subjected to bounds.

 The bounds are given by

 -100<=x<100 and 

-100<=y<=100 (say).

 I am using Sum of Squares (SOS) toolbox in YALMIP to find positivity of P(x,y).

I followed the tutorial given in http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.SumOfSquares

 g = [ 100 - x;

      -100 + x;

       100 - y;

      -100 + y];

sdpvar s1 s2 s3 s4

          

F = [sos(pxy_12-[s1 s2 s3 s4]*g), s1>=0,s2>=0,s3>=0,s4>=0];

options = sdpsettings('sos.postprocess',1,'solver','sdpt3');

solvesos(F,[],options,[s1;s2;s3;s4]);

s1 = double(s1)

s2 = double(s2)

s3 = double(s3)

s4 = double(s4)

When I solve, i get all s1,s2,s3 and s4 positive. It means I obtain certificate of P(x,y) is positive in the given bounds. I have a doubt. Is using s1,s2,s3,s4 as constants instead of polynomials (as in example) make quite deiffernt ? Sometimes I used to get feasiblity by increasing the order of s1,..,s4.

 

When I read http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Blog.Strictly-feasible-SOS-solutions, the certificate which I obtain from above might not be 

true one. Is there any alternative way without calculating lower bounds as shown in the previous link?

The range of s1,s2,s3 and s4 are quite different for sedumi and sdpt3. For sdpt3 they are in range of 10^2 and for sedumi they are in range of 10^5.

Is that quite normal for these solvers ?

Thank You Very Much,

Best Regards,

Suman

[Johan Löfberg]

I don't understand your question/issue.

Using constant multiplier is the easiest, but also most conservative approach. If it fails, you try higher order multipliers. In theory they are stronger, but you might run into numerical problems etc of course.

You talk about an alternative. Alternative for doing what? If you want to prove non-negativity of a polynomial, using sum-of-squares, on a region, you most often use the proposed approach using multipliers. An alternative is to perform a variable change such that an interval is mapped onto R^n.For instance, if -1<= x<=1 you write x as 2z/(1+z^2) and rewrite everything (remove denominator)  so you get a polynomial condition

The fact that you get the values of order 10^5 indicates something is fishy in my opinion. Easiest if you give us your complete example

[SRB]

Thank you very much for the reply. It helps to clear my doubts regarding the multipliers.

Sorry for mistake about the range. 10^5 is the range obtained from SOSTOOLS. Probably they might have bugs.

The next problem I have is about certificate of feasibility regarding different solvers. The problem which I have attached  is feasible using sdpt3 (v 3.02) but in-feasible with sedumi 1.01. Is sdpt3 is better solver than sedumi ? 

I have attached problem with this post.  

Thank You.

[Johan Löfberg]

Why are you using such old versions of the solvers?

Anyway, I tested with sedumi,sdpt3 and mosek, and they all yield roughly the same results. However, you will never be able to solve this without issues, since your polynomial has very small coefficients, not much larger than the typical tolerances used in a numerical solver. More over, I suspect your problem isn't strictly feasible which can lead to problems (and the fact that it is essentially impossible to generate an absolutely correct certificate of polynomial, you will always have some error)

[SRB]

Thank you very much for clearing all my doubts. I am using old versions because of the compatibility issues of other toolbox with sedumi. I'll look with new version of solvers. Hope they work with my problem.