Homework 1

You are welcome (and encouraged) to work with others, but each individual must submit their own writeup.

You are welcome to use your preferred computational toolkit – upload the commented sourcecode alongside your writeup.

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.

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.

optimization algorithms (10 pts)

Consider the following cost function of a scalar decision variable $u\in\mathbb{R}$:

\[ c(u) = \frac{u^{6}}{6} - \frac{7 u^{5}}{5} + \frac{17 u^{4}}{4} - \frac{17 u^{3}}{3} + 3 u^{2}. \]

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.
What is the minimum of $c$? What is the minimizing $u$?

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.

For the remainder of the problem, plot $u$ versus iteration and also plot the iterations on the graph of $c$, i.e. do plot(u) on one axis and plot(u,c(u),'.') where u is a vector containing the iterates.

Run the (gradient descent) iteration

\[ u^+ = u - \gamma\, d(u) \]

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.

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.

Run the iteration above using the (finite differences) approximation

\[ \left[d(u)\right]_j = \frac{1}{\Delta}( c(u + \Delta\, e_j) - c(u) ) \]

($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?

Run one of the (simple random search) iterations

\[ 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) \]

\[ 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} \]

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$?

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.

dynamic systems (14 pts)

Consider the continuous-time linear time-invariant (CT-LTI) system

\[ \dot{x}(t) = A x(t). \]

Verify that $x(t) = e^{A t} x(0) $ is the trajectory obtained from initial state $x(0)$.

The remainder of the problem will focus on the following specific $A$ (obtained from a damped harmonic oscillator): \[ A = \left[\begin{array}{cc} 0 & 1 \\ -\kappa & -\beta \end{array} \right].\]

A discrete-time linear time-invariant (DT-LTI) approximation of the original control system with timestep parameter $\Delta > 0$ is given by

\[ x(t + \Delta) \approx x(t) + \Delta\, \dot{x}(t) = \hat{A} x(t). \]

Determine the matrix $\hat{A}$.
Run the (forward Euler) iteration $x^+ = 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?
Repeat (c.) with $\beta = -1$. You should observe that trajectories are divergent spirals ($x_1,x_2 \rightarrow \infty$).
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).
Analytically differentiate the expression for $x(t)$ from (a) with respect to the initial state $x(0)$.
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.)

Bonus: repeat (a.–g.) for the control system $\dot{x} = A x + B u$ with trajectory expression \[ x(t) = e^{A t} x(0) + \int_0^t e^{A (t - \tau)} B u(\tau) d\tau \] 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).