solvesos

solvesos computes sum-of-squares decompositions.

Syntax

[sol,u,Q] = solvesos(Constraints,Objective,options,decisionvariables)

Examples

In its most simple form, solvesos takes a sos constrained polynomial and calculates a sum-of-squares decomposition.

x = sdpvar(1,1);
p = x^4+x+5;
F = [sos(p)];
sol = solvesos(F);
if sol.problem == 0
 disp('Sum-of-squares decomposition possible!);
end

If you are not interested in the used monomials \(u(x)\) and the Gramian \(Q\) available from solvesos in the second and third output, and the parameters in the problem are obvious from the constraints and the objective (see below), you can simply use optimize instead, and solvesos will be called automatically

x = sdpvar(1,1);
p = x^4+x+5;
F = [sos(p)];
optimize(F);

The sum-of-squares decomposition gives \(p(x) = u^T(x)Qu(x)=v^T(x)v(x)\). The computed decomposition \(v(x)\) can be recovered using the command sosd.

v = sosd(F);
sdisplay(p-v'*v)
ans =
    '-1.7764e-015+7.7716e-016x-1.1102e-015x^4'

Alternatively,

[sol,u,Q] = solvesos(F);
sdisplay(p-u{1}'*Q{1}*u{1})
ans =
    '-1.7764e-015+7.7716e-016x-1.1102e-015x^4'

Obviously, not entirely correct. However the coefficients are small and most likely due to numerical inaccuracy. Remove all terms with coefficients smaller than 1e-6 using the command clean.

sdisplay(clean(p-u{1}'*Q{1}*u{1},1e-6))
ans =
    '0'

Parametrized sum-of-squares problems are also possible. As an example, a lower bound on the global minimum of \(p(x)\) is obtained by finding a decomposition of \(p(x)-t\), while maximizing \(t\)

t = sdpvar(1,1);
F = [sos(p-t)];
solvesos(F,-t,[],t);
value(t)
ans =
    4.5275

Parametric variables (the last argument in the code above) are automatically detected if they are part of the objective function or part of non-SOS constraints. Hence, the problem above can be simplified (it is however recommended that you keep track of all decision variables and explicitly tell YALMIP which they are)

t = sdpvar(1,1);
F = [sos(p-t)];
optimize(F,-t);
value(t)
ans =
    4.5275

There is a large number of additional features in YALMIPs sum-of-squares module. To learn more check out the sum-of-squares tutorial.

Leave a Comment