\documentclass{beamer}

\input{settings.tex}


\title{Semidefinite Programming, }
\subtitle{Computational Intelligence, Lecture 11}
\author{by <NAME>}
\centering
\date{\mydate}



\begin{document}
\maketitle


\begin{frame}{Content}

\begin{itemize}
\item  Semidefinite Programming (SDP)
\begin{itemize}
    \item General form
    \item Multiple LMI
    \item SDP decision variable
\end{itemize}
\item  Example 1:  Continuous Lyapunov equation as an SDP/LMI
\item  Example 2:  Discrete Lyapunov equation as an SDP/LMI
\item  Example 3:  LMI Controller design for continuous LTI
\item How to describe an ellipsoid
\item Volume of an ellipsoid
\item Inscribed ellipsoid algorithms
\item Homework
\end{itemize}
\end{frame}



\begin{frame}{Semidefinite Programming (SDP)}
\framesubtitle{General form}
\begin{flushleft}

General form of a semidefinite program is:

%
\begin{equation}
\begin{aligned}
& \underset{\mathbf{x}}{\text{minimize}}
& & \mathbf{c}^\top\mathbf{x}, \\
& \text{subject to}
& & \begin{cases}
    \mathbf{G} + \sum \mathbf{F}_i x_i \preceq 0, \\
    \mathbf{A}\mathbf{x} = \mathbf{b}.
    \end{cases}
\end{aligned}
\end{equation}

where $\mathbf{F}_i \succeq 0$ and $\mathbf{G} \succeq 0$ (meaning they are positive semidefinite).

\bigskip

Constraint $\mathbf{G} + \sum \mathbf{F}_i x_i \preceq 0$ is called \emph{linear matrix inequality} or \emph{LMI}.
 
\end{flushleft}
\end{frame}




\begin{frame}{Semidefinite Programming (SDP)}
\framesubtitle{Multiple LMI}
\begin{flushleft}

SDP can have several LMIs. Assume you have:

\begin{equation}
    \begin{cases}
        \mathbf{G} + \sum \mathbf{F}_i x_i \preceq 0 \\
        \mathbf{D} + \sum \mathbf{H}_i x_i \preceq 0
    \end{cases}
\end{equation}


This is equivalent to:

\begin{equation}
    \begin{bmatrix} 
            \mathbf{G} & \mathbf{0} \\
            \mathbf{0} & \mathbf{D}
    \end{bmatrix} +
    \sum
    \begin{bmatrix} 
            \mathbf{F}_i & \mathbf{0} \\
            \mathbf{0}   & \mathbf{H}_i
    \end{bmatrix}
    x_i \preceq 0
\end{equation}

\end{flushleft}
\end{frame}




\begin{frame}{Semidefinite Programming (SDP)}
\framesubtitle{SDP decision variable}
\begin{flushleft}

Sometimes it is easier to directly think of semidefinite matrices as of decision variables. This leads to programs with such formulation:
%
\begin{equation}
\begin{aligned}
& \underset{\mathbf{X}}{\text{minimize}}
& & f(\mathbf{X}), \\
& \text{subject to}
& & \begin{cases}
    \mathbf{X} \preceq 0, \\
    \mathbf{g}(\mathbf{X}) = \mathbf{0}.
    \end{cases}
\end{aligned}
\end{equation}

where cost and constraints should adhere to SDP limitations.

\end{flushleft}
\end{frame}



\begin{frame}{Ex. 1: Continuous Lyapunov eq. as SDP/LMI}
\framesubtitle{Mathematical formulation}
\begin{flushleft}

In control theory, Lyapunov equation is a condition of whether or not a continuous LTI system $\dot{\mathbf{x}} = \mathbf{A}\mathbf{x}$ is stable:

\begin{equation}
    \begin{cases}
        \mathbf{A}^\top\mathbf{P} + \mathbf{P}\mathbf{A}  \preceq -\mathbf{Q} \\
        \mathbf{P} \succeq 0
    \end{cases}
\end{equation}
%
where $\mathbf{Q} \succeq 0$ is a constant and decision variable is $\mathbf{P}$. This can be represented as an SDP:
%
\begin{equation}
\begin{aligned}
& \underset{\mathbf{P}}{\text{minimize}}
& & 0, \\
& \text{subject to}
& & \begin{cases}
    \mathbf{P} \succeq 0, \\
    \mathbf{A}^\top\mathbf{P} + \mathbf{P}\mathbf{A} + \mathbf{Q} \preceq 0.
    \end{cases}
\end{aligned}
\end{equation}


\end{flushleft}
\end{frame}




\begin{frame}{Ex. 1: Continuous Lyapunov eq. as SDP/LMI}
\framesubtitle{Code}
\begin{flushleft}

\input{code1}

\end{flushleft}
\end{frame}




\begin{frame}{Ex. 2: Discrete Lyapunov eq. as SDP/LMI}
\framesubtitle{Mathematical formulation}
\begin{flushleft}

In control theory, Discrete Lyapunov equation is a condition of whether or not a discrete LTI system $\mathbf{x}_{i+1} = \mathbf{A}\mathbf{x}_i$ is stabilizable:

\begin{equation}
    \begin{cases}
        \mathbf{A}^\top \mathbf{P}\mathbf{A} - \mathbf{P} + \mathbf{Q} \preceq 0 \\
        \mathbf{P} \succeq 0
    \end{cases}
\end{equation}
%
where $\mathbf{Q} \succeq 0$ is a constant and decision variable is $\mathbf{P}$. This can be represented as an SDP:
%
\begin{equation}
\begin{aligned}
& \underset{\mathbf{P}}{\text{minimize}}
& & 0, \\
& \text{subject to}
& & \begin{cases}
    \mathbf{P} \succeq 0, \\
    \mathbf{A}^\top \mathbf{P}\mathbf{A} - \mathbf{P} + \mathbf{Q} \preceq 0.
    \end{cases}
\end{aligned}
\end{equation}


\end{flushleft}
\end{frame}



\begin{frame}{Ex. 2: Discrete Lyapunov eq. as SDP/LMI}
\framesubtitle{Code}
\begin{flushleft}

\input{code2}

\end{flushleft}
\end{frame}





\begin{frame}{Ex. 3: Control design for CT-LTI}
\framesubtitle{Mathematical formulation}
\begin{flushleft}

For an LTI system of the form $\dot{\mathbf{x}} = \mathbf{A}\mathbf{x} + \mathbf{B}\mathbf{u}$ there is an LMI condition to determine if it can be stabilized:

\begin{equation}
    \begin{cases}
        \mathbf{A}\mathbf{P} + \mathbf{P}     \mathbf{A}^\top + \mathbf{B}\mathbf{L} + \mathbf{L}^\top\mathbf{B}^\top + \mathbf{Q} \preceq 0 \\
        \mathbf{P} \succeq 0
    \end{cases}
\end{equation}
%
where $\mathbf{Q} \succeq 0$ is a constant and decision variables are $\mathbf{P}$ and $\mathbf{L}$. 

\bigskip

This gives as a direct way to calculate linear feedback controller $\mathbf{u} = \mathbf{K}\mathbf{x}$ (note the sign!) gains:

\begin{equation}
    \mathbf{K} = \mathbf{L}\mathbf{P}^{-1}
\end{equation}

\end{flushleft}
\end{frame}




\begin{frame}{Ex. 3: Control design for CT-LTI, Code}
% \framesubtitle{Code}
\begin{flushleft}

\input{code3}

\end{flushleft}
\end{frame}






\begin{frame}{How to describe an ellipsoid}
\framesubtitle{Unit sphere transformation}
\begin{flushleft}

Let us first remember how we describe a unit sphere:

\begin{equation}
    \mathcal{S} = \{ \mathbf{x}: \ || \mathbf{x} || \leq 1 \}
\end{equation}

An ellipsoid can be seen as a linear transformation of a unit sphere: 

\begin{equation}
    \mathcal{E} = \{ \mathbf{A}\mathbf{x} + \mathbf{b}: \ || \mathbf{x} || \leq 1 \}
\end{equation}
 
\end{flushleft}
\end{frame}


\begin{frame}{How to describe an ellipsoid}
\framesubtitle{A dual description}
\begin{flushleft}

Let us introduce a change of variables $\mathbf{z} = \mathbf{A}\mathbf{x} + \mathbf{b}$. Assuming $\mathbf{A}$ is invertible, we get:

\begin{equation}
    \mathbf{x} = \mathbf{A}^{-1}(\mathbf{z} - \mathbf{b})
\end{equation}

So, we can describe the exact same ellipsoid using an alternative formula: 

\begin{equation}
    \mathcal{E} = \{ \mathbf{z}: \ || \mathbf{B}\mathbf{z} + \mathbf{c} || \leq 1 \}
\end{equation}
 
 where $\mathbf{B} = \mathbf{A}^{-1}$ and $\mathbf{c} = -\mathbf{A}^{-1}\mathbf{b}$.
 
\end{flushleft}
\end{frame}



\begin{frame}{Volume of an ellipsoid}
\framesubtitle{Part 1}
\begin{flushleft}

For an ellipsoid of the form

\begin{equation}
    \mathcal{E} = \{ \mathbf{A}\mathbf{x} + \mathbf{b}: \ || \mathbf{x} || \leq 1 \}
\end{equation}

the "bigger" the $\mathbf{A}$, the bigger the ellipsoid. This concept can be made concrete by talking about the determinant of $\mathbf{A}$.

\bigskip

Thus, maximizing the volume of this ellipsoid is the same as maximizing $\text{det}(\mathbf{A})$. Or, it is the same as \emph{minimizing} the $\text{det}(\mathbf{A}^{-1})$, since $\text{det}(\mathbf{A}^{-1}) = 1 / \text{det}(\mathbf{A})$.
 
\end{flushleft}
\end{frame}




\begin{frame}{Volume of an ellipsoid}
\framesubtitle{Part 2}
\begin{flushleft}

For an ellipsoid of the form

\begin{equation}
    \mathcal{E} = \{ \mathbf{z}: \ || \mathbf{B}\mathbf{z} + \mathbf{c} || \leq 1 \}
\end{equation}

the "bigger" the $\mathbf{B}$, the \emph{smaller} the ellipsoid. We can make it obvious by thinking that increasing $\mathbf{B}$ leaves less room for valid $\mathbf{z}$, and it is the volume of valid $\mathbf{z}$ that makes the volume of the ellipsoid in this case.

\bigskip

This concept can be made concrete by talking about the determinant of $\mathbf{B}$. Thus, maximizing the volume of this ellipsoid is the same as \emph{minimizing} $\text{det}(\mathbf{B})$. Or, it is the same as \emph{maximizing} the $\text{det}(\mathbf{B}^{-1})$.
 
\end{flushleft}
\end{frame}


\begin{frame}{Min volume bounding ellipsoid}
	\begin{flushleft}
		
		Consider the problem: given V-polytope, defined by its vertices $\bo{v}_i$, find minimum-volume ellipsoid $\mathcal{E}$ containing the polytope. We will start with defining the ellipsoid as $\mathcal{E} = \{ \mathbf{z}: \ || \mathbf{B}\mathbf{z} + \mathbf{c} || \leq 1 \}$. The ellipsoid is smaller when $|| \mathbf{B} ||$ is bigger, and thus we can write the minimization as minimizing $\text{det} (\mathbf{B}^{-1}) $.
		
\begin{equation}
	\begin{aligned}
		& \underset{\mathbf{B}, \bo{c}}{\text{minimize}}
		& & \text{log} (\text{det} (\mathbf{B}^{-1}) ), \\
		& \text{subject to}
		& & \begin{cases}
			\mathbf{B} \succeq 0, \\
			|| \mathbf{B} \bo{v}_i + \mathbf{c} || \leq 0.
		\end{cases}
	\end{aligned}
\end{equation}

The solution gives us L\"owner-John ellipsoid.
		
	\end{flushleft}
\end{frame}



\begin{frame}{Max volume inscribed ellipsoid, 1}
	\begin{flushleft}
		
		Consider the problem: given H-polytope, defined by its half-spaces $\bo{a}_i^\top \bo{x} \leq b_i$, find maximum-volume ellipsoid $\mathcal{E}$ contained in the polytope. We will start with defining the ellipsoid as $\mathcal{E} = \{ \bo{C}\bo{x} + \bo{d}: \ || \bo{x} || \leq 1 \}$. The ellipsoid is larger when $|| \mathbf{C} ||$ is bigger, and thus we can write the minimization as minimizing $\text{det} (\mathbf{C}^{-1}) $.
		
		\bigskip
		
		Let us write down the constraint requiring that $\mathcal{E}$ lies in the polytope. We know that $\bo{a}_i^\top (\bo{C}\bo{x} + \bo{d}) \leq b_i$ holds for all $|| \bo{x} || \leq 1$. The worst-case scenario is when $\bo{x}$ aligned with $\bo{a}_i^\top \bo{C}$ and has length 1:
		%
		\begin{equation}
			\bo{x} = \frac{\bo{a}_i^\top \bo{C}}{|| \bo{a}_i^\top \bo{C} ||}
		\end{equation}
	%
		Thus the constraint becomes
		%
		\begin{equation}
			 || \bo{a}_i^\top \bo{C} || + \bo{a}_i^\top\bo{d} \leq b_i
		\end{equation}
		
	\end{flushleft}
\end{frame}



\begin{frame}{Max volume inscribed ellipsoid, 2}
	\begin{flushleft}
		
		Here is the resulting problem:
		
		\begin{equation}
			\begin{aligned}
				& \underset{\mathbf{C}, \bo{d}}{\text{minimize}}
				& & \text{log} (\text{det} (\mathbf{C}^{-1}) ), \\
				& \text{subject to}
				& & \begin{cases}
					\mathbf{C} \succeq 0, \\
					|| \bo{a}_i^\top \bo{C} || + \bo{a}_i^\top\bo{d} \leq b_i.
				\end{cases}
			\end{aligned}
		\end{equation}
		
		The solution gives us inscribed (inner) L\"owner-John ellipsoid.
		
	\end{flushleft}
\end{frame}




%\begin{frame}{Inscribed ellipsoid algorithms}
%\begin{flushleft}
%
%Continue with slides from Convex Optimization — Boyd \& Vandenberghe. Follow the link:
%
%\bigskip
%
%\centerline{\href{https://see.stanford.edu/materials/lsocoee364a/08GeometricalProbs.pdf}{8. Geometric problems}}
%
%\end{flushleft}
%\end{frame}



\begin{frame}{Homework}
% \framesubtitle{Parameter estimation}
\begin{flushleft}


Implement both examples from page 2 of the \href{http://stanford.edu/class/ee363/notes/lmi-cvx.pdf}{LMI CVX documents}.

\end{flushleft}
\end{frame}





\begin{frame}
	\centerline{Lecture slides are available via Moodle.}
	\bigskip
	\centerline{You can help improve these slides at:}
	\centerline{
		\mygit
	}
	\bigskip
	
	\textcolor{black}{\qrcode[height=1.5in]{https://github.com/SergeiSa/Computational-Intelligence-Slides-Spring-2022}}
	\bigskip
	
	
	\centerline{Check Moodle for additional links, videos, textbook suggestions.}
\end{frame}




\begin{frame}{Appendix A}
%	\framesubtitle{Part 1}
	\begin{flushleft}
		
		Schur compliment. Given $\bo{M}$
		
		\begin{equation}
			\bo{M} = 
			\begin{bmatrix}
				\bo{A} & \bo{B} \\
				\bo{B}^\top & \bo{C}
			\end{bmatrix}
		\end{equation}
	
	with full-rank $\bo{A}$, we can make the following statements:
	
	\begin{itemize}
		\item $\bo{M} \succ 0$ iff $\bo{A} \succ 0$ and $\bo{C} - \bo{B}^\top\bo{A}^{-1}\bo{B} \succ 0$
		\item $\bo{A} \succ 0 \implies$ $\bo{M} \succeq 0$ iff $\bo{C} - \bo{B}^\top\bo{A}^{-1}\bo{B} \succeq 0$
	\end{itemize}

\bigskip

	If $\bo{C}$ is full-rank, we can make the following statements:
	
	\begin{itemize}
	\item $\bo{M} \succ 0$ iff $\bo{C} \succ 0$ and $\bo{A} - \bo{B}\bo{C}^{-1}\bo{B}^\top \succ 0$
	\item $\bo{C} \succ 0 \implies$ $\bo{M} \succeq 0$ iff $\bo{A} - \bo{B}\bo{C}^{-1}\bo{B}^\top \succeq 0$
\end{itemize}		
		
		
		
	\end{flushleft}
\end{frame}



\begin{frame}{Appendix B}
	\framesubtitle{Part 1}
	\begin{flushleft}
		
		Let us prove that SOCP is a sub-set of SDP. SOC constraint is:
		
		\begin{equation}
			||\bo{A}\bo{x} + \bo{b}|| \leq \bo{c}^\top \bo{x} + d
		\end{equation}
	%
	where $\bo{c}^\top \bo{x} + d \geq 0$, and we can rewrite the SOC as: $(\bo{A}\bo{x} + \bo{b})^\top (\bo{A}\bo{x} + \bo{b}) = (\bo{c}^\top \bo{x} + d)^2$, and assuming $\bo{c}^\top \bo{x} + d > 0$ we can write it as:
	
	\begin{equation}
		\frac{(\bo{A}\bo{x} + \bo{b})^\top (\bo{A}\bo{x} + \bo{b})}{\bo{c}^\top \bo{x} + d} \leq \bo{c}^\top \bo{x} + d
	\end{equation}
	
	which is equivalent to:
	
	\begin{equation}
		-\frac{(\bo{A}\bo{x} + \bo{b})^\top (\bo{A}\bo{x} + \bo{b})}{-(\bo{c}^\top \bo{x} + d)} \leq \bo{c}^\top \bo{x} + d
	\end{equation}
		
	\end{flushleft}
\end{frame}





\begin{frame}{Appendix B}
	\framesubtitle{Part 2}
	\begin{flushleft}
		
		Note that $-\frac{(\bo{A}\bo{x} + \bo{b})^\top (\bo{A}\bo{x} + \bo{b})}{-(\bo{c}^\top \bo{x} + d)} \leq \bo{c}^\top \bo{x} + d$ is equivalent to:
		
		\begin{equation}
			\frac{(\bo{A}\bo{x} + \bo{b})^\top (\bo{A}\bo{x} + \bo{b})}{-(\bo{c}^\top \bo{x} + d)} + (\bo{c}^\top \bo{x} + d) \geq 0
		\end{equation}
		
		Using Schur we can re-write it as:
		
		\begin{equation}
			\begin{bmatrix}
				(\bo{c}^\top \bo{x} + d) & (\bo{A}\bo{x} + \bo{b}) \\
				(\bo{A}\bo{x} + \bo{b})^\top & (\bo{c}^\top \bo{x} + d)
			\end{bmatrix} \succeq 0
		\end{equation}
		
		which is an SDP constraint.
		
	\end{flushleft}
\end{frame}




\begin{frame}{Appendix C}
	\begin{flushleft}
		
		Consider the problem: minimize the largest eigenvalue of $A$. The solution is:
		
		\begin{equation}
			\begin{aligned}
				& \underset{\bo{A}, t}{\text{minimize}}
				& & t, \\
				& \text{subject to}
				& & \bo{A} \preceq t\bo{I}
			\end{aligned}
		\end{equation}
		
		Proof. If $\lambda$ is an eigenvalue of $\bo{A}$, then $\bo{A} \bo{v} = \lambda\bo{v}$, hence $(\bo{A} - t\bo{I}) \bo{v} = (\lambda - t)\bo{v}$, meaning $\lambda - t$ is eigenvalue of $(\bo{A} - t\bo{I})$. Thus, if $(\bo{A} - t\bo{I})$ is negative semi-definite, then $\lambda - t \leq 0$ and $\lambda \leq t$. \qed
		
		
	\end{flushleft}
\end{frame}




\end{document}
