Numerical Examples

Polynomial Optimization

This is a classical use case of sum-of-squares programming. Given a polynomial, say, $f = x^4 + 10x$, we want to find the smallest value $\gamma$ that $f$ on $\mathbb R$ (more precisely, we want to find the largest lower bound). Equivalently, we could ask: What is the smallest value of $\gamma$ such that $f + \gamma$ is nonnegative on $\mathbb R$? If we replace "nonnegative" by [sum-of-squares polynomials], we obtain the optimization problem

$$ \min_\gamma \gamma \quad \text{s.t. $f + \gamma \in \Sigma[x]$} $$

This problem is convex in the decision variable $\gamma$, since the cost function is linear and the constraint "$f + \gamma \in \Sigma[x]$" is affine, and thus can be solved using sossol. To that extent, we create a struct sos with fields for the decision variable (sos.x = $\gamma$), objective (sos.f = $\gamma$), and constraint (sos.g = $f + \gamma$). We then specify that the decision variable is a free scalar variable (Kx.lin = 1) whereas the constraint is a scalar sum-of-squares polynomial (Kc.sos = 1). Upon creation of the solver object, CaΣoS rewrites the polynomial sum-of-squares problem above into a semidefinite program.

% Polynomial optimization.

% indeterminate variable
x = casos.Indeterminates('x');
% some polynomial
f = x^4 + 10*x;
% scalar decision variable
g = casos.PS.sym('g');

% define SOS problem:
%   min g s.t. (f + g) is SOS
sos = struct('x',g,'f',g,'g',f+g);
% constraint is scalar SOS cone
opts = struct('Kc',struct('sos',1));

% solve by relaxation to SDP
S = casos.sossol('S','sedumi',sos,opts);
% evaluate
sol = S();

fprintf('Minimum is %g.\n', full(sol.f))

Quasiconvex sum-of-squares programming

TODO: add example (ROA)