Bellman Equation#
Exercises from the Class Notes#
Exercise 2.2#
Prove that the set \(\mathcal{C}(X)\) of bounded continuous functions \(f:X\rightarrow \mathbb{R}\) equipped with the sup norm \(|| y || \equiv \max_{\{ x \in X \}}|y(x)|\) is a complete normed vector space.
Solution
See Example 3 in Chapter 2.11 of Luenberger, \(\textit{Optimization by Vector Space Methods}\).
Exercise 2.3#
Use an inductive argument similar to the one in the proof of Theorem 2.5. to establish that, when assumptions 2.1-2.4 hold, \(V\) is concave.
Solution
Pick \(x_{1},\ x_{2}\in X\) with \(x_{1}\neq x_{2}\). Let \(\theta\in\left(0,1\right)\), and \(x_{\theta} = \left(1-\theta\right)x_{1} + \theta x_{2}\). We define \(g^{\theta}(x_1,x_2)=(1-\theta) g(x_1)+\theta g(x_2)\). Since \(\Gamma\) is convex, we have \(g^{\theta}(x_1,x_2) \in\Gamma\left(x_{\theta}\right)\). By the optimality of the \(T\) operator, we have
Assuming that \(f\) is concave, we find that
The second equality follows from the strict concavity of \(F\) with respect to its second argument, and the premise that \(f\) is also concave. Since \(V = \lim_{n\rightarrow \infty}T^nV_0\), and the space of concave functions is the closure of the space of strictly concave functions, assuming that \(V_0\) is concave, we can conclude that \(V\) is concave.
Additional Exercises#
Exercise 2.4#
Show that the space of non-decreasing functions is the closure of the space of increasing functions.
Show that the space of differentiable functions is not closed.
Solution
We show that any non-decreasing function can be approximated arbitrarily closely by a sequence of strictly increasing function.
Let \(f:[a,b]\rightarrow R\) be a non-decreasing function. We construct a sequence \(\{f_{n}\}\) such that \(f_{n}\left(x\right)=f\left(x\right) + \frac{x}{n}\), where \(n\in \mathbb{N}\).
Each \(f_{n}\) is strictly increasing as for any \(x_{1}\) and \(x_{2}\), if \(x_{1}<x_{2}\), \(f_{n}\left(x_{1}\right)<f_{n}\left(x_{2}\right)\).
As \(n\rightarrow +\infty\), we have \(\sup_{x\in [a,b]}\ |f_{n}\left(x\right) - f\left(x\right)| = \sup_{x\in [a,b]}\ \frac{x}{n} \leq \frac{b}{n}\). Therefore \(f_{n}\rightarrow f\) as \(n\rightarrow +\infty\), and we conclude that the space of non-decreasing functions is the closure of the space of strictly increasing functions.
We show that a sequence of differentiable functions in a closed set converges uniformly to a non-differentiable function.
Suppose \(f_{n}\left(x\right) = \sqrt{\left(x-\frac{1}{2}\right)^2 + \frac{1}{n^2}}\) for \(x\in [0,1]\). It can be easily shown that \(\lim_{n\rightarrow \infty}\ f\left(x\right) = |x - \frac{1}{2}|\), which is non-differentiable at \(x = \frac{1}{2}\).
Exercise 2.5#
Let \(S\) be the space of all continuous, strictly increasing functions on \([a,b]\), with \(||x,y||=\max_{a\leq t \leq b}|x(t)-y(t)|\).
Show that \(S\) is not complete.
Show that \(S\) is complete if “strictly increasing” is replaced with “nondecreasing”.
Solution
We show that there exists a Cauchy sequence that does not converge to an element in S.
Consider \(x_{n}^{t} = 1 + \frac{t}{n},\ t\in[a,b]\). Pick an arbitrary \(x_{m}\).
It can be easily shown that \(\rho\left(x_{n}, x_{m}\right) \rightarrow 0\) as \(n,m\rightarrow \infty\). However, \(x_{n}\left(t\right)\rightarrow x\left(t\right) = 1\), which is a constant. This contradicts our premise that the limit is strictly increasing, thus showing that \(S\) is not complete.
From Question 1 of Exercise 2.4, we know that the space of non-decreasing functions is the closure of the space of increasing functions, meaning that any non-decreasing function in \(S\) can be arbitrarily approximated by a sequence of strictly increasing functions. Therefore, any Cauchy sequence will converge to an element contained by \(S\), and such a space is complete.
Exercise 2.6#
Show that if \(T\) is a contraction on \(S\), then \(T\) is uniformly continuous on \(S\).
Solution
If \(T\) is a contraction mapping, then
\( \exists \beta\in\left(0,1\right), \forall x,y\in S,\ \rho\left(Tx, Ty\right) \leq \beta\rho\left(x,y\right) \).
If \(T\) is uniformly continuous, then
\( \forall \epsilon>0, \exists \delta>0, \forall x,y\in S,\ \rho\left(x,y\right)<\delta\ \Rightarrow\ \rho\left(Tx, Ty\right)<\epsilon\).
Now take \(\delta = \frac{\epsilon}{\beta}\), then \(\forall \epsilon>0\), if \(\rho\left(x,y\right)<\delta\),
\(\rho\left(Tx, Ty\right) \leq \beta\rho\left(x,y\right) < \beta \delta = \epsilon\).
Therefore, \(T\) is uniformly continuous on S.
Exercise 2.7#
Show that in a Banach space, i.e. a complete metric space, a subset is complete if and only if it is closed.
Solution
A complete subset is closed since every convergent (and hence Cauchy) sequence has a limit in the subset. A Cauchy sequence from a closed subset has a limit somewhere in the Banach space. By closure the limit must be in the subset.
More explicitly, Since \(S_0 ⊆ S\) is closed, any convergent sequence in \(S_0\) converges to a point in \(S_0\). Take the set of Cauchy sequences in \(S\). They all converge to points in \(S\) since \(S\) is complete. Take the subset of those sequences that belong to \(S_0\), then by the argument above they converge to a point in \(S_0\), so \(S_0\) is complete
Exercise 2.8#
Show that a continuous function on a compact metric space is bounded and uniformly continuous.
(Weierstrass’ extreme value theorem). If \(X\) is compact and \(f : X \rightarrow R\) is continuous, then \(f\) is bounded and attains its maximum and minimum values.
Solution
(Boundedness) Suppose \(f\) is continuous on a compact metric space \(X\), but it is not bounded. Then \(\forall n\in \mathbb{N}, \exists x_{n}\in X\), such that \(f\left(x_{n}\right)>n\). Since \(X\) is compact, by Bolzano–Weierstrass theorem, there exists a convergent subsequence \(\{x_{n_{k}}\}_{k\in\mathbb N}\). Denote its limit by \(x\). Since \(f\) is continuous at \(x\), \(f\left(x_{n_{k}}\right)\) should converge to \(f\left(x\right)\). However \(\forall k\), \(f\left(x_{n_{k}}\right) > x_{n_{k}}\), then \(\left(x_{n_{k}}\right) \rightarrow +\infty\). This contradicts our premise, implying that a continuous function on a compact metric space is bounded.
(Uniform Continuity) Suppose \(\exists \epsilon_{0}>0\), such that \(\forall \delta>0, \exists x_{n},y_{n}\in X\), such that \(\rho\left(x_{n}, y_{n}\right)<\delta\), but \(\rho\left(f\left(x_{n_{k}}\right),f\left(y_{n_{k}}\right)\right)\geq \epsilon_{0}\). Since \(X\) is compact, the sequence \(\{x_{n_{k}}\}\) has a convergent subsequence, denoted by \(x^{*}\). Then as \(k\rightarrow \infty\), \(\{x_{n_{k}}\}\rightarrow x^{*}\) and \(\{y_{n_{k}}\}\rightarrow x^{*}\). However, as \(f\left(x_{n_{k}}\right)\rightarrow f\left(x^{*}\right)\) and \(f\left(y_{n_{k}}\right)\rightarrow f\left(x^{*}\right)\), we have \(\rho\left(f\left(x_{n_{k}}\right), f\left(y_{n_{k}}\right)\right)\rightarrow 0\), as \(k\rightarrow +\infty\). This contradicts our premise, implying that a continuous function on a compact metric space is uniformly continuous.
(Maximum) Suppose \(f\) is upper-bounded by \(M\) on a compact metric space \(X\), but it cannot attain \(M\). Then \(f\left(x\right)<M,\ \forall x\in X\). Let \(g\left(x\right) = \frac{1}{M-f\left(x\right)}\), then g is also bounded on \(X\). Then \(\exists K>0\) such that \(g\left(x\right)\leq K,\ \forall x\in X\) and \(\frac{1}{M-f\left(x\right)}\leq K\), \(f\left(x\right)\leq M-\frac{1}{k}\). \(M\) is no longer an upperbound now, thus \(f\) attains its maximum values.
(Minimum) Suppose \(f\) is lower-bounded by \(N\) but cannot attain \(N\), and let \(g\left(x\right) = \frac{1}{N-f\left(x\right)}\). We can easily show that \(N\) is no longer a lower bound. Therefore \(f\) attains its minimum values.