04第四章 动态规划.doc

第四章 动态规划初步 第一节 问题概览 一、问题的表述 与变分法和最优控制相比，动态规划处理离散时间与不确定性问题更有优势。在本章中，我们将简介在确定性下的动态规划的初步知识。我们从下面的问题开始： （P1） ， 对所有的时间 给定。 约束说明在时的值。是状态变量，可以看作是时的控制变量。所以该约束说明给定状态变量如何确定控制变量。是瞬时回报（实值函数），不独立依赖于时间。 我们是要得到最优值序列以使得最大，被称为最优计划（plan），是值函数。我们把问题P1的形式称为序贯（sequence problem）问题。显而易见，与初始的相关，即不同的会导致不同的最优值。下面是一个该问题形式的具体例子： 例1： ，给定。 该例子实际上就是代表性主体（或计划者）的Ramsey问题。该问题不是标准的P1问题的形式，但是我们可以将它转化成P1的形式： 其中，。对应P1式中：，。 序贯问题有时会有优美的特性，但是它一般很难解出也不利于数值运算。 动态规划的思想是将上面的序贯问题转化成函数方程（functional equation）的形式，即将原问题的寻找一个最优序列转化成寻找一个函数。函数方程为： （P2） P2为贝尔曼方程。在P2中，我们寻找一个策略(policy)，它决定给定时应为多少，即如何由状态变量确定控制变量。由于不依赖于时间，策略也不依赖于时间。我们以和分别表示状态和控制变量。这样，问题被表述成对任何选出适当的。从数学上看，这对应于对任何最大化。 下面是一个将问题P1转化成P2的具体例子（不是十分严格）： 上式将一个最优化问题分成两部分，一部分是对当前期的优化，一部分是对后续路径的优化。 如果已知最优策略函数为，则可得最优值函数： 或者我们可以从上式来寻求，如果求到了，则使P2最大化。后面的一些定理保证了我们在一定条件下从P2问题求出的解与从P1问题求出的解是一致的。这样，我们处理动态规划问题的步骤为：首先将P1转化为P2的形式，再在P2寻求最优策略函数。 二、一阶条件 我们从如下形式的P2问题开始求解一阶条件（欧拉方程）： （1） 求解一阶条件分为三步： 1、上式右边对控制变量求导所得一阶导数为0。如果、是标量，则有： （2） 2、对（1）式应用包络定理： （3） 3、结合（2）和（3）得到如下的一阶条件： （4） 其中，定义了，且由（3）是得到： （5） 把（5）式的结果代入（2）即得（4）中的欧拉方程。 除了以上结果外，我们也有一个TVC： 例2： 先写成递归形式： 由（2）得到： （6） 由（3）得到： （7） 令，则有一阶条件： 下面的关键问题是求出策略函数。我们猜想。 例3： 约束为： 首先将约束变形得： 从而原问题转化为P2形式： 其中为的下期值。 如果、不是标量，则（2）、（3）、（4）式依次为： 横截性条件为： 定理：如果下节的假设1—5成立，则满足一阶条件（4）与TVC的序列是原问题P1的解。 第二节 若干定理 本节说明P1和P2两个问题的解的关系（解的等价性），从P1的假设开始： 假设1：非空，存在且有限。 在经济问题中，我们一般不关注极限值无限的问题，主要原因是稀缺性。但无限问题仍可分析。 假设2：，是的紧子集，非空、紧且连续。令假设是连续的。 在内生增长模型中，资本存量无限，不是紧的。 假设1和2保证了我们在某个可行计划下P1和P2有最大值。我们的一般化结论可在假设1和假设2下得到。 假设3：是严格凹的，G是凸的。 这个假设在经济问题中也非常常见：约束是凸集，目标函数是凹或严格凹。 凹函数为： 且如果则取严格不等号。凸集定义为： 假设4：对每一对前个自变量（状态变量）严格递增。单调，即，单调意味着更大的有更多的选择。 假设5：G在域内是连续可微的。 以下是有关定理。 定理1：（值的等价性）：假定1成立，则对任一，P2都有唯一的值，它等于问题1（P1）中的。 这个定理告诉我们，P1和P2可以达到同样的值。但动态规划中我们关注的是最优计划，所以定理1在经济分析中几乎没有多大作用。下面的定理2更为重要。 定理2：（最优性原理）：假设1成立，令是P1中达到的一个可行计划，则： ① 对任，，且都成立。 而且，对于任何满足①式的，它都能在问题1中达到最优值。 其中是从开始的可行序列（或计划）。 对中的一个代表性元素。 由于P1中的的形式与P2中的形式相同，常省略，即①为： 这个定理告诉我们，要解P1问题可从P2开始，反过来也一样。 下面的几个定理说明了P