This repo contains some exercise solutions for Daniel Liberzon's Calculus of Variations and Optimal Control Theory: A Concise Introduction book and other problems.
- Lecture 1: Introduction: path optimization vs. point optimization; basic analysis; basic facts from finite-dimensional optimization
- Lecture 2: Calculus of variations: examples of variational problems; Euler-Lagrange equation; Hamiltonial formalism and Legendre transformation; mechanical interpretation; constraints; second variation and Legendre’s necessary condition; weak and strong extrema; conjugate points and sufficient conditions
- Lecture 3: From Calculus of Variations to Optimal Control : statement of the optimal control problem; variational argument and preview of the maximum principle
- Lecture 4: The Maximum Principle: statement and proof of the maximum principle; relation to Lie brackets; bang-bang and singular optimal controls; dynamic programming; sufficient conditions for optimality
- Lecture 5: The Hamilton-Jacobi-Bellman equation: HJB equations; viscosity solutions of the HJB equation
- Lecture 6: The Linear Quadratic Regulator: LQR problems
The book is part of coursework for the Optimal Control course from professor Donghwan Lee at KAIST. Many exercises are taken from Liberzon's book, but not all of them - and many are not in order as well. I could not find a solution manual at the time, but searching in Google with certain keywords helped for some of the exercises. If you would like to improve the repo, please read the Feedback section!
The version of the text is the following:
[1] D. Liberzon, Calculus of Variations and Optimal Control Theory: A Concise Introduction. Princeton ; Oxford: Princeton University Press, 2012.
Here is the list of exercises divided by lectures, so they can be more easily searched. Equations are left in Latex and will be hopefully displayed by Github in the future.
Prove the above lemma: "If scalar sequence is monotonically nondecreasing and bounded above, then it converges. Similarly, if a scalar sequence is monotonically nonincreasing and bounded below, then it converges."
Devise a set X whose supremum exists and find its supremum. What is the maximum of the set? Do the same for the infimum.
Devise a sequence $(x_k)_{k=1}^{\infty}$ whose upper limit exists and find its upper limit. Do the same for the infimum.\
Devise examples of an open set and a closed set.\
Prove the two following propositions.
Proposition 1 (First-order necessary condition for constrained
optimality): Suppose that
Proposition 2 (Second-order necessary condition for constrained
optimality): Suppose that
Suppose that $f$ is a $\mathcal{C}^2$ function and $x^$ us a point of its domain at which we have $\langle\nabla f(x^),d \rangle \geq 0$ and $d^T \nabla^2 f(x^)d > 0$ for every nonzero feasible direction d. Is $x^$ necessarily a local minimum of f? Prove or give a counterexample.\
Give an example where a local minimum $x^$ is not a regular point and the above necessary condition (namely first-order necessary condition for constrained optimality) is false (justify both of these claims).*\
Prove that the set of continuous functions $f:[a,b] \to \mathbb{R}, f \in \mathcal{C}^0$ is a vector space with typical addition and scalar multiplication.\
For $y \in \mathcal{C}^0$, define:
For $x, y \in \mathcal{C}^0$, define
Consider the space $\mathcal{C}^0([0,1]) \to \mathbb{R}$, let
$g : \mathbb{R} \to \mathbb{R}$ be a $\mathcal{C}^1$ function, and
define the functional $J$ on $V$ by $J(y) = \int_0^1 g'(y(x))dx$. Show
that its first variation exists and it is given by the formula
Find another example of a variational problem. Describe it verbally first, then formalize it by specifying admissible curves and giving an expression for the functional to be minimized or maximized. You do not need to solve it.\
Find an extremal for the problem
Find an extremal for the problem
Use the no $x$ result to show that extremals for the brachistochrone
problem are indeed given by
Confirm directly from the equations (2.10), (2.11), 2.12) (Hamilton's canonical equations) that in the "no y" case $p$ is constant along extremals and in the "no x" case $H$ is constant along extremals.\
Find the curve $y^$ that minimizes*
Show that optimal curves for Dido's problem are circular arcs.\
Show that the optimal curves for the catenary problem satisfy
Is Legendre's necessary condition satisfied by the admissible extremal
for the problem minimizing
Consider the problem
subject to
Discuss how the solution changes as $P \to \infty$ and $P \to 0$.
Provide an intuitive explanation of the phenomenon.\
Solve the problem
$$\begin{aligned} &u^* := \argmin_{u:[0,t_f] \to [-1, 1]} J := t_f \ &\text{subject to} \ &\begin{cases} &\Dot{x}_1(t) = -4 x_1(t) + 2x_2(t) + 2u(t)\ &\Dot{x}_2(t) = 3x_1(t) -3x_2(t) \end{cases} \smallspace \begin{cases} &x_1(0) = x_0 \smallspace x_2(0) = 0 \ &x_1(t_f) = 0, \smallspace x_2(t_f) = 0 \end{cases}\end{aligned}$$\
Solve the problem
where a, b are given nonzero scalars, $x_0 \in \mathbb{R}$ is an initial state, $T > 0$ is a fixed final time, and $q > 0$ is a given positive scalar.\
Suppose we own a factory whose output we can control. Let us begin to construct a mathematical model by setting
-
$x(t)$: amount of output produced at time $t \in [0,T]$
-
$u(t)$: fraction of output reinvested at time $t \in [0,T]$
This will be our control, and is subject to the obvious constrain that
Given such a control, the corresponding dynamics are provided by the ODE
where the constant $k >0$ modeling the growth rate of our reinvestment and $u(t)x(t)$ is the amount of reinvested output. Let us take as a payoff functional
where $(1-u(t))x(t)$ is our consumption. The meaning is that we want to
maximize our total consumption of the output.
The overall problem is: $$\begin{aligned}
&u^* := \argmax_{u:[0,T] \to [0,1]} J(u) = \int_0^T (1-u(t))x(t)dt \
&\text{subject to}\
&\Dot{x}(t) = ku(t)x(t)\
&x(0)=x_0\end{aligned}$$
Find an optimal control policy for this problem.\
A young investor has earned in the stock market a large amount of money S and plans to spend it so as to maximize his enjoyment through the rest of his life without working. He estimates that he will live exactly T more years and that his capital $x(t)$ should be reduced to zero at time T, i.e., $x(T) = 0$. Also he models the evolution of his capital by the differential equation
where $x(0) = S$ is his initial capital, $\alpha > 0$ is a given
interest rate, and $u(t) \geq 0$ is his rate of expenditure. The total
enjoyment he will obtain is given by
Here $\beta$ is some positive scalar, which serves to discount the future enjoyment. Find the optimal control $u^ (t), t \in [0, T]$.*\
Solve the problem $$\begin{aligned} &u^* := \argmin_{u:[0,T] \to \mathbb{R}} J(u) = \int_0^T \sqrt{1 + u(t)^2}dt \ &\text{subject to}\ &\Dot{x}(t) = u(t), \smallspace x(0)=x_0\end{aligned}$$ where $x_0 \in \mathbb{R}$ is an initial state, $T>0$ is a fixed final time.\
Solve the problem $$\begin{aligned} &u^* := \argmin_{u:[0,T] \to \mathbb{R}} J(u) = \int_0^T \sqrt{1 + u(t)^2}dt \ &\text{subject to}\ &\Dot{x}(t) = u(t), \smallspace x(0)=x_0\end{aligned}$$ where $x_0 \in \mathbb{R}$ is an initial state, $T>0$ is a fixed final time.\
Solve the problem $$\begin{aligned} &u^* := \argmin_{u:[0,T] \to \mathbb{R}} J(u) = \int_0^T \sqrt{1 + u(t)^2}dt \ &\text{subject to}\ &\Dot{x}(t) = u(t), \smallspace x(0)=x_0, \smallspace x(T) = x_1\end{aligned}$$ where $x_0 \in \mathbb{R}$ is an initial state, $T>0$ is a fixed final time.\
Prove the lemma: if $a + \varepsilon \geq b$ for arbitrary $\varepsilon > 0$ with $a, b \in \mathbb{R}$, then $a \geq b$.\
Complete the proof of the principle of optimality by showing the reverse inequality $V(t,x) \leq \Bar{V}(t,x)$.\
For completeness, we consider a slightly more general form of the linear quadratic regulator. The standard LQR derivation attempts to drive the system to zero. Consider now the problem:
$$\begin{aligned} &u^* := \argmin_{u:[0,T] \to \mathbb{R}^m} J(u) \ &\text{subject to}\ &\Dot{x}(t) = Ax(t) + Bu(t), \smallspace x(0)=x_0\end{aligned}$$ where $$\begin{split} J(u) := &(x(T) - x_d (T)) ^T Q_f (x(T) - x_d (T) ) \ + &\int_0^T \left( (x(t) - x_d(t)) ^T Q(x(t) - x_d(t)) + (u(t) - u_d(t)) ^T R(u(t) - u_d(t)) \right) dt \end{split}$$
$Q_f = Q_f^T \geq 0$ (positive semidefinite), $Q = Q^T \geq 0$
(positive semidefinite), $R = R^T >0$ (positive definite).
Find a formulation of an optimal policy and the corresponding HJB
equation (similar to the Riccati equation) using the sufficient
condition.
Hint: consider a candidate of value functions of the following form
Given the optimal control problem for a scalar nonlinear system:
Obtain the optimal feedback solution by solving the associated HJB
equation.
Hint: First show that the HJB partial differential equation admits a
solution that is quadratic in x.\
Consider a cart with an inverted pendulum hinged on top of it. For simplicity, the cart and the pendulum are
assumed to move in only one plane, and the friction, the mass of the
stick, and the gust of wind are disregarded. The problem is to maintain
the pendulum at the vertical position. For example, if the inverted
pendulum is falling in the direction shown, the cart moves to the right
and exerts a force, through the hinge, to push the pendulum back to the
vertical position.
Let's consider the linearized inverted pendulum system (assuming
$\theta(t)$ and $\Dot{\theta}(t)$ are very small)
$$\begin{bmatrix}
\Dot{x}_1(t) \ \Dot{x}_3(t) \ \Dot{x}_3(t) \ \Dot{x}_4(t) \
\end{bmatrix}=
\begin{bmatrix}
0 & 1 & 0 & 0 \
0 & 0 & -\frac{mg}{M} & 0 \
0 & 0 & 0 & 1 \
0 & 0 & \frac{(M+m)g}{Ml} & 0
\end{bmatrix}
\begin{bmatrix}
x_1(t) \ x_2(t) \ x_3(t) \ x_4(t)
\end{bmatrix}
+
\begin{bmatrix}
0 \ \frac{1}{M} \ 0 \ - \frac{1}{Ml}
\end{bmatrix}
u(t)$$ where
$x_1(t) = x(t), \smallspace x_2(t) = \Dot{x}(t), \smallspace x_3(t) = \theta(t), \smallspace and \smallspace x_4(t) = \Dot{\theta}(t)$.
Consider the LQR problem
where A and B are appropriate system matrices with m=1, M=2, l=3 and
g=9.8.
Tasks:
-
Appropriately choose the weighting $Q \geq 0$ and $R > 0$ to maintain the pendulum at the vertical position, i.e., $\theta(t) = 0$ and $\Dot{\theta}(t) = 0$ as much as possible.
-
Find an optimal policy for the LQR problem using Python or Matlab functions.
-
Plot trajectories of the system x(t) and the control input u(t) over certain time interval to demonstrate the performance of your optimal control policy.
-
In the answer, please include your Python or Matlab codes.
-
Change the weight and see how the performance changes and discuss about the results.
Consider the double integrator $$\begin{aligned} &\Dot{x}_1(t) = x_2(t), \ &\Dot{x}2(t) = u(t)\end{aligned}$$ and the cost $$J(u) = \int{t_0}^\infty \left( x_1(t)^2 + x_2(t)^2 + u(t) ^2 \right) dt$$ Find P by solving the ARE. Verify (either analytically or numerically) that it is indeed the steady-state solution of the RDE.\
Consider the infinite-horizon LQR problem $$\begin{aligned} &u^* := \argmin_{u:[0,\infty) \to \mathbb{R}} J(u) := \int_0^\infty \left( qx(t)^2 + ru(t)^2 \right) dt \ &\text{subject to}\ &\Dot{x}(t) = ax(t) + bu(t), \smallspace t \in [t_0, \infty) \ &x(t_0) = x_0\end{aligned}$$
where $a, q, r > 0$ and $b \in \mathbb{R}$ is arbitrary. Find the optimal control law. Moreover, show that for $r \to 0$, the eigenvalue of the optimal closed-loop system moves off to $- \infty$, while for $r \to \infty$, the eigenvalue of the optimal closed-loop system tends to $−a$\
The complete lateral model of a Boeing 747 is $$\begin{aligned} &\Dot{x}(t) = Ax(t) + Bu(t) \ &y(t) = Cx(t) + Du(t)\end{aligned}$$ where $$A = \begin{bmatrix} -10 & 0 & 0 & 0 & 0 & 0 \ 0.0729 & -0.0558 & -0.997 & 0.0802 & 0.0415 & 0 \ -4.75 & 0.598 & -0.115 & -0.0318 & 0 & 0 \ 1.53 & -3.05 & 0.388 & -0.465 & 0 & 0 \ 0 & 0 & 0.0805 & 1 & 0 & 0 \ 0 & 0 & 1 & 0 & 0 & -0.3333 \ \end{bmatrix} , \smallspace B = \begin{bmatrix} 1\ 0\ 0\ 0\ 0\ 0\ \end{bmatrix}$$ and $$C = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & -0.3333 \end{bmatrix} , \smallspace D=0$$
Minimize the sum of the energy of the output y and the energy of the control u. The main effort is to minimize the energy of y which is supposed to be zero in a steady state condition. So we put a weight $q = 9.527 > 1$ on the energy of y. The problem now is as follows.
$$\begin{aligned} &u^* := \argmin_{u:[0,\infty) \to \mathbb{R}} J(u) := \int_0^\infty [qy(t)^Ty(t) + u(t)^2] dt \ &\text{subject to}\ &\Dot{x}(t) = Ax(t) + Bu(t), \smallspace t \in [t_0, \infty) \ &y(t) = Cx(t) + Du(t), \smallspace t \in [t_0, \infty) \ &x(t_0) = x_0\end{aligned}$$ Tasks:
-
Find an optimal policy for the LQR problem by solving ARE using Python or Matlab functions.
-
Plot trajectories of $y(t)$ and $u(t)$.
-
In the answer, please include your Python or Matlab codes.
If you would like to contribute to this repository by improving, correcting solutions or adding new exercises, feel free to raise an Issue or to contribute with a Pull Request!