动态规划与随机控制

动态规划与随机控制1953年，R.Bellman等人，根据某类多阶段序贯决策问题的特点，提出了著名的最优性原理”在这个原理的指导下，他将此类多阶段决策问题转变为一系列的互相联系的单阶段决策问题，然后，逐个阶段予以解决，最后再形成总体解决。从而创建了求解优化问题的新方法——动态规划。1957年，他的名著《动态规划》出版。离散型动态规划离散型确定性动态规划在解决美式期权问题时，我们通常采用倒向递推的方法来比较即时执行价格与继续持有价格。这是利用动态规划原理的一个典型例子。RichardBellman在1953年首次提出动态规划原理.最优化原理：无论过去的状态和决策如何，相对于前面的决策侧所形成的的状态而言，余下的决策序列必然构成最优子策略.求解最短路径问题：来看下面一个具体的例子：我们要求从Q点到T点的最短路径其基本思想是分阶段求出各段到T点的最短路径:TOC\o"1-5"\h\zW:C1—T3III--W:B1—C1—T4II--III--W:A2—B1—C1—T7-I--II--III--W：Q—A2—B1—C1—T11Q--A3—B1—C1—T11Q--A3—B2—C2—T11从以上分析可以看出最短路径不唯一。最短路径解的特点-1、可以将全过程求解分为若干阶段求解；------多阶段决策问题-2、在全过程最短路径中，将会出现阶段的最优路径；-----递推性-3、前面的终点确定，后面的路径也就确定了，且与前面的路径（如何找到的这个终点）无关；-----无后效性-3、逐段地求解最优路径，势必会找到一个全过程最优路径。-----动态规划离散型不确定性动态规划离散型不确定性动态规划的特点就是每一阶段的决策不是确定的，是一个随机变量，带有一

定的随机性，因此处理起来就相对复杂些。一个动态规划的经典问题：你打算与一个你遇到的最富有的人结婚，你的最优策略是什么？这里做几点基本的假设：1、如果碰到满足你要求的人，他无条件接受；2、有N个人供你选择；3、每个备选对象的财富值都服从[0,1].区间上的均匀分布；那么你要找具有最大期望财富值的结婚对象的最优策略是什么?这是一个看似简单但是很难解决的问题.通常的方法是顺序递推法，如果首先考虑碰到第一个人的财富，接着考虑碰到下一个人的财富值与第一个人的财富值进行比较，依次进行下去，但是你期望下一个对象的财富值的确定是一个很复杂的问题，并且很难进行比较.因此这里我们考虑倒向递推的方法进行计算，我们首先逆向考虑一个简单的问题就是假如你只面对2个人的情况，当你只碰到倒数第一个人时，我们认为他的财富期望值为0.5，我们知道，你将选择与倒数第二个对象结婚时只有在他的财富值大于0.5的情况下，否则你…一W_将与倒数第一个对象结婚。一般的，我们用"n表示倒数第一个人的财富期望值，用^N-1表示表示倒数第二个人的财富值，假设你的最优行动时在倒数第二步，则倒数第二个人的财富期望值为：v=pxeW|N-1N-1v=pxeW|N-1N-1N-1这里P=P(W>V)一般的倒f向递推公式就是：w^1>in*1-%)x匕,P三P(W>V),=N=PxE[WIWE(W)>V]+(1-P)xV,k+1kk+1k=N-1,…,1,W是倒数第k个人的财富值，如果我们把取N=10，则此时我们可以算出匕=0.861Vk是你在倒数第k阶段的最优策略的财富期望值。2.连续型动态规划问题确定性控制问题给定X0G^，考虑一个如下控制问题fx(t)=b(t,x(t),u(t)),a.e.tg[0,T],[x(0)=x0,(2)u(•):[0,T]rU是允许控制集，A[0,T]={u(•)在[0,T]上可测},U是一个度量空间，T>0,b:[0,T]x沮xUr沮为一给定的映射.则最优控制问题就是在控制系统(2)的条件下极小化如下成本函数J("(•))=jTf(t,x(t),u(t))dt+h(x(T)),overA[0,T],(3)对于给定的映射f和h。值函数的确定设(s,y)e[0,T)x沮；在区间[s,T]考虑以下控制系统：Ix(t)=b(t,x(t),u(t)),a.e.te[s,T],1x(s)=y,这里控制u(•)e出s,T]={u(・)lu(•)是区间[s,T]}上可测函数。则成本函数就是如下函数：J(s,y;u(•))=jTf(t,x(t),u(t))dt+h(x(T)).s现在我们来定义如下形式的值函数：Iv(s,y)=infJ(s,y;u(•)),forany(s,y)e[0,T)湘<u(•倒[s,T]1v(T,y)=h(y).(4)这里值函数就是在允许控制集的范围内，找出所有成本函数中的极小化函数并且满足一定的终止条件的函数。定理1.贝尔曼最优化原理假设U是可分的度量空间，f和h是一致连续，并且存在常数L>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,foranyte[0,T],x,xe/,ueU.(s,y)e[0,T)x/0<s<s<T则对于任何f和任意有：IV(s,y)=inf>sf(t,x(t),u(t))dt+V(s,x(s;u(•)))!ueA[s,s]s(5)方程(5)就是我们通常所讲的动态规划方程。也就是说，全局最优一定导致局部最优，这也是贝尔曼原理的精髓。定理2.HJBequation如果值函数VeC1([0,T]x/):则v是如下带有终止条件的一阶偏微分方程(HJBequation)的解v+inf{b(t,x,u)v+f(t,x,u)}=0,<tueUxvl=h(x),(t,x)e[0,T]x/.t=T⑹定理的简要证明:固定ueU，让x(•)为控制u(t)三u的相应状态轨迹，由贝尔曼原理V(s,y)<V(s,y)<jsf(t,x(t),u)dt+V(s,x(?))，由V+b(t,x,uV+f(,x,u女tsueU，有V+inf{b(t,x,u)V+f(t,x,u)}>0另一方面，对于任意£>0,0<s<s<T当s-s>0充分小得V(s,y)+s(s-s)>jsf(t,x(t),u(t))dt+V(s,x(§))0对于任意存在u(•)三us(•)eA[s,T]这也就V+infb,t{,x(u+)V,f,t<xuteuUx。例：考虑如下系统;X(t)=X3(t)+u(t),X(0)=X0目标函数为”1J=Jf(X2+u2)dt1=—X2+—u2+人"一人X3221=—X2+—u2+人"一人X32TOC\o"1-5"\h\zdudx可以得到dV

dxudV

dxmdV_11dVH(x,)x2—dx22dx则HJBequation为dV1「dV12「dVdtdxX3+—X2=0dV(x(t),t)若优化区间为无穷的大，则—云dt我们求解以下微分方程：dV12」dVI八I+2dV1「dV12「dVdtdxX3+—X2=0dV(x(t),t)若优化区间为无穷的大，则—云dt我们求解以下微分方程：dV12」dVI八I+2lIX3—X2=0dxIIdxIV(0)=0将V(x)展开成如下级数形式:1为了求解上述非线性微分方程，11,/V(x)=p+pX+——pX2+——pX3+——pX4+012!23!34!4令n=4，则得p=p=p=0013p2=1p=64所以最优控制作用为…dV°u(t)=一X(t)=一=一x+x3闭环系统为dXX=—X3(t)+u(t)=—X3(t)—x(t)+X3(t)=—x(t)随机控制问题设Z(t)为一布朗运动，我们考虑如下随机控制系统：dx(t)=b(t,x(t),u(t))dt+q(t,x(t),u(t))dZ(t),te[0,T],

x(0)=X0,(7)定义区间［0,T］上可测的允许控制集出0,T］=｛u(•)，和｛匕｝,>0是适应的，最优随机控制问题就是如下允许集A［0,T］下的成本函数'湖(8)(9)设(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),tg[s,T],Ix(s)=y,{}这里控制u(•)GA[s,T],成本函数是J(s,y;u(•))=E"Tf(t,x(t),u(t))dt+h(x(T))'我们定义值函数如下：V(s,y)=infJ(s,y;u(•)),forany(s,y)g[0,T)x沉n"(•)gA[s,T](10)V(T,y)=h(y(10)定理3.贝尔曼最优化原理对于任意(s，y)G[。,T)x宙n和任意0<s<拦T有V(s,y)=infEJsf(t,x(t;s,y,u(•)),u(t))dt+V(s,x(顶;s,y,u(•)))'ugA[s,s]亍定理4.HJBequation如果值函数VgC1,2([0,T]x宙n):则V是以下带有终止条件问题的J_1,解v+inf{"2©2(t,x,u)v+b(t,x,u)v+f(t,x,u)}=0,vl=h(x),(t,x)g[0,T]x宙n.(11)3.Merton’sproblem我们假设市场上只有两类资产进行投资：无风险资产(银行储蓄)和风险资产(股票),它们的价格分别定义为B(t)和S(t)，并且由以下方程决定：JdB(t)=rB(t)dt,(12)IdS(t)=S(t)"t+bdZ(t)],这里r>0是无风险利率；u>0和。>(12)现在我们考虑市场中的一个投资和消费组合问题，假设一个投资商具有初始财富W。，在时刻t，投资者拥有兀(t)份额风险投资和W(t)-兀(t)份额无风险投资，而且他的消费率为JdW(t)=