动态规划与随机控制

1、动态规划与随机控制1953年，R . Bellman等人，根据某类多阶段序贯决策问题的特点，提出了著名的最 优性原理”在这个原理的指导下，他将此类多阶段决策问题转变为一系列的互相联系的单阶 段决策问题，然后，逐个阶段予以解决，最后再形成总体解决。从而创建了求解优化问题的 新方法动态规划。1957年，他的名著动态规划出版。离散型动态规划离散型确定性动态规划在解决美式期权问题时，我们通常采用倒向递推的方法来比较即时执行价格与继续持有 价格。这是利用动态规划原理的一个典型例子。Richard Bellman在1953年首次提出动态规 划原理.最优化原理：无论过去的状态和决策如何，相对于前面的决策侧所

2、形成的的状态而言，余 下的决策序列必然构成最优子策略.求解最短路径问题：来看下面一个具体的例子：我们要求从Q点到T点的最短路径其基本思想是分阶段求出各段到T点的最短路径: TOC o 1-5 h z W : C1T3III -W : B1C1T4II-III-W : A2B1C1T7-I-II-III -W：QA2B1C1T11Q-A3B1C1T11Q-A3B2C2T11从以上分析可以看出最短路径不唯一。最短路径解的特点-1、可以将全过程求解分为若干阶段求解；-多阶段决策问题-2、在全过程最短路径中，将会出现阶段的最优路径；-递推性-3、前面的终点确定，后面的路径也就确定了，且与前面的路径（如

3、何找到的这个终 点）无关；-无后效性-3、逐段地求解最优路径，势必会找到一个全过程最优路径。-动态规划离散型不确定性动态规划离散型不确定性动态规划的特点就是每一阶段的决策不是确定的，是一个随机变量，带有一定的随机性，因此处理起来就相对复杂些。一个动态规划的经典问题：你打算与一个你遇到的最富有的人结婚，你的最优策略是什 么？这里做几点基本的假设：1、如果碰到满足你要求的人，他无条件接受；2、有N个人供你选择；3、每个备选对象的财富值都服从0, 1.区间上的均匀分布；那么你要找具有最大期望财富值的结婚对象的最优策略是什么?这是一个看似简单但是很难 解决的问题.通常的方法是顺序递推法，如果首先考虑碰

4、到第一个人的财富，接着考虑碰到下一个人 的财富值与第一个人的财富值进行比较，依次进行下去，但是你期望下一个对象的财富值的 确定是一个很复杂的问题，并且很难进行比较.因此这里我们考虑倒向递推的方法进行计算，我们首先逆向考虑一个简单的问题就是假 如你只面对2个人的情况，当你只碰到倒数第一个人时，我们认为他的财富期望值为0.5， 我们知道，你将选择与倒数第二个对象结婚时只有在他的财富值大于0.5的情况下，否则你 一W _ 将与倒数第一个对象结婚。一般的，我们用n表示倒数第一个人的财富期望值，用N-1表 示表示倒数第二个人的财富值，假设你的最优行动时在倒数第二步，则倒数第二个人的财富 期望值为：v =

5、 p x e W |N-1N-1N-1这里 P = P(W V ) 一般的倒f向递推公式就是：w 1 in *1 - %) x 匕,P 三 P(W V ),=N= P x EW IWE (W ) V + (1-P ) x V ,k+1k k+1k = N -1,1,W是倒数第k个人的财富值，如果我们把取N = 10，则此时我们可以算出匕=0.861Vk是你在倒数第k阶段的最优策略的财富期望值。2.连续型动态规划问题确定性控制问题给定X0 G，考虑一个如下控制问题f x(t) = b(t, x(t), u(t), a.e. t g 0, T, x(0) = x0,(2)u(): 0,T r U是

6、允许控制集，A0,T = u()在0,T上可测, U是一个度量空间， T 0,b: 0,Tx沮x U r沮为一给定的映射.则最优控制问题就是在控制系统(2)的条件下极小化如下成本函数J() = j T f (t,x(t),u(t)dt + h(x(T), over A0,T,(3)对于给定的映射f和h。值函数的确定设(s, y) e 0,T)x沮；在区间s,T考虑以下控制系统：I x(t)= b(t, x(t), u(t), a.e. t e s, T,1x (s) = y,这里控制u() e出s,T = u()lu()是区间s,T上可测函数。则成本函数就是如下函数：J(s, y; u() =

7、 j T f (t, x(t), u(t)dt + h(x(T).s现在我们来定义如下形式的值函数：Iv(s, y) = infJ(s, y; u(), for any (s, y) e 0, T)湘 0使得对于4 (t, x, u) = b(t, x, u), f (t, x, u), h(x)，l4(t, x, u) 一4(t, x, u)l Llx 一 xi,l顿t,0,u)l L,for any t e 0,T, x, x e/, u e U.(s, y) e 0, T) x/0 s s s f (t, x(t), u (t )dt + V (s, x (s; u ()!ueAs,s

8、s( 5)方程(5)就是我们通常所讲的动态规划方程。也就是说，全局最优一定导致局部最优，这 也是贝尔曼原理的精髓。定理2. HJB equation如果值函数V e C1(0,Tx/):则v是如下带有终止条件的一阶偏微分方程(HJB equation)的解v + infb(t, x, u )v + f (t, x, u) = 0, t ueUxvl= h(x), (t, x) e 0,T x/.t=T定理的简要证明:固定u eU，让x ()为控制u (t)三u的相应状态轨迹，由贝尔曼原理V(s, y) 0另一方面，对于任意 0,0 s s 0充分小 得V (s, y) + s (s - s)

9、j s f (t, x(t), u (t)dt + V (s, x()0对于任意存在u ()三 u s () e As, T这也就V + i nfb,t,x(u+)V,f,t 0是适应的，最优随机控制问 题就是如下允许集A0,T下的成本函数湖(8)(9)/ () = E fy(, X。),u (脚 + hx(T)J值函数就是如下系统下的极小化函数：设(s, y) g 0,T) x宙n，我们考虑区间s,T上以下控制系统 Jdx(t) = b(t, x(t), u(t)dt + b (t, x(t), u(t)dZ(t), t g s, T,Ix( s) = y,这里控制 u() G As,T,成

10、本函数是 J(s, y;u() = E T f (t,x(t),u(t)dt + h(x(T)我们定义值函数如下：V(s, y) = inf J(s, y;u(),for any (s, y) g 0,T)x沉n()gAs,T (10)V (T, y )=h( y).定理3 .贝尔曼最优化原理 对于任意(s，y)G。,T)x宙n和任意0s0是无风险利率；u0和。0是常数分别称为股票的回报率期望值和波动率。现在我们考虑市场中的一个投资和消费组合问题，假设一个投资商具有初始财富W。，在时 刻t，投资者拥有兀(t)份额风险投资和W(t)-兀(t)份额无风险投资，而且他的消费率为J dW (t) = rW (t) + (日一r )兀(t) - C (t )dt +。兀(t )dZ (t) TOC o 1-5 h z C(t)，