第四章 动态规划初步
第一节 问题概览
一、问题的表述
与变分法和最优控制相比，动态规划处理离散时间与不确定性问题更有优势。在本章中，我们将简介在确定性下的动态规划的初步知识。我们从下面的问题开始：
00(1)((0))((),(1))maxttxtVxUxtxt （P1）
.. (1)(())stxtGxt， 对所有的时间t
(0)x给定。
约束说明在()xt时(1)xt的值。()xt是状态变量，(1)xt可以看作是t时的控制变量。所以该约束说明给定状态变量如何确定控制变量。U是瞬时回报（实值函数），U不独立依赖于时间。
我们是要得到最优值序列0(1)txt以使得((0))Vx最大，0(1)txt被称为最优计划（plan），((0))Vx是值函数。我们把问题P1的形式称为序贯（sequence
problem）问题。显而易见，((0))Vx与初始的(0)x相关，即不同的(0)x会导致不同的最优值。下面是一个该问题形式的具体例子：
例1：(),()0max(())tctkttUct
.. (1)(())()(1)()stktfktctkt
()0kt，(0)k给定。
该例子实际上就是代表性主体（或计划者）的Ramsey问题。该问题不是标准的P1问题的形式，但是我们可以将它转化成P1的形式：
0(1)((0))((())(1)(1)())maxttktVkUfktktkt
.. (1)[0,(())(1)()]stktfktkt
其中，()(())(1)(1)ctfktktkt。对应P1式中：()()xtkt，(1)(1)xtkt。
序贯问题有时会有优美的特性，但是它一般很难解出也不利于数值运算。
动态规划的思想是将上面的序贯问题转化成函数方程（．．．．．．．．．．．．functional equation．．．．．．．．．．．．．．．．．．）．的形式．．．，即将原问题的寻找一个最优序列转化成寻找一个函数。函数方程为：
()()max(,)()yGxVxUxyVy （P2）
P2为贝尔曼方程。在P2中，我们寻找一个策略(policy)，它决定给定()xt时(1)xt应为多少，即如何由状态变量确定控制变量。由于U不依赖于时间，策略也不依赖于时间。我们以x和y分别表示状态和控制变量。这样，问题被表述成对任何x选出适当的y。从数学上看，这对应于对任何x最大化()Vx。
下面是一个将问题P1转化成P2的具体例子（不是十分严格）：
0((0))((),(1))ttVxUxtxt
1((0),(1))((1),(2))stUxxUxtxt
((0),(1))((1))UxxVx
上式将一个最优化问题分成两部分，一部分是对当前期的优化，一部分是对后续路径的优化。
如果已知最优策略函数为():xXX，则可得最优值函数：
()(,()(())VxUxxVx
或者我们可以从上式来寻求()x，如果求到了()x，则()yx使P2最大化。后面的一些定理保证了我们在一定条件下从P2问题求出的解与从P1问题求出的解是一致的。这样，我们处理动态规划问题的步骤为：首先将P1转化为P2的形式，再在P2寻求最优策略函数()yx。
二、一阶条件
我们从如下形式的P2问题开始求解一阶条件（欧拉方程）： ()()[(,)()]maxyGxVxUxyVy （1）
求解一阶条件分为三步：
1、上式右边对控制变量求导所得一阶导数为0。如果x、y是标量，则有：
(,)()0UxyVyy （2）
2、对（1）式应用包络定理：
(,)()UxyVxx （3）
3、结合（2）和（3）得到如下的一阶条件：
(,())((),(())0UxxUxxyx （4）
其中，定义了()yx，且由（3）是得到：
((),(())()(())UxxVyVxx （5）
把（5）式的结果代入（2）即得（4）中的欧拉方程。
除了以上结果外，我们也有一个TVC：
((),(1))lim()0()ttUxtxtxtxt
例2：
00(),(1)ln()maxtttctktct
.. (1)()()stktktct
0(0)0kk
先写成递归形式：
0()ln()()maxyVxxyVy
由（2）得到：
1()Vyxy （6）
由（3）得到： 1()xVxxy （7）
令()yx，则有一阶条件：
1()1()(())xxyxx
下面的关键问题是求出策略函数。我们猜想()xax。
1(1)21()axxaxaxaaxaxax
,()axx
(1)()ktkt
()1()ctkt
例3：
00(),()(())maxttctatUct
约束为：(1)()()()atRatwtct
首先将约束变形得：
1()()()(1)ctatwtRat
从而原问题转化为P2形式：
10()()()maxbVaUawRaVb
1()()0()()()RUcVbVaUVbUc
()()UcRUc
其中c为c的下期值。
如果x、y不是标量，则（2）、（3）、（4）式依次为：
(,)()0yxUxyVy
()(,)xxVxUxy (,())(),(())0yxUxxUxx
横截性条件为：
()lim((),(1))()0txttUxtxtxt
定理：如果下节的假设1—5成立，则满足一阶条件（4）与TVC的序列(1)xt是原问题P1的解。
第二节 若干定理
本节说明P1和P2两个问题的解的关系（解的等价性），从P1的假设开始：
假设1：()Gx非空，0lim((),(1))nttnUxtxt存在且有限。
在经济问题中，我们一般不关注极限值无限的问题，主要原因是稀缺性。但无限问题仍可分析。
假设2：()KxtXR，X是KR的紧子集，G非空、紧且连续。令(,):()GXxyXXyGx假设:GUXR是连续的。
在内生增长模型中，资本存量无限，X不是紧的。
假设1和2保证了我们在某个可行计划x下P1和P2有最大值。我们的一般化结论可在假设1和假设2下得到。
假设3：U是严格凹的，G是凸的。
这个假设在经济问题中也非常常见：约束是凸集，目标函数是凹或严格凹。
凹函数为：
(,)(1)(,)(,)(1)(,)UxyxyUxyUxy
且如果xx则取严格不等号。凸集定义为：
:(),()(1)(1)GyGxyGxyyGxx
假设4：对每一,(,)yXUy对前K个自变量（状态变量）严格递增。G单调，即()()xxGxGx，G单调意味着更大的x有更多的选择。
假设5：G在域内是连续可微的。
以下是有关定理。
定理1：（值的等价性）：假定1成立，则对任一xX，P2都有唯一的值()Vx，它等于问题1（P1）中的()Vx。
这个定理告诉我们，P1和P2可以达到同样的值。但动态规划中我们关注的是最优计划，所以定理1在经济分析中几乎没有多大作用。下面的定理2更为重要。 定理2：（最优性原理）：假设1成立，令((0))xx是P1中达到((0))Vx的一个可行计划，则：
① (())[(),(1)]((1))VxtUxtxtVxt
对任0t，1，且(0)(0)xx都成立。
而且，对于任何满足①式的((0))xx，它都能在问题1中达到最优值。
其中(())xt是从()xt开始的可行序列（或计划）。
(())():(1)(()),stxtxsxsGxs对,1stt(())xt中的一个代表性元素((0),(1))(())Xxxxt。
由于P1中的V的形式与P2中V的形式相同，常省略，即①为：
(())((),(1))((1))VxtUxtxtVxt
这个定理告诉我们，要解．．．．．．．．．．．P1．．问题可从．．．．P2．．开始，反过来也一样．．．．．．．．．。
下面的几个定理说明了P2中V的特征。
定理3：假设1和2成立，则存在一个唯一的连续有界函数V：XR满足P2，且对作任一(0)xX存在一个最优计划((0))xx。
这个定理（结合定理1）保证了P1中V的唯一性。而且最优解总是存在的，但不能保证唯一性（这要结合假设3）。
定理4：（值函数的凹性）：假设1、2和3成立。唯一的V是严格凹的。
由定理4和3有：
推论：假设1、2和3成立，存在唯一的最优计划，((0))xx（对任一(0)x），而且(1)(())xtxt，是连续的策略函数。
由于x是唯一的，确实是函数而不是对应关系。推论说的是解的唯一性。
定理5（值函数的单调性）：假设1、2和4成立，V是问题2的唯一解，V对其自变量严格递增。
定理6（值函数的可微性）：假设1、2、3和5成立，为策略函数，(),()(),()xINTXxINTGxVx在x处连续可微。()INTX表示在集合X的内
