Monomials in SOS

[Yan Wang]

Hi,

Recently, I am studying using SOS to check the positive definiteness of a 4th-order multivariate polynomial with x1 x2 z1 z2 z3 z4 z5 as the independent variables. The codes I used are shown below. The problem is in the polynomial only a few 4th order terms, which are x1^2*z1*z2, x1*x2*z1^2, x2^2*z2*z3, x2^2*z3*z4, appear. For the 3rd order terms, I have the similar situation. But the command "monolist" produces all the possible monomials with degree 4, which will result in the dimension of the matrix Q very large and very sparse and the computational speed is extremely slow. I wonder if there is some way to put some constraints on the monomials used in the SOS programming.

v = monolist([x1 x2 z1 z2 z3 z4 z5],4);

Q = sdpvar(length(v));

Poly_sos = v'*Q*v;

%*************** Solve SOS Problem ***************%

F = [coefficients(Poly-Poly_sos,[x1 x2 z1 z2 z3 z4 z5]) == 0, Q >= 0];

[Johan Löfberg]

Why don't you use the built-in SOS solver to begin with, to see if it generates a decomposition with smaller number of monomials when addressing your polynomial? (it uses Newton polytopes and symmetry reductions, it can make a massive difference on some polynomials)

[Yan Wang]

Hi Lofberg,

Thank a lot!