动态规划与随机控制

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

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

3、先逆向考虑一个简单的问题就是假 如你只面对 2 个人的情况，当你只碰到倒数第一个人时，我们认为他的财富期望值为0.5，我们知道，你将选择与倒数第二个对象结婚时只有在他的财富值大于 0.5 的情况下，否则你 将与倒数第一个对象结婚。一般的，我们用VN表示倒数第一个人的财富期望值，用 WN 1表示表示倒数第二个人的财富值， 假设你的最优行动时在倒数第二步， 则倒数第二个人的财富 期望值为：VN 1 PN 1 E WN 1 WN 1 VN (1PN 1) VN这里 PN 1 P(WN 1 VN )一般的倒向递推公式就是：设 Pk P(Wk Vk 1),VNE(WN )VkPkEWkWkVk1(1Pk )Vk 1(1)k N 1 1Wk 是倒数第 k 个人的财富值， Vk是你在倒数第 k 阶段的最优策略的财富期望值。 如果我们把取 N 10，则此时我们可以算出 V1 0 8612.连续型动态规划问题确定性控制问题给定 x0， 考虑一个如下控制问题x(t) b(t x(t) u(t) ae t 0 Tx(0) x0( 2)u() 0T U是允许控制集， A0 T u() 在0 T上可测 , U

4、是一个度量空间 , T 0,b 0 T U 为一给定的映射 .则最优控制问题就是在控制系统( 2)的条件下极小化如下成本函数TJ(u() 0 f(t x(t) u(t)dt h(x(T) over A0 T(3)对于给定的映射 f 和 h。值函数的确定设 (s y) 0 T)；在区间 s T 考虑以下控制系统：x(t) b(t x(t) u(t) ae t sT x(s) y 这里控制 u() AsT u()|u()是区间sT 上可测函数。 则成本函数就是如下函数：TJ(s yu() f(t x(t) u(t)dt h(x(T)s现在我们来定义如下形式的值函数：V(sy) infu() AsTJ(syu() for any(s y) 0T)V(T y) h(y)(4)这里值函数就是在允许控制集的范围内， 找出所有成本函数中的极小化函数并且满足一定的 终止条件的函数。定理 1.贝尔曼最优化原理 假设 U 是可分的度量空间 , f 和 h 是一致连续，并且存在常数 L 0 使得对于(t x u) b(t x u) f (t x u) h(x) ， | (t x u) (t x?u)| L|

5、x x?| 有 | (t 0 u)| L for any t 0 T x x? u U(s y) 0 T) 0 s s? T 则对于任何 和任意 有： V(s y) infu As s? s f (t x(t) u(t)dt V ( s? x(s? u( )s( 5)方程( 5)就是我们通常所讲的动态规划方程。也就是说，全局最优一定导致局部最优，这 也是贝尔曼原理的精髓。1 定理 2. HJB equation 如果值函数 V C1(0T )：则V 是如下带有终止条件的一阶偏微 分方程( HJB equation )的解vt inf b(t x u)vx f (t x u) 0v|t T h(x) (t x) 0 T(6) 定理的简要证明： 固 定 u U ， 让 x() 为控 制 u(t) u 的相应状 态轨 迹，由贝 尔曼 原 理 s?V(s y) s f(t x(t) u)dt V(sx(s?) ，由Vt b(t xu)Vx f t( xu ) 0：对 于任意 u U ，有Vt infu Ub(t x u)Vx f(t x u) 0 另一方面，对于任意 0 0 s s? T 当s

6、? s 0充分小， 存在 u() u s?() As T使 s?得V(s y) (s? s)s f (tx(t) u(t)dt V(s x(s?)，这也 就 有Vti n u fbU tx(xu )V f txu。例：考虑如下系统3x(t) x3(t) u(t), 目标函数为1 t f 2 2 J 12 0f (x2 u2)dtx(0) x0解：根据以上分析，系统的拉格朗日型值函数为1H(x,u, ,t) 2 x2 1u 2 u x32可以得到H(x,21 V 2 V 3x2 x x则 HJB equation 为2V 1 V 2 V 3xt 2 x x20V(x(t),t)若优化区间为无穷的大，则我们求解以下微分方程：为了求解上述非线性微分方程，将V(x) p0 令 n=4 ，则得V(0) 0V(x) 展开成如下级数形式：2p1x 2! p2x231! p3x3 41! p4x4p0 p1 p3 0 p2 1 p4 6所以最优控制作用为dV 3u(t) (t) x x3 闭环系统为 dxx x3(t) u(t) x3(t) x(t) x3(t) x(t)随机控制问题 设 Z(t) 为

7、一布朗运动，我们考虑如下随机控制系统：7)dx(t) b(t x(t) u(t)dt (t x(t) u(t)dZ(t) t 0 Tx(0) x0定义区间 0 T上可测的允许控制集 A0 T u()，和 Ftt 0是适应的，最优随机控制问 题就是如下允许集 A0 T 下的成本函数TJ(u() E 0 f(t x(t) u(t)dt h(x(T)8)值函数就是如下系统下的极小化函数：设 (s y) 0 T) n ，我们考虑区间 s T 上以下控制系统dx(t) b(t x(t) u(t)dt (t x(t) u(t)dZ(t) t sTx(s) y这里控制 u() As T ，成本函数是 J(s yu() E s f(t x(t) u(t)dt h(x(T) s我们定义值函数如下：V(s y) u()inAfsTJ(s y u( ) for any(s y) 0 T)V(T y) h(y)10)定理 3 .贝尔曼最优化原理 对于任意(sy) 0T) n和任意0 s s? T 有 s?V(s y) infu Ass?E s f(t x(t s y u() u(t)dt V(s?x(s?s

8、y u()s定理 4. HJB equation 如果值函数 V C1 2 (0 T n)：则V 是以下带有终止条件问题的解：12(t x u)vxx b(t x u)vx f (t x u) 0 2v|t T h(x) (t x) 0 T n11)3. Merton s problem我们假设市场上只有两类资产进行投资：无风险资产(银行储蓄)和风险资产(股票)它们的价格分别定义为 B(t)和 S(t) ，并且由以下方程决定：dB(t) rB(t)dtdS(t) S(t) dt dZ(t)( 12)这里 r 0是无风险利率；0 和0是常数分别称为股票的回报率期望值和波动率。现在我们考虑市场中的一个投资和消费组合问题，假设一个投资商具有初始财富W0 ，在时刻 t ，投资者拥有 (t) 份额风险投资和 W(t) (t) 份额无风险投资，而且他的消费率为C(t)，则 dW(t) rW(t) ( r) (t) C(t)dt (t)dZ(t)W(0) W0，(13)则投资问题就变成了求如下随机控制问题的最优解的问题了，sup E Texp( s)U(C(s)ds exp( T)U (W(T) () C() 0这里 U() 是效用函数。4. Exersice1、假设以上问题给定的效用函数是：求解默顿问题？2、计算这个问题的状态价格收缩因子？

《动态规划与随机控制》由会员工****分享，可在线阅读，更多相关《动态规划与随机控制》请在金锄头文库上搜索。