\chapter{A Tool for Control Design}
\label{chpt:SDP}

\section{Motivation}
Many control design problems  for linear and nonlinear systems can be formulated as {\it convex optimization} problems. To define a convex optimization problem, we need definitions of a convex set and a convex function.
\begin{defn} A set $\b{\Theta} \subseteq \mb{\Bb R}^n$ is convex if for any $\b x$ and $\b y$ in $\b{\Theta}$, the line segment between $\b x$ and $\b y$ lies in $\b{\Theta}$, that is,
\[
\alpha \b x + (1-\alpha)\b y \in \b{\Theta} \quad\mb{for any}\quad \alpha \in (0, 1).
\]
\end{defn}


Examples of convex sets include the empty set, $\mb{\Bb R}^n$, a subspace, a line, a line segment.


\begin{defn}
A real-valued function
\[
f: \Omega \to \mb{\Bb R}
\]
defined on a convex set $\b{\Theta} \subseteq \mb{\Bb R}^n$ is convex if for all $\b x,\b y \in \Omega$ and all $\alpha \in (0, 1)$,
\[
f(\alpha \b x + (1-\alpha)\b y) \le \alpha f(\b x) + (1-\alpha) f(\b y).
\]
\end{defn}

Thus a real-valued function on $n$ variables is convex over a convex set if for all $\b x,\b y \in \Omega$ the points on the line segment connecting $(\b x, f(\b x))$ and $(\b y, f(\b y))$ line on or above the graph of $f$. For more information on the subject of convex function, we recommend~\cite[Section~21.2]{chong08}.

A convex optimization problem is the one where the objective function to be minimized or maximized is convex and the constraint set, over which we optimize the objective function, is a convex set.


Semidefinite programming~(SDP) is a subfield of convex
optimization concerned with minimizing or maximizing a linear objective function
subject to a matrix inequality. The matrix inequality constraint
is convex and defines a convex feasible set over which the linear
objective function is being optimized. Semidefinite programming
can be viewed as an extension of linear programming, where the
componentwise inequalities on vectors are replaced by matrix
inequalities. For further reading on the subject of semidefinite
programming, we recommend an excellent survey paper by
Vandenberghe and Boyd~\cite{vandenberghe96}.

\section{Linear Matrix Inequality and Its Properties}
Consider $n+1$ real symmetric matrices
\[
\b F_i=\b F_i^{\top}\in \mb{\Bb R}^{m\times m},\;\; i=0,1,\ldots,n
\]
and a vector
\[
\b x=\left[\begin{array}{cccc} x_1&x_2&\cdots &x_n
\end{array}\right]^{\top}\in \mb{\Bb R}^n.
\]
Then,
\begin{eqnarray*}
\b F(\b x) &=& \b F_0+x_1\b F_1 + \ldots + x_n\b F_n\\
&=& \b F_0 + \sum_{i=1}^n x_i \b F_i
\end{eqnarray*}
is an affine function of $\b x$, rather than a linear function of
$\b x$ because $\b F(\b x)$ is composed of a linear term,
$\sum_{i=1}^n x_i \b F_i$, and a constant term, $\b F_0$.

Consider now an expression of the form
\[
\b F(\b x) = \b F_0+x_1\b F_1 + \cdots + x_n\b F_n > 0.
\]
The above is to be interpreted as follows: find a set of vectors
$\b x$ such that
\[
\b z^{\top}\b F(\b x)\b z > 0\;\;\mb{for all}\;\; \b z\in
\mb{\Bb R}^m,
\]
that is, $\b F(\b x)$ is positive definite. Recall that $\b
F_i$s are constant matrices, $\b x$ is unknown, and $\b F(\b x)=\b
F(\b x)^{\top}$ is an affine function $\b x$.

The expression, $\b
F(\b x) = \b F_0+x_1\b F_1 + \cdots + x_n\b F_n > 0$, is referred to
as in the literature as the {\emph{linear matrix inequality}}~(LMI)
although the term the {\emph affine matrix inequality} would be a
correct term to use.

It is easy to verify, see Exercise~\ref{ex:convex_set_pf}, that the set, $\{\b x:\b
F(\b x)> 0\}$, is a convex set.



A system of LMIs,
\[
\b F_1(\b x) > 0, \;\b F_2(\b x) > 0, \ldots, \b F_k(\b x) > 0,
\]
can be represented as one single LMI,
\[
\b F(\b x)=\left[\begin{array}{cccc} \b F_1(\b x)&{}& {}& {}\\
{}& \b F_2(\b x)&{}& {}\\
{}&{}&\ddots& {}\\
{} & {} & {} & \b F_k(\b x)
\end{array}\right] > 0.
\]
A linear matrix inequality, involving an $m$-by-$n$ constant
matrix $\b A$, of the form,
\[
\b A\b x < \b b
\]
can be represented as $m$ LMIs
\[
b_i-\b a_i^{\top}\b x > 0,\quad i=1,2,\ldots,m,
\]
where $\b a_i^{\top}$ is the $i$-th row of the matrix $\b A$. We
can view each scalar inequality as an LMI. We then represent $m$
LMIs as one LMI,
\[
\b F(\b x)=\left[\begin{array}{cccc} b_1-\b a_1^{\top}\b x&{}& {}& {}\\
{}& b_2-\b a_2^{\top}\b x&{}& {}\\
{}&{}&\ddots& {}\\
{} & {} & {} & b_m-\b a_m^{\top}\b x
\end{array}\right] > 0.
\]

With the above facts as a background, we can now give an example
of semidefinite programming,
\begin{eqnarray*}
\mb{minimize}&{}& \b c^{\top}\b x\\
\mb{subject to}&{}& \b F(\b x) > 0.
\end{eqnarray*}

The matrix property that we discuss next is useful when converting
some nonlinear matrix inequalities into linear inequalities. We
start with a simple observation. Let $\b P=\b P^{\top}$ be a nonsingular
$n$-by-$n$ matrix and let $\b x=\b M\b z$, where $\b M\in \mb{\Bb
R}^{n\times n}$ such that $\det \b M \ne 0$. Then, we have
\[
\b x^{\top}\b P\b x \ge 0\;\;\mb{if and only if}\;\; \b z^{\top}\b
M^{\top}\b P\b M\b z \ge 0,
\]
that is,
\[
\b P\ge 0 \;\;\mb{if and only if}\;\; \b M^{\top}\b P\b M \ge 0.
\]
Suppose that we have a square block matrix
\[
\left[\begin{array}{cc} \b A & \b B\\
\b B^{\top} & \b D
\end{array}\right].
\]
Then
\[
\left[\begin{array}{cc} \b A & \b B\\
\b B^{\top} & \b D
\end{array}\right]\ge 0\;\;\mb{if and only if}\;\; \left[\begin{array}{cc}
\b O & \b I\\
\b I & \b O
\end{array}\right]\left[\begin{array}{cc} \b A & \b B\\
\b B^{\top} & \b D
\end{array}\right]\left[\begin{array}{cc}
\b O & \b I\\
\b I & \b O
\end{array}\right]\ge 0,
\]
where $\b I$ is an identity matrix of appropriate dimension. In
other words,
\[
\left[\begin{array}{cc} \b A & \b B\\
\b B^{\top} & \b D
\end{array}\right]\ge 0\;\;\mb{if and only if}\;\; \left[\begin{array}{cc}\
\b D & \b B^{\top}\\
\b B & \b A
\end{array}\right]\ge 0.
\]
Consider now a square block matrix of the form
\[
\left[\begin{array}{cc} \b A_{11} & \b A_{12}\\
\b A_{21} & \b A_{22}
\end{array}\right],
\]
where $\b A_{11}$ and $\b A_{22}$ are square submatrices. Let us
now suppose that the matrix $\b A_{11}$ is invertible. Then we
have
\[
\left[\begin{array}{cc} \b A_{11} & \b A_{12}\\
\b A_{21} & \b A_{22}
\end{array}\right]=\left[\begin{array}{cc} \b I & \b O\\
\b A_{21}\b A_{11}^{-1}& \b I
\end{array}\right]\left[\begin{array}{cc} \b A_{11} & \b O\\
\b O & \b \Delta
\end{array}\right]\left[\begin{array}{cc} \b I & \b A_{11}^{-1}\b A_{12}\\
\b O & \b I
\end{array}\right],
\]
where
\[
\b \Delta=\b A_{22}-\b A_{21}\b A_{11}^{-1}\b A_{12}.
\]
The matrix $\b \Delta$ is called the Schur complement of $\b
A_{11}$. For the case when $\b A_{12}=\b A_{21}^{\top}$, we have
\[
\left[\begin{array}{cc} \b A_{11} & \b A_{21}^{\top}\\
\b A_{21} & \b A_{22}
\end{array}\right]=\left[\begin{array}{cc} \b I & \b O\\
\b A_{21}\b A_{11}^{-1}& \b I
\end{array}\right]\left[\begin{array}{cc} \b A_{11} & \b O\\
\b O & \b \Delta
\end{array}\right]\left[\begin{array}{cc} \b I & \b A_{11}^{-1}\b A_{21}^{\top}\\
\b O & \b I
\end{array}\right],
\]
where
\[
\b \Delta=\b A_{22}-\b A_{21}\b A_{11}^{-1}\b A_{21}^{\top}.
\]
Hence,
\[
\left[\begin{array}{cc} \b A_{11} & \b A_{21}^{\top}\\
\b A_{21} & \b A_{22}
\end{array}\right]>0\;\;\mb{if and only if}\;\;\left[\begin{array}{cc} \b A_{11} & \b O\\
\b O & \b \Delta
\end{array}\right]>0,
\]
that is,
\[
\left[\begin{array}{cc} \b A_{11} & \b A_{21}^{\top}\\
\b A_{21} & \b A_{22}
\end{array}\right]>0\;\;\mb{if and only if}\;\;\b
A_{11}>0\;\;\mb{and}\;\; \b \Delta >0.
\]

Many problems of optimization, control design, and signal
processing can be formulated in terms of LMIs. To test whether or
not there exist solutions $\b x$ to $\b F(\b x)>0$ is called a
feasibility problem. We say that the LMI is non-feasible if no
solution exists.


\begin{example}\rm
We present an example illustrating the LMI feasibility
problem. It is well known that a constant square matrix $\b A\in
\mb{\Bb R}^{n\times n}$ has its eigenvalues in the open left
half-complex plane if and only if for any real, symmetric,
positive definite $\b Q\in \mb{\Bb R}^{n\times n}$ the solution
$\b P=\b P^{\top}$ to the Lyapunov matrix equation
\[
\b A^{\top}\b P+\b P\b A=-\b Q,
\]
is positive definite. That is, real parts of the eigenvalues of
$\b A$ are all negative if and only if there exists a real
symmetric positive definite matrix $\b P$ such that
\[
\b A^{\top}\b P+\b P\b A<0,
\]
or equivalently,
\[
-\b A^{\top}\b P-\b P\b A>0.
\]
Thus, the location of all eigenvalues of $\b A$ in the open left
half-complex plane is equivalent to feasibility of the following
LMI,
\[
\left[\begin{array}{cc} \b P & \b O\\
\b O & -\b A^{\top}\b P-\b P\b A
\end{array}\right]>0,
\]
that is, the existence of a symmetric positive definite $\b P$
such that the above inequality holds.

We now show that finding $\b P=\b P^{\top}>0$ such that $\b
A^{\top}\b P+\b P\b A<0$ is indeed an LMI. For this let
\[
\b P=\left[\begin{array}{cccc} x_1 & x_2 & \cdots & x_n\\
x_2 & x_{n+1}& \cdots & x_{2n-1}\\
\vdots & {}& {}& \vdots\\
x_n & x_{2n-1} & \cdots & x_q
\end{array}\right],
\]
where
\[
q=\frac{n(n+1)}{2}.
\]
We next define the following matrices,
\[
\b P_1=\left[\begin{array}{ccccc} 1 & 0 & 0 &\cdots & 0\\
0 & 0 & 0 & \cdots & 0\\
0 & 0 & 0 & \cdots & 0\\
\vdots & {} & {}& {}& \vdots\\
0 & 0 & 0 & \cdots & 0
\end{array}\right],
\]
\[
\b P_2=\left[\begin{array}{ccccc} 0 & 1 & 0 &\cdots & 0\\
1 & 0 & 0 & \cdots & 0\\
0 & 0 & 0 & \cdots & 0\\
\vdots & {} & {}& {}& \vdots\\
0 & 0 & 0 & \cdots & 0
\end{array}\right],
\]
\[
\vdots
\]
\[
\b P_q=\left[\begin{array}{ccccc} 0 & 0 & 0 &\cdots & 0\\
0 & 0 & 0 & \cdots & 0\\
0 & 0 & 0 & \cdots & 0\\
\vdots & {} & {}& {}& \vdots\\
0 & 0 & 0 & \cdots & 1
\end{array}\right].
\]
Note that $\b P_i$ has only non-zero elements corresponding to $x_i$ in $\b P$. Let
\[
\b F_i=-\b A^{\top}\b P_i-\b P_i\b A,\quad i=1,2,\ldots, q.
\]
We then can write
\begin{eqnarray*}
\b A^{\top}\b P+\b P\b A &=& x_1\left(\b A^{\top}\b P_1+\b P_1\b A
\right)+x_2\left(\b A^{\top}\b P_2+\b P_2\b A \right)+\cdots
+x_q\left(\b A^{\top}\b P_q+\b P_q\b A \right)\\
&=&-x_1\b F_1-x_2\b F_2-\cdots -x_q\b F_q\\
&<& 0.
\end{eqnarray*}
Let
\[
\b F(\b x)=x_1\b F_1+x_2\b F_2+\cdots + x_q\b F_q,
\]
then
\[
\b P=\b P^{\top}>0\quad\mb{and}\quad \b A^{\top}\b P+\b P\b A<0
\]
if and only if
\[
\b F(\b x)>0.
\]
More examples of linear matrix inequalities in system and control
theory can be found in the book by Boyd et al.~\cite{boyd94}.
\end{example}
\markex

\section{LMI Solvers}
One can use MATLAB's toolbox to efficiently solve LMIs.  This toolbox has three types of LMI solvers that we discuss next.

\subsection{Solving the Feasibility Problem}

This solver computes a feasible solution, that is, is solves the feasible problem defined by a given system of LMI constraints. Using this solver, we can solve any system of LMIs of the form
\[
\b N^{\top}\b{\cal{L}}(\b X_1,\ldots,\b X_k)\b N<\b
M^{\top}\b{\cal{R}}(\b X_1,\ldots,\b X_k)\b M,
\]
where $\b X_1,\ldots, \b X_k$ are matrix variables, $\b N$ is the
left outer factor, $\b M$ is the right outer factor,
$\b{\cal{L}}(\b X_1,\ldots,\b X_k)$ is the left inner factor and
$\b{\cal{R}}(\b X_1,\ldots,\b X_k)$ is the right inner factor. The
matrices $\b{\cal{L}}(\cdot)$ and $\b{\cal{R}}(\cdot)$ are, in
general, symmetric block matrices. We note that the term
``left-hand side'' refers to what is on the ``smaller'' side of
the inequality $0<\b X$. Thus in $\b X>0$, the matrix $\b X$ is
still on the right-hand side because it is on the ``larger '' side
of the inequality.

We now provide a description of an approach that can be used to
solve the given LMI system feasibility problem. To initialize the
LMI system description, we type \verb!setlmis([])!. Then we
declare matrix variables using the command \verb!lmivar!. The
command \verb!lmiterm! allows us to specify LMIs that consitute
the LMI system under consideration. Next, we need to obtain an
internal representation using the command \verb!getlmis!. We next
compute a feasible solution to the given LMI system using the
command \verb!feasp!. After that we extract matrix variable values
with the command \verb!dec2mat!. In summary, a general structure
of a MATLAB program for finding a feasible solution to the set of
LMIs could have the form,
\begin{verbatim}
setlmis([])
lmivar
lmiterm
.
.
.
lmiterm
getlmis
feasp
dec2mat
\end{verbatim}
We now analyze the above commands in some detail so that the
reader can write simple MATLAB programs for solving LMIs after
finishing reading this section. First, to create a new
matrix-valued variable, say, $\b X$, in the given LMI system, we
use the command
\begin{verbatim}
X=lmivar(type,structure)
\end{verbatim}
The input \verb!type! specifies the structure of the varibale
\verb!X!. There may be three structures of matrix variables. When
\verb!type=1!, we have a symmetric block diagonal matrix variable.
The input \verb!type=1! refers to a full rectangular matrix
variable. Finally, \verb!type=3! refers to other cases. The second
input \verb!structure! gives additional information on te
structure of the matrix variable \verb!X!. For example the matrix
variable \verb!X! could have the form
\[
\b X=\left[\begin{array}{cccc} \b D_1 &\b O&\cdots &\b O\\
\b O & \b D_2 & \cdots & \b O\\
\vdots & {} &\ddots & \vdots\\
\b O & \b O & \cdots & \b D_r
\end{array}\right],
\]
where each $\b D_i$ is a square symmetric matrix. For the above
example we would use \verb!type=1!. The above matrix variable has
$r$ blocks. The input \verb!structure! is then an $r\times 2$
matrix whose $i$-th row describes the $i$-th block, where the
first component of each row gives the corresponding block size,
while the second element of each row specifies the block type. For
example,
\begin{verbatim}
X=lmivar(1,[3 1])
\end{verbatim}
specifies a full symmetric $3\times 3$ matrix variable. On the
other hand,
\begin{verbatim}
X=lmivar(2,[2 3])
\end{verbatim}
specifies a rectangular $2\times 3$ matrix variable. Finally, the
matrix variable $\b S$ of the form
\[
\b S=\left[\begin{array}{ccccc} s_1 & 0 & |& 0 & 0\\
0 & s_1 & |& 0 & 0\\
--&--&|&--&--\\
0 & 0 &| & s_2 & s_3\\
0 & 0 &| & s_3 & s_4
\end{array}\right],
\]
can be declared as follows:
\begin{verbatim}
S=lmivar(1,[2 0;2 1])
\end{verbatim}
Note that in the above the second component of the first row of
the second input has the value of zero, that is,
\verb!structure(1,2)=0!. This describes a scalr block matrix of
the form
\[
\b D_1=s_1 \b I_2.
\]
Note that the second block is a $2\times 2$ symmetric full block.

We next take a closer look at the next command whose purpose is to
specify the terms of the LMI system of interest. This command has
the form
\begin{verbatim}
lmiterm(termid,A,B,flag)
\end{verbatim}
We briefly descibe each of the four inputs of this command. The
first input, \verb!termid!, is a row with four elements that
specify the terms of each LMI of the LMI system. We have
\verb!termid(1)=n! to specify the left-hand side of the $n$-th
LMI. We use \verb!termid(1)=-n! to specify the right-hand side of
the $n$-th LMI. The middle two elements of the input \verb!termid!
specify the block location. Thus \verb!termid(2,3)=[i j]! refers
to the term that belongs to the $(i,j)$ block of the LMI specified
by the first component. Finally, \verb!termid(4)=0! for the
constant term, \verb!termid(4)=X! for the variable term in the
form $\b A\b X\b B$, while \verb!termid(4)=-X! for the variable
term in the form $\b A\b X^{\top}\b B$. The third and the fourth
inputs of the command \verb!lmiterm! give the values of the left
and right outer factors, that is, \verb!A! and \verb!B! give the
value of the constant outer factors in the variable terms, $\b A\b
X\b B$ or in $\b A\b X^{\top}\b B$. Finally the fourth input to
\verb!lmiterm! serves as a compact way to specify the expression
\[
\b A\b X\b B+(\b A\b X\b B)^{\top}.
\]
Thus \verb!flag='s'! can be used to denote a symmetrized
expression. We now illustrate the above command on the following
LMI,
\[
\b P\b A+(\b P\b A)^{\top}<0.
\]
We have one LMI with two terms. We could use the following
description of this single LMI,
\begin{verbatim}
lmiterm([1 1 1 P],1,A)
lmiterm([1 1 1 -P],A',1)
\end{verbatim}
On the other hand, we can compctly describe the above LMI with the
use of the \verb!flag! as follows,
\begin{verbatim}
lmiterm([1 1 1 P],1,A,'s')
\end{verbatim}
Now to solve the feasibility problem we could have typed
\begin{verbatim}
[tmin,xfeas]=feas(lmis)
\end{verbatim}
In general, for a given LMI feasibility problem of the form
\begin{eqnarray*}
\mb{find}&{}& \b x\\
\mb{such that}&{}& \b L(\b x) < \b R(\b x)
\end{eqnarray*}
the command \verb!feasp! solves the auxiliary convex problem
\begin{eqnarray*}
\mb{minimize}&{}& t\\
\mb{subject to}&{}& \b L(\b x)<\b R(\b x)+t\b I.
\end{eqnarray*}
The system of LMIs is feasible if the minimal $t$ is negative. We
add that the current value of $t$ is displayed by \verb!feasp! at
each iteration.

Finally we convert the output of the LMI solver into matrix
variables using the command
\begin{verbatim}
P=dec2mat(lmis,xfeas,P).
\end{verbatim}

\subsection{Minimization of a Linear Objective Under LMI Constraints}

This solver is invoked using the function \verb!mincx!. It solves the convex problem
\begin{eqnarray*}
\mb{minimize}&{}& \b c^{\top}\b x\\
\mb{subject to}&{}& \b A(\b x)<\b
B(\b x).
\end{eqnarray*}
The notation $\b A(\b x)<\b B(\b x)$ is a shorthand notation for general structured LMI systems.

Thus to solve a \verb!mincx! problem, in addition to specifying the LMI constraints as in the \verb!feasp! problem, we also declare the linear objective function. Then we invoke the function \verb!mincx!. We illustrate both the \verb!feasp! and  \verb!mincx! solvers in the following example.
\begin{example}\rm
We consider the optimization problem
\begin{eqnarray*}
\mb{minimize}&{}& \b c^{\top}\b x\\
\mb{subject to}&{}& \b A\b x \le \b b,
\end{eqnarray*}
where
\begin{eqnarray*}
\b c^{\top} &=& \left[\begin{array}{cc}
4 & 5
\end{array}\right],\\
\b A &=& \left[\begin{array}{cc}
1 & 1\\
1 & 3\\
2 & 1
\end{array}\right],\quad \b b=\left[\begin{array}{c}
8\\
18\\
14
\end{array}\right].
\end{eqnarray*}
We first solve the feasibility problem, that is, we find an $\b x$ such that $\b A\b x\le \b b$, using the \verb!feasp! solver. After that we solve the above minimization problem using the \verb!mincx! solver. A simple MATLAB code accomplishing the above tasks is shown below.
\begin{verbatim}
% Enter problem data
A =[1 1;1 3;2 1];
b=[8 18 14]';
c=[-4 -5]';
setlmis([]);
X=lmivar(2,[2 1]);
lmiterm([1 1 1 X],A(1,:),1);
lmiterm([1 1 1 0],-b(1));
lmiterm([1 2 2 X],A(2,:),1);
lmiterm([1 2 2 0],-b(2));
lmiterm([1 3 3 X],A(3,:),1);
lmiterm([1 3 3 0],-b(3));
lmis=getlmis;
%------------------------------------
disp('-------------feasp result---------------')
[tmin,xfeas]=feasp(lmis);
x_feasp=dec2mat(lmis,xfeas,X)
disp('-------------mincx result---------------')
[objective,x_mincx]=mincx(lmis,c,[0.0001 1000 0 0 1])
\end{verbatim}
\end{example}
The \verb!feasp! produces
\[
\b x_{feasp}=\left[\begin{array}{c}
-64.3996\\
-25.1712
\end{array}\right].
\]
The \verb!mincx! produces
\[
\b x_{mincx}=\left[\begin{array}{c}
3.0000\\
5.0000
\end{array}\right].
\]\markex

\subsection{Generalized Eigenvalue Minimization Problem}

This problem can be stated as
\[
\begin{array}{cccc}
\mb{minimize}& \lambda& {} &{}\\
\mb{subject to}&{}& {}&{}\\
{}& \b C(\b x)&<&\b D(\b x)\\
{}&  0 &<& \b B(\b x)\\
{} & \b A(\b x) &<& \lambda \b B(\b x).
\end{array}
\]
In the above, we need to distinguish between standard LMI constraints of the form $\b C(\b x)<\b D(\b x)$ and the linear-fractional LMIs of the form $\b A(\b x) < \lambda \b B(\b x)$ that are concerned with the generalized eigenvalue $\lambda$. For more information on this type of the LMI solver, we refer to the LMI Lab in the MATLAB's Robust Control Toolbox user's guide.

\section{Notes}

A quick introduction to the LMI toolbox is the tutorial that can be accessed by typing in \verb!lmidem!. It is very instructive and we recommend to try it.

We mention that in addition to the MATLAB's LMI Toolbox there is another toolbox for solving LMIs called LMITOOL, a built in software package in Scilab toolbox, developed at INRIA in France. Scilab offers free software for numerical optimization. There is a version of LMITOOL for MATLAB that can be uploaded from the website of the Scilab Consortium.

Yet Another LMI Package (YALMIP) for solving LMIs was developed in Switzerland in the Automatic Control Laboratory at ETH. YALMIP is an ``intuitive and flexible modelling language for solving optimization problems in MATLAB.''

\section{Exercises}
\begin{exercise}\label{ex:convex_set_pf}\rm
Show that the set
\[
\{\b x : \b F_0+x_1\b F_1 + \cdots + x_n\b F_n > 0 \}
\]
is convex.
\end{exercise}

\begin{exercise}\label{ex:first_SDP_exercise}\rm %Fin_Fall09 P5
Consider the following symmetric matrix,
\[
\b Q=\left[\begin{array}{cc|c}
2 & 2 & 1\\
2 & 3 & 1\\\hline
1 & 1 & 2\\
\end{array}\right]=\left[\begin{array}{c|c}
\b Q_{11} & \b Q_{12}\\\hline
\b Q_{21} & \b Q_{22}
\end{array}\right].
\]
\begin{itemize}
\item[{\bf (i)}] Compute the Schur complement, $\Delta_{11}$, of $\b Q_{11}$;

\item[{\bf (ii)}] Compute the Schur complement, $\Delta_{22}$, of $\b Q_{22}$.

\end{itemize}
\end{exercise}

\begin{exercise}\label{exer:dlyap}\rm
Use the Schur complement to show that solving the discrete Lyapunov matrix equation
\[
\b A^{\top}\b P\b A-\b P < 0
\]
for $\b P=\b P^{\top} >0$ is equivalent to solving the LMI,
\[
\left[\begin{array}{cc}
\b P & \b A^{\top}\b P\\
\b P\b A & \b P
\end{array}\right] > 0
\]
\end{exercise}

\begin{exercise}\label{ex:LMI_two_Lyaps}\rm %Fin_Fall09 P9
Write a MATLAB program that finds a positive definite $\b P$ such that
\begin{eqnarray*}
\b A_1^{\top}\b P+\b P\b A_1 &<& 0\\
\b A_2^{\top}\b P+\b P\b A_2 &<& 0,
\end{eqnarray*}
and
\[
\b P< 5 \b I_2,
\]
where
\[
\b A_1=\left[\begin{array}{cc}
-1 & 0\\
0 & -1
\end{array}\right]\quad\mb{and}\quad \b A_2=\left[\begin{array}{cc}
-2 & 0\\
1 & -1
\end{array}\right].
\]
\end{exercise}

\begin{exercise}\label{exer:infeasible_two_mats}\rm It is known, see Example~\ref{ex:infeasp_two_mats}, that for the matrices
\[
\b A_1=\left[\begin{array}{cc}
-1 & 4\\
0 & -2
\end{array}\right], \quad \b A_2=\left[\begin{array}{cc}
-1 & 0\\
4 & -2
\end{array}\right]
\]
there is no common positive definite $\b P$ such that $\b A_i^{\top}\b P+\b P\b A_i<0$ for $i=1,2$, that is, there is no $\b P=\b P^{\top}>0$ such that
\[
\b A_1^{\top}\b P+\b P\b A_1 < 0\quad\mb{and}\quad \b A_2^{\top}\b P+\b P\b A_2 < 0.
\]
Verify this using LMIs.
\end{exercise}

\begin{exercise}\label{exer:infeasible_two_mats}\rm
Formulate LMIs that find a state feedback controller
\[
\b u= -\b K\b x
\]
that stabilizes each individual system for a family of linear systems,
\[
\dot{\b x} = \b A_i \b x + \b B_i \b u,\quad i=1,\ldots, N.
\]
One way to solve this is to formulate LMIs that solve the problem of finding $\b P=\b P^{\top}>0$ such that
\[
(\b A_i-\b B_i\b K)^{\top}\b P + \b P(\b A-\b B_i\b K) < 0, \quad i=1,\ldots , N .
\]

\end{exercise}