SMRSOFT

Citation
G. Chesi. SMRSOFT: a Matlab Toolbox for Optimization over Polynomials and Dynamical Systems Study via SOS Programming. Available at http://www.eee.hku.hk/~chesi

Abstract
SMRSOFT is a Matlab toolbox for solving basic optimization problems over polynomials and studying dynamical systems via SOS programming. The main functions currently available in SMRSOFT are based on the techniques described in the book

G. Chesi. Domain of Attraction: Analysis and Control via SOS Programming. Springer, 2011

Download
SMRSOFT version 1.2 (with guide and examples)

Software requirements
SMRSOFT requires SeDuMi (tested with SeDuMi version 1.3)

Bugs
The search for optimal polynomial LFs does not work if the equilibrium point is not the origin (thanks to Eduardo Sontag for noticing this problem)

Functions currently available

SMRSOFT version 1.2 includes the following functions:

• smrda: computes a lower bound of the largest estimate of the domain of attraction (LEDA) of an equilibrium point of a polynomial system for a given polynomial Lyapunov function (LF), verifies the tightness of the found lower bound, searches for optimal polynomial LFs maximizing the size of the LEDA, computes a polynomial output controller for enlarging the LEDA, and plots the found results in the case of second or third order polynomial systems
   

• smropt: computes a lower bound of the minimum of a rational function with unconstrained variables or variables constrained over a semialgebraic set, and verifies the tightness of the found lower bound

• smrplot: plots a level set of a polynomial in two or three dimensions
   

• smrprint: prints a polynomial, vector polynomial or matrix polynomial
   

• smrsos: computes the SOS index or the generalized SOS index of a polynomial or a matrix polynomial (which measures how SOS or ratio of two SOS polynomials is a polynomial), and allows one to establish whether a polynomial or matrix polynomial is positive or non-positive with unconstrained variables or variables constrained over a semialgebraic set.
   

• smrsps: determines the solutions of a system of polynomial equations and inequalities.
   

Some illustrative examples

% computing the SOS index for Motzkin polynomial
%
% f(x)=1-3x1^2x2^2+x1^4x2^2+x1^2x2^4
%
% Motzkin polynomial is a PNS polynomial (nonnegative but not SOS)
% clearly, we find that the SOS index is negative

>> f='1-3x1^2x2^2+x1^4x2^2+x1^2x2^4';
>> smrsos(f);

SOS index (k=0):
  ind=-0.00638


% computing the generalized SOS index (case k=1) for Motzkin polynomial
% we find that the generalized SOS index is 0 (+/- solver precision)
% i.e. Motzkin polynomial is the ratio of two SOS polynomials
% (the denominator has degree 2k=2)

>> k=1;
>> f='1-3x1^2x2^2+x1^4x2^2+x1^2x2^4';
>> smrsos(f,k);

SOS index (k=1):
  ind=-5.593e-010
 

% establishing whether the following polynomial is non-positive:
%
% f(x)=3.3-2x1+3x2-x1x2+x1^2x2-x1x2^3+x1^3x2^2+x1^6+x2^6
%
% we find that f(x)<0 for some x (point in M), and hence f(x) is non-positive

>> f='3.3-2x1+3x2-x1x2+x1^2x2-x1x2^3+x1^3x2^2+x1^6+x2^6';
>> smrsos(f);

SOS index (k=0):
  ind=-5.787e-005
Points in set M:
  x=[-1.039,-1.144] -> f(x)=-0.001455
 

% establishing whether the (symmetric) matrix polynomial
%
% F(x)=[3+3x1^2-x1x2^2,-1+x1-2x2;
%       *,4+x1^4+x2^4]
%
% is positive over the semialgebraic set
%
% Theta={x: 4-x1^2>=0, 9-x2^2>=0, 1-x1x2+x1^3-2x2^2=0}
%
% we find that the generalized SOS index is positive, and hence F(x) is positive over Theta

>> F='[3+3x1^2-x1x2^2,-1+x1-2x2;4+x1^4+x2^4]';
>> a={'4-x1^2';'9-x2^2'};
>> b='1-x1x2+x1^3-2x2^2';
>> smrsos(F,[],a,b);

SOS index (k=0):
  ind=0.0003031
 

% determining the minimum of the rational function
%
% f(x)/g(x)=(7+x1x2^2+x1^4-x2^3)/(1+x2+x2^2)
%
% over the semialgebraic set
%
% Theta={x: 4-x1^2-2x2^2>=0, -1+x1^2+x1+x1x2+x2+x2^3=0}
%
% we obtain the lower bound bnd and we find that bnd is achieved
% by the rational function for some x in Theta (point in M)
% hence implying that bnd is tight

>> f='7+x1x2^2+x1^4-x2^3';
>> g='1+x2+x2^2';
>> a='4-x1^2-2x2^2';
>> b='-1+x1^2+x1+x1x2+x2+x2^3';
>> smropt(f,[],g,a,b);

Lower bound (k=0):
  bnd=1.913
Points in set M:
  x=[-0.8144,0.9891] -> f(x)/g(x)=1.913, min(a(x))=1.38, max(|b(x)|)=3.326e-005
 

% determining the solutions of the system of polynomial equations
%
% x1^4+x2^4+x3^4-1=0
% x1x2x3+x1^2+x2=0
% x1^2-x2^2-x3^2+x2x3-x1=0
%
% over the semialgebraic set
%
% Theta={x: x3>=0}
%
% we obtain one solution (point in set M)
% the accuracy of the solution is measured by the shown max(|f(x)|)
% the admissability of the solution is measured by the shown min(a(x))

>> f={'x1^4+x2^4+x3^4-1';'x1x2x3+x1^2+x2';'x1^2-x2^2-x3^2+x2x3-x1'};
>> a='x3';
>> smrsps(f,[],a);

scaled SOS index (k=0):
  snd=3.922e-009
Points in set M:
  x=[-0.7683,-0.886,0.4344] -> max(|f(x)|)=8.972e-005, min(a(x))=0.4344
 

% computing and plotting the LEDA of the origin of the Van der Pol
% system
%
% dot(x1)=x2
% dot(x2)=-x1-x2(1-x1^2)
%
% provided by the Lyapunov function
%
% v(x)=x1^2+x1x2+x2^2
%
% i.e. solving
%
% gamma = sup c s.t. dot(v)(x)<0 for all x in V(c)={x: v(x)<=c}\{0}
%
% we obtain the lower bound bnd of gamma
% moreover we find that for some x (points in M) one has
% dot(v)(x)=0 and v(x)=bnd hence implying that bnd is tight

>> f={'x2';'-x1-x2(1-x1^2)'};
>> v='x1^2+x1x2+x2^2';
>> [bnd,M,Dat]=smrda(f,[],v);
>> clf
>> smrda('plot',Dat)

LEDA lower bound (h=0):
  bnd=0.9152
Points in set M:
  x=[-0.8586,1.031] -> dot(v)(x)=-5.386e-006, v(x)=0.9152
  x=[0.8586,-1.031] -> dot(v)(x)=-5.386e-006, v(x)=0.9152