CDS 212, Homework 9, Fall 2010

From Murray Wiki
Revision as of 09:01, 23 November 2010 by Sojoudi (talk | contribs) (→‎Problems)
Jump to navigationJump to search
  1. REDIRECT HW draft
J. Doyle Issued: 23 Nov 2010
CDS 212, Fall 2010 Due: 2 Dec 2010


  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 {\tt issos}.)
    4. How can we use the results of the first two parts of this question to conclude that $p$ 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
    V(x) - \epsilon x^Tx \in \Sigma[x],~~~~V(0) = 0,\\
    -\frac{\partial V}{\partial x} f(x) - \epsilon x^Tx \in \Sigma[x],

    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

    f(x) =\left[ \begin{array}{c} -x_2-1.5x_1^2-0.5x_1^3\\
    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\~{}~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\~{}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.
    \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\}.
    (Hint: Generalized S-procedure and SOS relaxations for polynomial nonnegativity.)
  6. Consider the system


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


    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>


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

    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 Salla's invariance principle, show that $V$ satisfies the conditions for certifying global asymptotic stability.)