hw1.ipynb

{"cells":[{"cell_type":"markdown","metadata":{"id":"pMQbHfCcNF4z"},"source":["# 546 (Optimization for Learning and Control) hw1\n","\n","You are welcome (and encouraged) to work with others, but each individual must submit their own writeup.\n","\n","You are welcome to use your preferred computational toolkit -- upload the **commented** sourcecode alongside your writeup (e.g. the .ipynb file).\n","\n","You are welcome to consult research articles and other materials -- upload a .pdf of the article alongside your writeup and indicate which references were used where in the writeup."]},{"cell_type":"markdown","metadata":{"id":"TToKMqGqNF42"},"source":["# optimization and learning for control\n","\n","***Purpose:***  this sequence of exercises will introduce you to the basic concepts, problems, and techniques we'll explore throughout the course.  If you don't understand what a problem is asking or how to approach it, it's very likely there are other folks in the same boat -- please ask questions at Office Hours or on Canvas Discussions.  The problems are designed to stretch your thinking and abilities -- I encourage you to make a genuine attempt on every problem, but don't spin your wheels if you're not making good progress."]},{"cell_type":"markdown","metadata":{"id":"_MsVesnnNF43"},"source":["## optimization algorithms\n","\n","Consider the following cost function of a scalar decision variable $u\\in\\mathbb{R}$:\n","\n","$$ c(u) = \\frac{u^{6}}{6} - \\frac{7 u^{5}}{5} + \\frac{17 u^{4}}{4} - \\frac{17 u^{3}}{3} + 3 u^{2}. $$\n","\n","a. Plot $c(u)$, $D c(u)$, and $D^2 c(u)$ for scalar $u$; use the `subplot(3,1,n)` for `n = 1, 2, 3` to align the $u$-axes of the three plots.\n","\n","b. What is the minimum of $c$?  What is the minimizing $u$?\n","\n","***Notice:*** $Dc(u^*) = 0$ and $D^2 c(u^*) > 0$ at the minimizing $u^*$ (similarly, $Dc(u_*) = 0$ and $D^2 c(u_*) < 0$ at the maximizing $u_*$) -- such points are termed ***stationary*** for reasons that will become clear in the next problem.\n","\n","c. Run the (***gradient descent***) iteration\n","\n","$$ u^+ = u - \\gamma\\, d(u) $$\n","\n","using the actual derivative $d(u) = Dc(u)$ starting from multiple initial $u$'s and with multiple values of the parameter $\\gamma > 0$.  Describe all of the outcomes (i.e. asymptotic behavior of the iteration) you observe and provide plots that illustrate these outcomes.\n","\n","***Notice:*** you should observe that ***stationary points*** (where $Dc = 0$) are ***fixed points*** for this iteration, and that minimizers are (locally) attracting points for this iteration.\n","\n","d. Run the iteration above using the (***finite differences***) approximation\n","\n","$$ \\left[d(u)\\right]_j = \\frac{1}{\\Delta}( c(u + \\Delta\\, e_j) - c(u) ) $$\n","\n","($e_j = \\left(0, \\dots, 0, 1, 0, \\dots, 0\\right)^\\top$ is the $j$-th standard Euclidean basis vector) starting from multiple initial $u$'s and with multiple values of the parameters $\\gamma, \\Delta > 0$.  Describe all of the outcomes you observe and provide plots that illustrate these outcomes.  Does $\\gamma > \\Delta$ or $\\Delta > \\gamma$ give better results?\n","\n","e. Run one of the (***simple random search***) iterations\n","\n","$$ u^+ = u - \\frac{\\gamma}{N\\, \\sigma} \\sum_{n = 1}^N ( c(u + u_n) - c(u) ) \\cdot u_n,\\ u_n \\sim \\mathcal{N}(0,\\sigma^2) $$\n","\n","$$ u^+ = u - \\frac{\\gamma}{N\\, \\Delta} \\sum_{n = 1}^N ( c(u + \\Delta u_n) - c(u) ) \\cdot u_n,\\ u_n \\sim \\mathcal{S} $$\n","\n","starting from multiple initial $u$'s and with multiple values of the parameters $\\gamma, \\Delta, \\sigma > 0$, where $\\mathcal{N}(0,\\sigma^2)$ denotes a ***normal*** or ***Gaussian*** distribution with mean $0$ and variance $\\sigma^2$ and $\\mathcal{S}$ denotes the ***uniform*** distribution on the sphere.  Describe all of the outcomes (i.e. asymptotic behavior of the iteration) you observe and provide plots that illustrate these outcomes.  How should $\\sigma$ or $\\Delta$ relate to $\\gamma$?\n","\n","***Bonus:*** repeat (a.--e.) with the quadratic function $c(u) = u^\\top H u$ where $u\\in\\mathbb{R}^2$ and $H = H^\\top > 0$ is a positive-definite matrix of your choosing; you may want to use the `contour` function to visualize the results."]},{"cell_type":"markdown","metadata":{"id":"R94C5NR5NF44"},"source":["## dynamic systems\n","\n","Consider the continuous-time linear time-invariant (CT-LTI) system\n","\n","$$ \\dot{x}(t) = A x(t). $$\n","\n","a. Verify that $x(t) = e^{A t} x(0) $ is the trajectory obtained from initial state $x(0)$.\n","\n","The remainder of the problem will focus on the following specific $A$ (obtained from a damped harmonic oscillator):\n","$$ A = \\left[\\begin{array}{cc} 0 & 1 \\\\ -\\kappa & -\\beta \\end{array} \\right].$$\n","\n","A discrete-time linear time-invariant (DT-LTI) approximation of the original control system with timestep parameter $\\Delta > 0$ is given by\n","\n","$$ x(t + \\Delta) \\approx x(t) + \\Delta\\, \\dot{x}(t) = \\hat{A} x(t). $$\n","\n","b. Determine the matrix $\\hat{A}$.\n","\n","c. Run the (***forward Euler***) iteration $x^+ = \\hat{A} x $ with $\\kappa = 1$ and $\\beta = 1$ with multiple values of the parameter $\\Delta > 0$ and compare with the result obtained from the expression for $x$ from (a.) (you may want to use `np.expm` to numerically evaluate this expression).  Create two types of plots to illustrate your results: (i) states $x_1,x_2$ versus time $t$; (ii) second state $x_2$ versus first state $x_1$.  You should observe that trajectories are spirals that converge to the origin ($x_1,x_2 \\rightarrow 0$); is there a value of $\\Delta$ that prevents this from happening?\n","\n","d. Repeat (c.) with $\\beta = -1$.  You should observe that trajectories are divergent spirals ($x_1,x_2 \\rightarrow \\infty$).\n","\n","e. Repeat (c.) with $\\beta = 0$.  You should observe that the (CT-LTI) trajectories are circles (because $\\beta = 0$ corresponds to an energy-conserving oscillator), whereas the (DT-LTI) trajectories are divergent spirals (because this simulation algorithm does not preserve energy).\n","\n","f. Analytically differentiate the expression for $x(t)$ from (a) with respect to the initial state $x(0)$.\n","\n","g. Differentiate the (DT-LTI) iteration with respect to initial state and compare with the result from (f.) for $t = 1$ $\\kappa = 1$ and $\\beta = 0, +1, -1$.  (***Hint:*** you may consider computing the derivative analytically or numerically, e.g. using finite differences.)\n","\n","***Bonus:*** repeat (a.--g.) for the control system $\\dot{x} = A x + B u$ with trajectory expression\n","$$ x(t) = e^{A t} x(0) + \\int_0^t e^{A (t - \\tau)} B u(\\tau) d\\tau $$\n","using a sinusoidal input $u(t) = \\sin(\\omega t)$ ($\\hat{A}$ will be the same in (b.), but you'll need to find $\\hat{B}$ for the subsequent subproblems)."]}],"metadata":{"anaconda-cloud":{},"colab":{"collapsed_sections":[],"name":"hw1.ipynb","provenance":[]},"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"},"language_info":{"codemirror_mode":{"name":"ipython","version":3},"file_extension":".py","mimetype":"text/x-python","name":"python","nbconvert_exporter":"python","pygments_lexer":"ipython3","version":"3.8.3"}},"nbformat":4,"nbformat_minor":0}