2. 递归问题的求解

在上一部分之中, 我们成功把同时需要求解无限个变量的顺序问题, 转化为只需求解下一期的有限变量的递归问题. 这一部分中, 我们将讨论如何求解递归问题.

2.1值函数与策略函数: 一个通俗比喻

描述递归问题的最关键方程是 Bellman 方程, 为如下形式:$$v(x_t)=\underset{x_{t+1}\in \Gamma (x_t)}{\max }\left\{F(x_t,x_{t+1})+\beta v_{t+1}(x_{t+1})\right\}$$(2.1)其中, 值函数 $v(x_t)$ 是给定初值 $x_{t+1}$ 之后这一最优化问题可取得的最值, 策略函数 $x_{t+1}^{\ast }=g(x_t)$ 是这一最优化问题的解. 同时, 策略函数满足 Bellman 方程推导出的 Euler 方程.$$F_2(x_t^{\ast },x_{t+1}^{\ast })+\beta F_1(x_{t+1}^{\ast },x_{t+2}^{\ast })=0$$(2.2)

对值函数和策略函数的最好比喻是 “尽人事, 知天命”. 在给定 “生辰八字”(初值 $x_t$) 之后, “人事表”(策略函数 $g(x_t)$) 告诉我们在此情形下我们应该执行的最优行动, 而 “天命表”(值函数 $v(x_t)$) 则告诉我们在 “尽人事” 之后我们能够达到的最好结果.

我们也容易证明值函数与策略函数的对偶关系 (“历览前贤国与家, 成由勤俭败由奢”). 最优化问题取到值函数的对应值, 当且仅当最优化问题的解取策略函数的对应值.

然而求解值函数与策略函数并不容易, 因为 Bellman 方程两侧同时出现了值函数, 意味着我们在求解值函数时已经预先 “知道” 了值函数. 要解决这一问题, 我们需要使用迭代的方法.

2.2迭代法的理论基础: Banach 不动点定理

Banach 不动点定理 (压缩映射定理)

在使用迭代法之前, 我们需要先引入重要的 Banach 不动点定理. 我们先从定义几个概念开始.

定义 2.2.1 (序列的收敛性).

对度量空间 $(X,d)$ 中的一个序列 $\{x_n\}$, 若 $\forall ϵ>0$, $\exists N(ϵ)$, 使得$$d(x^{\ast },x_n)<ϵ,\forall n\ge N(ϵ),$$则称 $\{x_n\}$ 收敛 (convergent) 至极限 $x^{\ast }\in X$.

定义 2.2.2 (Cauchy 列).

对度量空间 $(X,d)$ 中的一个序列 $\{x_n\}$, 若 $\forall ϵ>0$, $\exists N(ϵ)$, 使得$$d(x_m,x_n)<ϵ,\forall m,n\ge N(ϵ),$$则称 $\{x_n\}$ 为 Cauchy 列.

注 2.2.3.

1.	所有收敛列都是 Cauchy 列.
2.	某些度量空间中, Cauchy 列不收敛到该空间之中, Cauchy 列不一定是收敛列.

定义 2.2.4 (完备度量空间).

若一个度量空间中的所有 Cauchy 列都收敛到空间中的某一点, 则称该空间为完备度量空间 (complete metric space).

例 2.2.5 (几个完备度量空间).

1.	$({\mathbb{R}}^n,d_2)$ 是完备的, 其中 $d_2(x,y)=\sqrt{{\sum }_{i=1}^n(x_i-y_i{)}^2}$.
2.	$(C[a,b],d_{\infty })$ 是完备的, 其中 $d_{\infty }(f,g)=\underset{x}{\max }|f(x)-g(x)|$

定义 2.2.6 (压缩映射).

对度量空间 $(X,d)$, 映射 $f:X\to X$, 若 $\exists \beta \in [0,1)$, 使得$$d[f(x),f(y)]\le \beta d(x,y),\forall x,y\in X,$$则称 $f$ 为压缩映射 (contraction mapping), 称 $\beta$ 为该压缩映射的模量 (modulus).

有了上述的准备, 我们可以引入 Banach 不动点定理.

定理 2.2.7 (Banach 不动点定理).

对于完备度量空间 $(X,d)$, 若 $f:X\to X$ 是模量为 $\beta$ 的压缩映射, 则 $f$ 有唯一不动点 (fixed point) $x^{\ast }\in X$, 使得 $f(x^{\ast })=x^{\ast }$.

该定理还有两条推论.

推论 2.2.8.

1.	给定初始点 $x_0$, 通过 $x_{n+1}=f(x_n)$ 定义出 $\{x_n\}$, 则 $\{x_n\}$ 收敛至 $x^{\ast }$.
2.	$\{x_n\}$ 的收敛速率为几何速率, 即$$d(f^n(x_0),x^{\ast })\le {\beta }^{n}d(x_0,x^{\ast }).$$

Blackwell 充分条件

直接检验一个映射是否为压缩映射有所不便, 故而我们引入 Blackwell 充分条件来简化判定过程.

定理 2.2.9 (Blackwell 充分条件).

令 $B(X)$ 为有界函数 $f:X\to R,X\subseteq R^I$ 构成的空间, 令 $T$ 为度量空间 $(B(X),d_{\infty })$ 上的一个算子.

若 $T$ 有如下两个性质:

1.	单调性 (monotonicity): $\forall f,g\in B(X)$, 若 $f\ge g$, 则 $T(f)\ge T(g)$;
2.	贴现性 (discounting): $\forall c>0,f\in B(X)$, $\exists \beta \in [0,1)$, 使得$$T(f+c)\le T(f)+\beta c;$$

则 $T$ 是一个模量为 $\beta$ 的压缩映射.

证明.

令 $||f-g||\equiv d_{\infty }(f,g)=\underset{x\in X}{\max }|f(x)-g(x)|$. 则有$$\begin{array}{rl}& f(x)-g(x)\le ||f-g||,\forall x\in X\\ ⟹& f-g\le ||f-g||⟹f\le g+||f-g||\end{array}$$由单调性, 则有: $$T(f)\le T(g+||f-g||)$$由贴现性, 则有: $$T(g+||f-g||)\le T(g)+\beta ||f-g||$$综上有: $$\begin{array}{r}T(f)\le T(g)+\beta ||f-g||\\ T(f)-T(g)\le \beta ||f-g||\end{array}$$调换 $f$ 与 $g$, 同理可得 $T(g)-T(f)\le \beta ||f-g||$.

则有: $$||T(g)-T(f)||\le \beta ||f-g||$$等价于: $$d_{\infty }[T(g),T(f)]\le \beta d_{\infty }(g,f)$$则 $T$ 为度量空间 $(B(X),d_{\infty })$ 上的压缩映射, 模量为 $\beta$.

$\square$

2.3值函数迭代法的过程

值函数迭代法 (Value Function Iteration) 可以帮助我们求解递归问题.

对于 Bellman 方程:$$v_t(x_t)=\underset{x_{t+1}\in \Gamma (x_t)}{\max }\left\{F(x_t,x_{t+1})+\beta v_{t+1}(x_{t+1})\right\}$$(2.1)传统方法难以求解, 因为要求出方程左边的 $v$, 必须要通过方程右边使用正确的 $v$ 来求解最大化问题, 从而陷入了 “套娃” 的困难.

但我们可以观察到, 方程的右边天然定义了一个作用于 $v\in B(X)$ 的映射 $T$:$$Tv=\underset{x_{t+1}\in \Gamma (x_t)}{\max }\left\{F(x_t,x_{t+1})+\beta v_{t+1}(x_{t+1})\right\}$$(2.3)而 Bellman 方程则成为:$$v=Tv$$(2.4)

若我们能证明 $T$ 是压缩映射, 则无论从怎样的初值 $v_0$ 出发, 经过足够多次 $T$ 的作用, $\{v_n\}$ 最终总会收敛至不动点 $v^{\ast }=T{v}^{\ast }$.

命题 2.3.1.

对于度量空间上的如下映射 $T$: $$Tv(x)=\underset{y\in \Gamma (x)}{\max }\left\{F(x,y)+\beta v(y)\right\}$$若满足:

1.	$F(x,y):X\times X\to \mathbb{R}$ 是有界 (bounded) 连续 (continuous) 函数;
2.	$\Gamma (x)$ 是紧 (compact-valued) 且连续的对应 (correspondence);

则 $T$ 是度量空间 $(C(X),d_{\infty })$ 上的压缩映射.

证明.

我们验证 $T$ 满足 Blackwell 充分条件:

1.	单调性: 令 $v(x)\ge w(x)$, $\forall x\in X$, 则有$$\begin{array}{rl}Tv& =\underset{y\in \Gamma X}{\max }\left\{F(x,y)+\beta v(y)\right\}\\ & \ge \underset{y\in \Gamma X}{\max }\left\{F(x,y)+\beta w(y)\right\}\\ & =Tw\end{array}$$
2.	贴现性: $$\begin{array}{rl}T(v+c)& =\underset{y\in \Gamma X}{\max }\left\{F(x,y)+\beta [v(y)+c]\right\}\\ & =\underset{y\in \Gamma X}{\max }\left\{F(x,y)+\beta v(y)+\beta c\right\}\\ & =Tv+\beta c\end{array}$$

此外, 命题的两个条件确保 $\max$ 运算有意义并能求出最大值, 由最大值原理, 可证明 $T$ 将有界连续函数 $v$ 映射为有界连续函数 $Tv$, 即 $T:C(X)\to C(X)$.

$\square$

故而, 值函数迭代的过程可以总结成如下的过程:

1.	任意定义一个连续的迭代起点 $v$ (例如 $v(x)\equiv 0$);
2.	使用 Bellman 算子 $T$ 作用于 $v$ 获得 $Tv$;
3.	计算 $d_{\infty }(v,Tv)$;
4.	若 $d_{\infty }(v,Tv)=0$, 则停止迭代, $v^{\ast }=Tv$; 若 $d_{\infty }(v,Tv)\ne 0$, 则将 $Tv$ 赋予 $v$ 进行更新, 重复 2–4 的步骤.

通过计算机程序的迭代, 我们可以设计程序求出给定的 $F$ 函数对应的值函数 $v$. 如下是一些关于值函数 $v$ 的性质, 可由 Banach 不动点定理的变体得出:

推论 2.3.2 (值函数的性质).

在特定条件下:

1.	若 $F(x,y)$ 是 (严格) 凹 (concave) 的, 则 $v(x)$ 也是 (严格) 凹的;
2.	若 $F(x,y)$ 是 (严格) 递增的, 则 $v(x)$ 也是 (严格) 递增的;
3.	若 $F(x,y)$ 是连续可微 (continuously differentiable) 的, 则 $v(x)$ 也是连续可微的;
4.	$v(x)$ 对应的策略函数 $g(x)$ 也是连续且递增的.

2.4待定系数法: 徒手解法

在计算机发明之前, 只有一些特定形式的 $F(x,y)$ 可以通过徒手求解的方式找出 $v(x)$. 然而, 鉴于我们有 Banach 不动点定理保障 $v(x)$ 的存在性, 对于某些特定形式的 $F(x,y)$, 我们可以猜测其值函数取某一特殊的形式, 这时即可用待定系数法 (“Guess and Verify”) 进行求解.

例 2.4.1 (Brock-Mirman 模型的待定系数法).

Brock-Mirman 问题的 Bellman 方程是: $$v(k_t)=\underset{0\le k_{t+1}\le A{k}_t^{\alpha }}{\max }\left\{\ln (A{k}_t^{\alpha }-k_{t+1})+\beta v(k_{t+1})\right\}$$(2.5)我们猜测值函数取得如下形式: $$v(k_t)=E+F\ln k_t$$(2.6)则方程右边: $$\begin{array}{rl}& \underset{0\le k_{t+1}\le A{k}_t^{\alpha }}{\max }\left\{\ln (A{k}_t^{\alpha }-k_{t+1})+\beta v(k_{t+1})\right\}\\ =& \underset{0\le k_{t+1}\le A{k}_t^{\alpha }}{\max }\left\{\ln (A{k}_t^{\alpha }-k_{t+1})+\beta [E+F\ln k_{t+1}]\right\}\\ =& \beta E+\underset{0\le k_{t+1}\le A{k}_t^{\alpha }}{\max }\left\{\ln (A{k}_t^{\alpha }-k_{t+1})+\beta F\ln k_{t+1}\right\}\end{array}$$一阶条件为: $$\begin{array}{rl}& -\frac{1}{A{k}_t^{\alpha }-k_{t+1}}+\beta F\frac{1}{k_{t+1}}=0\\ & k_{t+1}=\frac{\beta F}{1+\beta F}A{k}_t^{\alpha }\end{array}$$则 Bellman 方程变成: $$\begin{array}{rl}E+F\ln k_t& =\ln \left(\frac{1}{1+\beta F}A{k}_t^{\alpha }\right)+\beta \left[E+F\ln \left(\frac{\beta F}{1+\beta F}A{k}_t^{\alpha }\right)\right]\\ & =\left[\ln \left(\frac{1}{1+\beta F}A\right)+\beta E+\beta F\ln \left(\frac{\beta F}{1+\beta F}A\right)\right]+\alpha (1+\beta F)\ln k_t\end{array}$$则待定系数需要满足: $$\{\begin{array}{rl}E& =\ln \left(\frac{1}{1+\beta F}A\right)+\beta E+\beta F\ln \left(\frac{\beta F}{1+\beta F}A\right)\\ F& =\alpha (1+\beta F)\end{array}$$解得: $$\{\begin{array}{rl}E& =\frac{1}{1-\beta }\left[\ln ((1-\alpha \beta )A)+\frac{\alpha \beta }{1-\alpha \beta }\ln (\alpha \beta A)\right]\\ F& =\frac{\alpha }{1-\alpha \beta }\end{array}$$则带入策略函数有: $$k_{t+1}=g(x_t)=\frac{\beta F}{1+\beta F}A{k}_t^{\alpha }=\alpha \beta A{k}_t^{\alpha }$$(2.7)

有时, 待定系数法的值函数形式不好直接猜测. 我们可以 “借助” 迭代法的思想, 先将迭代起点设成 $v\equiv 0$ 迭代 1–2 期, 看少数几期迭代之后的 $v$ 中出现了怎样的函数成分, 再对值函数进行大胆猜测.