spot_manual.tex

\documentclass[12pt]{article} 
\usepackage{amsmath} % assumes amsmath package installed
\usepackage{amssymb}  % assumes amsmath package installed
\usepackage{amsfonts}
\usepackage{graphicx}

\title{
SPOT\\ (Systems Polynomial Optimization Tools)\\ Manual
}


\author{Alexandre Megretski$\ ^\dagger$% 
\thanks{$\ ^\dagger$LIDS, EECS, MIT,
        {\tt\small ameg@mit.edu}}%
}


\newtheorem{thm}{Theorem}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem{lem}{Lemma}
\newcounter{remark}
\newcounter{example}

\newenvironment{rmk}{\addtocounter{remark}{1}\smallbreak\noindent
  {\bf Remark \theremark}}{\hfill$\Box$\smallbreak}
\newenvironment{exmp}{\refstepcounter{example}\smallbreak\noindent
  {\bf Example \theexample .}}{\hfill$\Box$\smallbreak}
\newenvironment{dfn}{\smallbreak\noindent{\bf 
Definition.} }{\hfill$\Box$\smallbreak}
\newenvironment{pf}{\smallbreak\noindent{\it Proof. }}{\hfill$\Box$\smallbreak}
\newenvironment{pf*}[1]{\smallbreak\noindent{\it #1}}{\hfill$\Box$\smallbreak}

\makeatother
\ifx\Box\undefined
  \makeatletter\input{oldlfont.sty} \makeatother
\fi


\newcommand{\bb}[1]{\mbox{{\boldmath$#1$\unboldmath}}}
\newcommand{\bbo}[1]{\mbox{\rm{\bf #1}}}
\newcommand{\cs}{\mbox{\rm const}\cdot}
\newcommand{\rf}[1]{(\ref{#1})}
\newcommand{\cl}[1]{{\cal #1}}
\newcommand{\hh}[1]{\breve{#1}}
\newcommand{\col}{\mbox{\rm col}}
\newcommand{\tx}[1]{\mbox{\rm{#1}}}
\newcommand{\tre}[1]{2\mbox{\rm{Re}}\{#1\}}
\newcommand{\rre}[1]{\mbox{\rm{Re}}\{#1\}}
\def\Box{\hbox{\hskip 1pt \vrule width 8pt height 6pt depth 1.5pt
  \hskip 1pt}}

\renewcommand{\a}{\alpha}
\renewcommand{\b}{\beta}
\newcommand{\e}{\epsilon}
\newcommand{\g}{\gamma}
\newcommand{\Ga}{\Gamma}
\renewcommand{\d}{\delta}
\newcommand{\D}{\Delta}
\newcommand{\ka}{\kappa}
\newcommand{\w}{\omega}
\newcommand{\G}{\Gamma}

\newcommand{\Wo}{\Omega}
\newcommand{\W}{\Omega}
\renewcommand{\r}{\rho}
\renewcommand{\t}{\theta}
\newcommand{\Th}{\Theta}
\newcommand{\s}{\sigma}
\renewcommand{\S}{\Sigma}
\newcommand{\n}{\nabla}
\renewcommand{\L}{\Lambda}

\newcommand{\EQ}[2]{\begin{equation}\label{#1}#2\end{equation}}
\newcommand{\AR}[2]{\left[\begin{array}{#1}#2\end{array}\right]}
\newcommand{\ARR}[2]{\begin{array}{#1}#2\end{array}}
\newcommand{\OR}[2]{\left\{\begin{array}{#1}#2\end{array}\right.}
\newcommand{\NI}{\noindent}
\newcommand{\SK}{\vskip5mm}
\newcommand{\HD}[2]{\SK\NI{\bf #1.}\ \ #2\SK}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\sat}{\mbox{{\rm sat}}}
\newcommand{\sgn}{\mbox{{\rm sgn}}}
\newcommand{\dzn}{\mbox{{\rm dzn}}}
\newcommand{\dom}{\mbox{{\rm Dom}}}
\newcommand{\wto}{\to^*}
\newcommand{\LL}[2]{L_{#1}^{#2}}
\renewcommand{\sp}[2]{\langle #1,#2\rangle}
\newcommand{\rank}{\mbox{{\rm rank{\ }}}}
\newcommand{\sys}[4]{\left(\begin{array}{c|c}#1&#2\\ \hline #3&#4
\end{array}\right)}
\newcommand{\EPS}[4]{
\begin{center}
\resizebox{#2cm}{#3cm}{\rotatebox{#4}{\includegraphics{#1.eps}}}
\end{center}
}

\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}



\begin{document}



\maketitle
\thispagestyle{empty}
\pagestyle{empty}


SPOT (Systems Polynomial Optimization Tools) 
is a MATLAB toolbox written as an alternative
implementation of SOSTools to be used in 
implementing a class of 
nonlinear system identification algorithms. 
It was tested with {\tt MATLAB 7.8.0}
(R2009a).
SPOT provides its own matrix multivariable polynomial variable
class {\tt msspoly} for handling elementary polynomial operations, 
a special class {\tt mssprog} for defining convex optimization problems
(to be solved by {\tt SeDuMi}) in terms 
of polynomial identities and self-dual cones, 
and a set of
functions for identification of linear and nonlinear dynamical systems.

\section{Installation}
POT is distributed in the form of 
compressed archives {\tt spotDDMMYY.zip},
where {\tt DDMMYY} indicates the date of release (for example,
{\tt pot110110.zip} was released on January 11, 2010).

Create directory {\tt spot} and extract {\tt spotDDMMYY.zip} into it. 
Start MATLAB, and run {\tt spot\_install.m} from the {\tt pot}
directory. The script sets the path for POT, and compiles some binaries:
\begin{verbatim}
>> spot_install

 Installing SPOT in C:\home\matlab\spot:
 updating the path...
 compiling the binaries...
 Done.
>> 
\end{verbatim}

Once SPOT is installed, you can check that it works by running
{\tt spot\_chk.m}:
\begin{verbatim}
>> spot_chk
\end{verbatim}




\section{Multivariable Polynomials}
The {\tt @msspoly} environment handles matrix polynomials in multiple variables.
Individual variables in {\tt @msspoly} have identifiers which begin with a 
{\sl single} character, which may be followed by a non-negative integer number.
While, in principle, a variable identifier can begin with
any MATLAB-recognized character, the only ones which are safe to use in applications
are the 52 Latin alphabet letters
\begin{verbatim}
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
\end{verbatim}
Other characters can be used for automated variable definitions. For example,
in the {\tt mssprog} environment (used to define convex optimization programs
in terms of polynomial equations which are linear with respect to the optimized
({\sl decision}) variables, but have arbitrary dependence on other ({\sl abstract})
variables,
the identifiers beginning with a ``{\tt @}'' are reserved for hidden decision
variables, while the identifiers  beginning with a ``{\tt \#}'' are reserved for 
hidden abstract variables.

\subsection{Defining {\tt @msspoly} Variables}
Use {\tt msspoly.m}:
\begin{verbatim}
>> f=msspoly('v')

[    v  ]
\end{verbatim}
defines {\tt xx} as an {\tt @msspoly} polynomial {\tt f}$=f: f(v)=v$.
{\tt g=msspoly('v',k)} where {\tt k} is a positive integer
will define a {\tt k}-by-1 vector of different variables, as in
\begin{verbatim}
>> g=msspoly('t',3)

[   t0  ]
[   t1  ]
[   t2  ]
\end{verbatim}
Using {\tt g=msspoly('v',[a b])} prodices a vector of {\tt a} variables with indexing
starting with {\tt b}, as in
\begin{verbatim}
>> g=msspoly('A',[2 1])

[   A1  ]
[   A2  ]
\end{verbatim}


\subsection{``Free'' and ``Simple'' {\tt @msspoly} Variables}
An {\tt @msspoly} variable is called {\sl free} if it is a matrix of
independent scalar variables. An {\tt @msspoly} variable is called {\sl simple} 
if it is a column of
independent scalar variables and constants. For example, in 
\begin{verbatim}
>> f1=msspoly('x',7);
>> f2=f1(1:6);
>> f3=reshape(f1,3,2);
>> f4=[f2;f2;1];
>> f5=f1*f1';
\end{verbatim}
the resulting free variables are {\tt f1}, {\tt f2}, {\tt f3}, 
the simple variables are
{\tt f1}, {\tt f2}, {\tt f3}, {\tt f4}, while {\tt f5} is not free and not simple.



\subsection{Handling {\tt @msspoly} Variables}
A number of functions of the {\tt @msspoly} environment have the
standard meaning:
\begin{itemize}
\item {\tt ctranspose.m} (as in {\tt z=x'})
\item {\tt horzcat.m} (as in {\tt z=[x y]})
\item {\tt minus.m} (as in {\tt z=x-y})
\item {\tt mtimes.m} (as in {\tt z=x*y})
\item {\tt plus.m} (as in {\tt z=x+y})
\item {\tt uminus.m} (as in {\tt z=-x})
\item {\tt uplus.m} (as in {\tt z=+x})
\item {\tt vertcat.m} (as in {\tt z=[x;y]})
\item {\tt subsasgn.m} (as in {\tt x(2)=y})
\item {\tt reshape.m}
\item {\tt isempty.m}
\item {\tt isscalar.m}
\item {\tt length.m}
\item {\tt repmat.m}
\item {\tt size.m}
\item {\tt sum.m}
\end{itemize}
Other functions are close to their expected definitions, with minor
modifications or restrictions:
\begin{itemize}
\item {\tt decomp.m}: decomposes an {\tt @msspoly} variable into a vector of its
free variables, and matrices of degrees and coefficients of its terms;
\item {\tt deg.m}: gives the a single number degree; can be used with a second
argument, which must be a {\sl free} {\tt @msspoly} variable, in which case the
degree with respect to the independent variables listed in the second argument
is computed;
\item {\tt diag.m}: produces a diagonal {\tt @msspoly} matrix when the input is a row
or a column; otherwise extracts the diagonal as a column vector;
\item {\tt diff.m}: the second (required) and third (optional) arguments
must be free {\tt @msspoly}
variables; with two arguments, the first argument must be a column, and
the result is the matrix of the partial derivatives of the first
argument  with respect to the second; with three 
arguments, the first argument can have arbitrary dimensions,
and the result is the derivative of the first
argument  with respect to the second in the direction provided by the third;
\item {\tt double.m}: converts a constant {\tt @msspoly} to {\tt double},
otherwise returns character '?';
\item {\tt isfunction.m}: the second argument must be a free {\tt @msspoly};
true iff the firts argument is a function of the second;
\item {\tt mono.m}: produces column vector of all monomials from the argument;
\item {\tt mpower.m} (as in {\tt z=x\^{}y}): argument
{\tt y} must be a non-negative integer;
\item {\tt mrdivide.m} (as in {\tt z=x/y}): argument
{\tt y} must be a non-singular {\tt double};
\item {\tt newton.m}: applies Newton method iterations to try to solve
approximately systems of polynomial equations;
\item {\tt recomp.m}: the inverse of {\tt decomp.m};
\item {\tt subs.m}: a restricted substitution routine, allows to replace,
in the first argument,
the independent variables from the second argument 
(must be a {\sl free} {\tt @msspoly})
by the corresponding components of the third argument (must be a 
{\sl simple}  {\tt @msspoly});
\item {\tt subsref.m} (as in {\tt z=x(1:2)} or {\tt z=x.n}): for the first type
of call, works as expected; for the second, {\tt x.m} and {\tt x.n} return
the dimensions, while {\tt x.s} returns the internal {\tt @msspoly} structure 
of {\tt x} (something that only a developer of new {\tt @msspoly} code would need);
\item {\tt trace.m}: the usual sum of the diagonal elements,
but non-square arguments are admissible, too.
\end{itemize}

\section{MSS Programs}

MSS stands for ``Modified Sums of Squares''\footnote{or for ``Meager Sums of Squares'',
``Magnificent Sums of Squares'', etc., just not ``Alternative Sums of Squares'',
though that's what it is. }
The {\tt @mssprog} environment allows its user to define 
matrix decision variables ranging over certain convex sets which are, in {\tt SeDuMi}
terminology, self-dual cones, to impose linear constraints in terms of polynomial
identities, to call {\tt SeDuMi} to optimize the decision variables, and to
extract the resulting optimal values.

\subsection{{\tt @mssprog} Operations}
To initialize a blanc MSS program, use {\tt mssprog.m}, as in
\begin{verbatim}
pr=mssprog;
\end{verbatim}
The most straightforward way of adding items to an MSS program is by using the
{\tt '.'} subsassignments:
\begin{itemize}
\item {\tt pr.free=x} registers the elements of {\tt x} as free ({\tt SeDuMi}-style) decision
variables ({\tt x} must be a {\sl free} {\tt @msspoly});
\item {\tt pr.pos=x} registers the elements of {\tt x} as positive ({\tt SeDuMi}-style) decision
variables ({\tt x} must be a {\sl free} {\tt @msspoly});
\item {\tt pr.lor=x} registers the columns of {\tt x} as Lorentz cone ({\tt SeDuMi}-style) decision
variables ({\tt x} must be a {\sl free} {\tt @msspoly} with at least two rows);
\item {\tt pr.rlor=x} registers the columns of {\tt x} as rotated Lorentz cone 
({\tt SeDuMi}-style) decision
variables ({\tt x} must be a {\sl free} {\tt @msspoly} with at least three rows);
\item {\tt pr.psd=x} registers the elements of every  column of
{\tt x} as the components of positive semidefinite ({\tt SeDuMi}-style) decision
variables ({\tt x} must be a {\sl free} {\tt @msspoly} with {\tt nchoosek(m+1,2)}
rows to generate an {\tt m}-by-{\tt m} symmetric matrix: use
{\tt y=mss\_v2s(x(:,k)} to re-shape the {\tt k}-th column
of {\tt x} into the corresponding symmetric matrix);
\item {\tt pr.eq=x} registers equality {\tt x==0} with MSS program {\tt pr}
({\tt x} must be an {\tt @msspoly} which is linear with respect to the vector
of all independent variables which are registered with {\tt pr} as decision
parameters);
\item {\tt pr.sos=x} registers the constraint that
all scalar components of x must be sums of squares of polynomials
({\tt x} must be an {\tt @msspoly} which is linear with respect to the vector
of all independent variables which are registered with {\tt pr} as decision
parameters);
\item {\tt pr.sss=x} registers the constraint that
all {\tt u'*x*u}, where \newline 
{\tt u=msspoly('\#',size(x,1))}, must be a sum of squares
({\tt x} must be a square-sized {\tt @msspoly} which is linear 
with respect to the vector
of all independent variables which are registered with {\tt pr} as decision
parameters);
\item {\tt pr.sedumi=r} calls {\tt SeDuMi} to find the values of the decision
variables which minimize {\tt r} ({\tt r} must be a scalar {\tt @msspoly} 
which is a linear function of the decision parameters).
\end{itemize}
To extract the optimized polynomials, use the {\tt '()'} subsreferencing:
\begin{itemize}
\item {\tt y=pr(x)}: {\tt y} is the result of substituting the optimized values
of decision variables into {\tt @msspoly} x;
\item {\tt y=pr(\{x\})}: same as {\tt double(pr(x))}.
\end{itemize}

For example, the following code (contained in {\tt mss\_test3.m})
finds the minimal value of $r$ for which
the polynomial $4x^4y^6+rx^2-xy^2+y^2$ is a sum of squares:
\begin{verbatim}
x=msspoly('x');                      % define the variables
y=msspoly('y');
r=msspoly('r');
q=4*(x^4)*(y^6)+r*(x^2)-x*(y^2)+y^2; % the SOS polynomial
pr=mssprog;                          % initialize MSS program
pr.free=r;                           % register r as free
pr.sos=q;                            % register sos constraint
pr.sedumi=r;                         % minimize r
pr({r})                              % get the optimal r
\end{verbatim}


\section{System Identification}
Functions from the {\tt nlid} directory are designed to help solving
nonlinear system identification problems. 
Functions from the {\tt nlid} directory treat the linear time invariant (LTI)
case.

\subsection{Identification of Symmetric Passive Transfer Matrices}
Function {\tt ltid\_passive.m} is a user interface to a number of
algorithms to aid in converting frequency samples of a 
marginally stable symmetric transfer
matrix (such as impedance of a passive circuit)
to a reduced order state space model.



\subsection{Nonlinear System Identification}
Currently, the following examples from the {\tt nlid} directory appear to work:
\begin{itemize}
\item {\tt nlid\_io\_lti\_old\_test1.m}: LTI system identification with
POT;
\item {\tt nlid\_miso0\_test1.m}: memoryless NL system identification;
\item {\tt nlid\_fl\_test1.m}: more powerful memoryless NL system identification.
\end{itemize}

\end{document}