Skip to main content
$$ \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} $$

Homework 2

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.

linear quadratic regulation (16 pts)

Consider the discrete-time linear quadratic regulator problem (DT-LQR)

\[\min_u c_\tau (x,u) \ \text{s.t.} \ x_{s+1} = A_s x_s + B_s u_s,\] \[c_\tau(x,u) = \frac{1}{2} x_t^\top P_t x_t + \frac{1}{2}\sum_{s=\tau}^{t-1} x_s^\top Q_s x_s + u_s^\top R_s u_s\]

where \(P_t\), \(\{Q_s\}_{s=\tau}^{t-1}\), \(\{R_s\}_{s=\tau}^{t-1}\) are given symmetric positive-definite matrices.

In this problem, you’ll apply Bellman’s dynamic programming principle to determine the optimal control, then verify this control is the same one obtained by a descent algorithm.

  1. Determine the optimal control and value at time \(\tau = t\) (i.e. minimize \(c_t\) with respect to \(u_t\), and let \(v^*_t = c_t(x^*,u^*)\) denote the optimal value that can be obtained at time \(t\)).

  2. Determine the optimal control and value at time \(\tau = t-1\) (i.e. minimize \(c_{t-1}\) with respect to \(u_{t-1}\), and let \(v^*_{t-1} = c_{t-1}(x^*,u^*)\) denote the optimal value that can be obtained at time \(t-1\)).

  3. Note that the optimal control is linear in state and the optimal value is quadratic in state (i.e. determine \(K_{t-1}\) and \(P_{t-1}\) such that \(u_{t-1} = K_{t-1} x_{t-1}\) and \(v^*_{t-1} = c_{t-1}(x^*,u^*) = x_{t-1}^T P_{t-1} x_{t-1}\)).

  4. Use the substitution in (c.) to generalize the calculation in (b.) to derive a recursive formula to compute the optimal control and value at any time \(s\in [\tau,t]\).

  5. Implement the recursion in (d.) numerically for the following system, which is a discretized linear spring-mass-damper (let \(\kappa,\beta,q,r,\Delta > 0\) be parameters that you can easily vary in your implementation):

\[A^\Delta = I + \Delta \left[\begin{array}{cc} 0 & 1 \\ -\kappa & -\beta \end{array}\right],\ B^\Delta = \Delta \left[\begin{array}{c} 0 \\ 1 \end{array}\right],\ P_t = 0,\ Q^\Delta_s = q \cdot \Delta \cdot I,\ R^\Delta_s = r \cdot \Delta \cdot I.\]

  1. Investigate how the optimal controls vary with respect to the ratio \(q/r\) (i.e. let \(q/r\) range from \(0.1\) to \(10\), compute the optimal control input, describe the trend you observe, and provide a visualization that clearly illustrates this trend).

  2. Verify your implementation in (e.) by applying a descent algorithm to approximate the optimal input on time horizon \(t = 10\cdot\Delta\) and \(t = 100\cdot\Delta\) for the following initial conditions with \(\kappa,\beta,q,r = 1\), \(\Delta = 0.1\):

\[x_1 = (1,0),\ x_2 = (0,1).\]

Hint: you can directly apply simple random search, or use finite differences to approximate the gradient. To apply steepest descent or Newton-Raphson, you’ll need to analytically differentiate the cost with respect to the control input applied at each timestep.

Bonus: analytically differentiate the cost with respect to the control input applied at each timestep one or two times to implement steepest descent or Newton-Raphson algorithms to approximate the optimal control.

  1. Now consider the infinite time-horizon problem with time-invariant dynamics:

\[\min_u c(x,u) \ \text{s.t.} \ x_{s+1} = A x_s + B u_s,\] \[c(x,u) = \frac{1}{2}\sum_{s=0}^{\infty} x_s^\top Q x_s + u_s^\top R u_s,\]

where \(A\), \(B\), \(Q\), and \(R\) do not vary in time. Noting that the system from (e.) is time-invariant, solve the LQR problem on an “infinite” time horizon: iterate the recursion from (d.) many times and plot the entries of the \(P\) matrix versus iteration number. Compare with the result obtained from solving the discrete algebraic Riccati equation

\[ X = (A - B K)^\top X (A - B K) + K^\top R K + Q,\ K = (B^\top X B + R)^{-1} B^\top X A \]

using the solve_discrete_are routine from the scipy.linalg module or the dare routine from the python-control module (execute !pip install python-control in Jupyter to make this module available).

paper presentation (8pts)

Recall that you will review and present a paper as part of this class; these elements are worth 30% of the grade. More details and guidelines are provided on the course Syllabus.

You must obtain approval for your selected paper prior to submitting this writeup – one third of the credit for this assignment (8/24 points) are earned for selecting an approved paper and entering the paper and presentation information in the shared Google Doc (linked at Canvas -> Collaborations).

The papers provided in the following research literature repository are pre-approved; so long as no one else has claimed the paper when you enter the information in the Google Doc, no further action is needed: link to repository

If you want to present a paper that isn’t in the repository, you must send it to Prof Burden to obtain approval.