CDS 212, Homework 9, Fall 2010

J. Doyle	Issued: 23 Nov 2010
CDS 212, Fall 2010	Due: 2 Dec 2010

Problems

1. Prove that a quadratic polynomial is positive semidefinite if and only of it is sum-of-squares.
2. Let <amsmath>p(x_1,x_2) = x_1^2x_2^4 + x_1^4x_2^2 + 1 - 3x_1^2x_2^2.</amsmath>
   1. Is <amsmath>p</amsmath> sum-of-squares?
   2. Is <amsmath>p(x_1,x_2)\cdot(x_1^2+x_2^2)</amsmath> sum-of-squares?
   3. Can you intuitively interpret the difference between the results in the first two parts? (Hint: Remember to use issos.)
   4. How can we use the results of the first two parts of this question to conclude that <amsmath>p</amsmath> is positive semidefinite (even though it is not sum-of-squares)?
3. Generalized S-procedure: Given polynomials <amsmath>f</amsmath> and <amsmath>g,</amsmath> if there exists a positive semidefinite polynomial <amsmath>s</amsmath> such that <amsmath>f-gs</amsmath> is positive semidefinite, then <amsmath>\{x \in\mathbb{R}^n~:~g(x) \geq 0\} \subseteq \{x\in \mathbb{R}^n~:~f(x) \geq 0\}.</amsmath>
   Let <amsmath>f_1(x) = x_1+x_2+1,</amsmath> <amsmath>f_2(x) = 19-14x_1+3x_1^2-14x_2+6x_1x_2+3x_2^2,</amsmath> <amsmath>f_3(x) = 2x_1-3x_2,</amsmath> <amsmath>f_4(x) = 18-32x_1+12x_1^2+48x_2-36x_1x_2+27x_2^2,</amsmath> and <amsmath>f = (1+f_1^2f_2)(30+f_3^2f_4).</amsmath>
   1. Compute a lower bound on the global minimal value of <amsmath>f.</amsmath>
   2. Compute a lower bound on the minimal value of <amsmath>f</amsmath> over the set <amsmath>\{x \in \mathbb{R}^2 ~:~1-(1-x_1)^2 - (1-x_2)^2 \geq 0\}.</amsmath> (Hint: Use the generalized S-procedure and sosopt to set up a SOS program to solve this problem. Try polynomial multipliers <amsmath>s</amsmath> (wherever you need them) of different degrees.)
4. If there exists a polynomial that satisfies <amsmath>

   \begin{array}{c}
   V(x) - \epsilon x^Tx \in \Sigma[x],~~~~V(0) = 0,\\
   -\frac{\partial V}{\partial x} f(x) - \epsilon x^Tx \in \Sigma[x],
   \end{array}
   

   </amsmath>

   then the system <amsmath>\dot{x} = f(x),</amsmath> with <amsmath>f(0)=0,</amsmath> is globally asymptotically stable around the origin. Let's take <amsmath>\epsilon = 10^{-6}</amsmath> and

   <amsmath>

   f(x) =\left[ \begin{array}{c} -x_2-1.5x_1^2-0.5x_1^3\\
   3x_1-x_2\end{array}\right].
   

   </amsmath>
   1. Can you construct a quadratic Lyapunov function that satisfies the above conditions? (Hint: You can try to modify the last piece of the demo file at http://www.cds.caltech.edu/\~utopcu/VerInCtrl/lecture4Demo.m which is on global stability analysis.)
   2. If you cannot find a quadratic Lyapunov function, try a 4th degree one. If you cannot find a 4th degree Lyapunov function, then increase the degree of the candidate Lyapunov functions until you find one. (Hint: 4th degree should work.)
5. Use the data in http://www.cds.caltech.edu/\~utopcu/VerInCtrl/assignment4Data.mat for this exercise. This file contains variables <amsmath>V</amsmath> and <amsmath>f.</amsmath> If you care, <amsmath>V</amsmath> is a Lyapunov function (obtained through some analysis that we will cover later in this course) computed for a system governed by <amsmath>\dot{x} = f(x).</amsmath> Compute a lower bound on the optimal value of the following optimization problem. <amsmath>

   \begin{array}{c}
   \displaystyle{\max_{\mu > 0}} ~~~~\mu\\
   \text{subject to}~~~~~\{ x~:~ V(x) \leq 0.01\} \subseteq \{ x~:~ \frac{\partial V}{\partial x} \cdot f(x) \leq -\mu V\}.
   \end{array}
   

   </amsmath> (Hint: Generalized S-procedure and SOS relaxations for polynomial nonnegativity.)
6. Consider the system <amsmath>

   \begin{aligned}

   &\dot{x}_1 = -x_2\\
   &\dot{x}_2 = -f(x_2) - g(x_1), 
   

   \end{aligned}

   </amsmath>where the functions <amsmath>f</amsmath> and <amsmath>g</amsmath> satisfy the following conditions:
   1. <amsmath>f</amsmath> and <amsmath>g</amsmath> are continuous.
   2. <amsmath>f(0)=g(0)=0.</amsmath> <amsmath>\sigma f(\sigma) >0</amsmath> and <amsmath>\sigma g(\sigma)>0</amsmath> whenever <amsmath>\sigma\neq 0.</amsmath>
   3. <amsmath>\int_0^\sigma g(\xi) d\xi \rightarrow \infty</amsmath> as <amsmath>|\sigma| \rightarrow \infty.</amsmath>

   Using

   <amsmath>

   V(x_1,x_2) = \frac{1}{2}x_2^2 + \int_0^{x_1} g(\xi) d\xi
   

   </amsmath>

   as a Lyapunov function candidate, show that the origin is a globally asymptotically stable equilibrium point for this system. (Hint: Using the above conditions and La Salle's invariance principle, show that <amsmath>V</amsmath> satisfies the conditions for certifying global asymptotic stability.)