论文研究-动态规划问题研究 .pdf,
系统工程理论与实践 2007年8月 ()=x( 中(籴(1),(1),(…,((T-1),公(T-1),可(籴(D)…) d(x(),u(t),(…,中(x(T-1),(T-1),中(X(D)…) 成立,则对任何使☆(t)=x(t)=H-1(x(t-1),u(t-1))得到满足的(x(t-1),u(t-1))我们有, 小(x(t-1),u(:-1),(全() q(…,中((7-1),分(7-1),(分(T))… ≤(x(t-1),n(t-1),(x(t),(),(…,(x(7-1),n(T-1),(x(T)…) 多日标动态规划最优性原埋:如果多目标动态规划问题(MDP满足后向可分和后向单调,那么,对 任何非劣控制序列而言,不论前面决策形成的状态如何,余下的控制子序列对当前的状态也必定构成一非 劣控制策略 我们也能类似定乂前向可分性和前单调性以建立前向多目标动态规划理论.但计算前向多目标动 态规划理论要求动态系统能够逆转表小,而且前间动态规划方法不适用随机情况.因此,传统上,多数多目 标动态规划理论是针对后向可分和后向单调建立的. 个常用的求解多目标优化问题(MP)的非劣解的方法是加权法.通过加权法把多个目标转化为单 目标的加权和.然而,加权法在般情况下并不适用,因为只要有个目标不是可加型,多个后向可分函数 之加权和即是不可分的因此,以下介绍的包络法应运而生 令E=啪(x(),v(),(…,中(x(了-1),n(T-1),(x()…),=1,2,…,k,为第r个目 标从x(1)到x(T)的cos-torg 假定在x(t+1)的书劣前沿可以表示为: E1 E1(x(t+1)) E2#(x(t+1)9) (x(t+1)) 其中是(k-1)维参数向量那么,对于给定的x(t),由k个目标形成的超曲面族为 E1=(x(t),n(t),1(H(x(t),n(t)月) E2=4(x(t),u(t),E2(B(x(t),())9) E=(x(t),u( t)) 其屮,u(t)可视为族参数 从图1中可以清楚看到,如果上述的超曲面族是正则的,那么,对于给定的x(t),求多目标问题的非 劣解等价于求超曲面族的包络,即, a(,E,…B_OE0(E c(1 102, 04.1)a(t)a(102,…k-1)an(t) +(.1)k:1a(E1,E,…E1)E 0, 0 Cu(t 如解方程(2)能把u(t)表小成x(1)和θ的函数,那么,有如下表达式 E=E'(x(t)日) x(t)e (x(t)日 这样就产生了求解MmP的回归方程.因此我们有下面求解(MP)的包络方法: At Stage T:对于给定的x(n),计算k个目标函数值 中=“(x() 91994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreservedhttp://www.cnki.net 第8期 动态规划问题矿究 59 x(t1) 图 的包络 At Stage T-1:对于x(r-1),求解下面多目标优化问题 (T 1),v(r·1),中(H1(x(T-1),n(T-1)) (x(T-1),v(r-1),(H121(x(T-1),v(T-1))) min 中(x(T-1),a(T-1),中(11(x(T-1),u(T-1)) s.t.x(m)=Hr:1(x(T-1),t(T-1)) 以产生位于x(T-1)的丰劣前沿的参数形式 (x(r-1)6) E2=E2(x(T-1)6 El'(x(T-1)0 其中日为参数,可以是加权 Lagrangian法中的权向量,或E约束法中的向量 At Stage t:对于给定的x(t)(0≤t≤T-2),求解包络方程(2),进而求出(3) 完成t从T-2到0的递推迭代,则位于x(0)的非劣前沿对应原问题(MDP)的非劣前沿 可参考文献[5]了解关于求解多目标优化问题包终方法的更多细节 3自适应微分动态规划 珪论上,包络法能够求解具有可分结构的一般多目标最优控制冋题,它不要求冋题有凸结构、也不扩 大状态空间然而技术上遏到的困难就是在求解包络方程門,很难得到解析解.为此,需要进行离散化,求 出数值解,然后再通过诸如最小二乘之类的拟合技术,获得个不精确的解析解.这样,多目标最优控制问 题中的动态规划维数灾常常会变得史严重 自适应徽分动态规划是微分动态规划在多目标最优控制中的推广.为讨论方便,我们以另一种 形式直接给出多目标最优控制问题 (P) min f(X, U)=[ f(X, U),2(X,U),",f(X,U] s.t.x(t+1)=H(x(t),v(t),t=0,1,…,T-1,x给定 91994-2009chinaAcademicJournalElectronicPublishingHouse.Allrightsreservedhttp://www.cnki.net 60 系统工程理论与实践 2007年8月 其中,U=[u(0),'(1),…,l(7-1)],x=[x(0),x(1),…,x(n],x(t)∈R",u(t)∈R 假定问题(P)中所有的性能指标f(X,U是后向可分的,即,存在函数中:R×R×R→R,t=0 1,和中:R"→R,=1,2,…,k,使每个f(X,U)能够表示成如下的后向嵌套形式 中(x(T)) k (x(1),u(t),y),i-1,…,k;t (4) f i( X,D)=10 k 其中 以上假定(5)保证单调性条件得到满足 方程(4)能够写成如下更紧凑的形式 yr=吻(x(1)), 中(x(t),(1),y),t=T-1,…,0 f(X,)=y0, 其中 ,t=0 (x(T)=[喟(x(T),…,(x(T)], 中(x(1),u(),y1)=[(x(t),u(n),y),…,嗔(x(t),n(t),yk)],t=0,…,T-1, f(X,U)=[f1(X,U),…f(x,U)] 这里我们假定所有函数二阶连续可导 问题(P)包含了所有在动态规划意义下具有可分结构的多目标伏化问题每个性能指标f可以有不 同的形式,一个阶段到另一阶段的复合算子可以相同,也可以不同 令EZ={UU是(P的非劣解}为问题(P的非劣解集,如果U∈Ez,令X为相应的状态轨道那 么,根据最优性原理,非劣解U的子列(u^(t),…,l(T-1))也是下面问题的非劣解 (P(t)) min中(x(t),u(t),y+1) {a(),…,a(7-1)} s.t.x〔+1)=H(x(),u()=t,…,T-1,x(t)=x(t) 中(x(),u(T),1)T=r yr=中(x(7)) 定理181假定问题(P)和问题(P(1)是R4-凸的,U^∈Ez,X是对应的状态轨道那么,对所有t ,…,T-1,存在θ1≥0,i=1,2,…,k,使得U=[u'(t),…,u^(r-1)]是下面问题的解 (P2(t) fu(a) s.t.x〔t+1)=H(x(),u()),=t,……,T-1,x(t)=x(t) 计=中(x(),u(),+)x=T-1 yr=中(x(7)) 其屮θ′,i=1,2,…,k;t=0,…,T-1,满足下列方程: 此处所有的导数为相关函数在(U,X)处的导数值 除非向量目标函数J是阶段可加的,否则,最优权系数6是时变的由于在不同阶段权向量是时变 的,所以,(P(1)中的目标函数也是时变的因此,目标函数∑不能表示成回归的嵌套形式为了回 91994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreservedhttp://www.cnki.net 第8期 动态规划问题矿究 归地求解多阶段优化问题,必须记录∞stog.对于组给定的>0,求P(0)的解U,就能产生Ez 的一个子集 基于以上讨论我们能发展出自适应徽分动态规划方法显然,在阶段t日(=1,2,…,k)的选择,将 影响以后各阶段的解.因此,我们将增广状态空间,使θ成为状态向量,并随状态变量的变化而变化.作如 下定义 6:=θ1,…∪',t=0,…,T, ∧,=diag(1,…入x), 0 其中 入 k 增加(6)为问题(P2(1))的一个约束,我们有下面的问题 P(t)) min ,) T+1 H(x(t),ut)) ∧a x()和日,给定 中(x(℃),u(T),t+1),T t yr=中(x(7)) 问题(P(t)中存在三种状态转移结构:1)变量ν(t=T-1,T-2,…,0)具有后向嵌套转移结构;2)变量 x(t)具有前向转移结构;3)变量θ,具有混合转移结构.对于给定的∧月,具有前向结构,而∧,又由后向 回归关系确定.于〔P3(ω))中的上述三种特姝结构,传统的微分动态规划策略无法直接应用,因此,我们」 需要一和新的微分动态规划方法,用自适应策略来克服目标函数在不同阶段有不同形式所产生的求解困 难.以下方法被称为自适应微分动态规划( Adaptive Differential Dynamic Programming:ADDP) 1)对于给定的控制序列U,用ADDP计算一个新的控制序列U,使(P(0)的目标函数值小于当前的 目标函数值.这个过程迭代进行,直至停止条件满足. 2)ADDP的每次迭代包含两个工作过程—反馈过程和校正过程.对于给定的簧略U和相应的轨 道,如果U是(P(1)的一个新的策略,是对应的轨道,定义: △v(t)=u()-u(t),t=0,…,T △ T 在反馈过程中,从阶段T-1开始,反向计算反馈函数△u(t)=屮(△x(t),在阶段0结束.在每个阶 段,问题(P3(t)被近似求解,以获取反馈函数△v(t)=ψ(△Ax(1) 校正过程:a)把新导出的反馈函数用于动态系统,前向求出状态x(1)和v(t);b)用新得到的x(t) n(),反向求出y和∧,:c)用新得到的∧,,前向求出e 定理2对于任意给定的控制U,假定水平集S(U)有界.令{U}是ADP算法产生的控制 列,则{U“}的任何极限点是问题(P3(0)标函数)y0的稳态点 可参考文献[8]发现关于求解多目标最优控制问题自适应微分动态规划方法的更多细节 4不可分多阶段决策问题 考虑下面的具有不可分结构的单目标多阶段优化问题 (N)minf=f[x(1),…,x(T),u(0),…,u(T-1)] s.t.x(t+1)=H(x(t),u(t),t=0,1,…,T-1,x(0)给定, 其中,H,t=0,1,…,T和∫在各自的定义域内可微 动态规划的显著特点就是在性能指标∫满足后向可分和后叵单调条件时,能够把个多阶段决策问 o1994-2009ChinaAcademicJournalElectronicpUblishingHouse.Allrightsreservedhttp://www.cnki.net 62 系统工程理论与实践 2007年8月 题分辉成系列单阶段决策问题然而,许多实际遇到的序列决策问题,本身的结构是不可分的.直觉上动 态规划方法似乎不能宜接用于解决这类问题.下面讨论这类问题在动态规划框架下的求解方法 定义在问题(N)中,性能指标∫是k次可分的,如果∫能够被分解成下面的形式 其中Φ对每个〃严格递增,=1,2,…,k,而且每个f是后向可分的,即存在函数中和, :R×R”×R→R,=0,1,…,T-1;中:R"→R 使得 f1=(x(0),a(0),(x(1),n(1),(x(2),u(2),…,中(x(T-1),v(T-1),中(x()…)), 除此之外,还假定每个f是后向单调的这里我们假设k是最小次数,即不存在小于k的s,使得f=中 (f,…f).显然,传统意义下的可分性能指标,在以上定乂下可被视为是1次可分的 注意到如果某些∫前向可分,则可引进新状态变量我们然后可以用它在最终时间段的值在目标函 数中取代∫ 例不可分性能指标 14 (0)+n2(1)-n(1)a2(2)] 是二次可分的我们可以选择 f1 (1)u(2) 如果一个不可分问题(N)是k次可分的,我们可考虑构造以下对应的多目标优化问题 4(x(0),v(0),(x(1),n(1),…,将(x(T-1),n(7-1),(x(m)…) 3=或(x(0),n(0),(x(1),(1),…,(x(T-1),n(T-1),(x(n))…) S IIIn f=哦(x(0),u(0),(x(1),u(1).…,(x(T-1),u(T-1),(x(m))…) .t.x(t+1)=H(x(t),u(t),t=0,1,…,T-1,x(0)给定 定理3不可分问题(N)的最优解一定是多目标可分问题(S)的一个非劣解 定理4如果问题(S)县有凸结构,那么,问题(N的最优解(X,U)为以下的加权问题的最优解, (W) min f, (x, U) (t+1)=H(x(t),u(t),t=0 1,x(0)给定 其中权系数入满足 入 入 入 上述两个定理给出了原不可分问题(N)的最优解和对应的可分多目标问题(S)的非劣解之间的关系.即使 问题有凸性,除非(S)中每个目标函数都具可加性,则,加权和∑A是不可分的因此在一般情况下, 需用前面介绍的包络法对可分多目标问题(S进行求解才为合适 可参考文献[6,7]阅读本芍介绍的关于不可分动态规划问题求解方法的更多的细节 5多阶段均值-方差框架下的投资组合问题 № Markowitz上世纪五十年代提岀单阶段投资均值-方差模型,运用方差来度量投资中的凤险,在金融理 论与实践中产生了巨大影响. Markowitz并以此获得了1990年的诺贝尔经济学奖 但是将 Markowitz单阶段均值-方差组合投资的结果推广到多阶段动态框架下的企图,在过去的四十 多年里遇到了很多困难,屡屡得不到成功其中最主要的原因是没认识到传统动态规划方法对于方差极小 化问题的不适用性,基于文献[6,7屮处理不可分优化问题的思路,这一问题在参考文献[9]得到彻底解 决我们在这节中介绍在参考文献[9]中取得的突破. o1994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreservedhttp://www.cnki.net 第8期 动态规划问题矿究 63 我们考虑个有n+1个证券的资本市场.拥有x财富的投资者在0时刻进入市场.投资者能够在 T-1个时间阶段的每个阶段开始时重新在n+1证券之间进行财富分配.在t阶段,我们用e=[e,e, e]来表示风险证券的随机回报向量,其中,e是第i个证券在t阶段的随机回报我们这里假定向量 e(t=0,1,…,7-1)统计独立,且均值为E(e)=LE(e),E(e1),…,E(e)」,方差为 令x,为投资者在t时刻的财富,u(i=1,2,…,n)为在t阶段开始时投资于第讠个证券的财富数量.在均 值ˉ方差模型下,投资者的最佳策略是寻求v=[u,u,…,l"](l=0,1,2,…,T-1)求解以下问题, (E(w)): max E(xn)- wVar(xr) 其中 P]=[ 及w∈[0,∞代表投资者在终端财富期望与相应风险之间的权衡系数.对投资者来说,提供这样一个主观 确定的ν,比构造终端财富的效用函数,吏容易理解与操作.而改变问题(E(w))中的ν值,就能产生组合 投资策略的有效集合(非劣集合). 问题(E(w)在动态规划的意义下是不可分的,原因如下.令1是t时刻的信息集我们有c Vt.一个重要的事实是期望算子有光滑性质 F[F(1)r]=F(11),V>k 而上述性质对于方差则不成立,則, Vi>k 所以,方差最小化是随机控制中的个长期棘手难题.我们无法直接应用动态规划求解(E(w)) 参考文献[叨中采用求解策略把问题(E(ν)嵌入到一个可分的辅助问题中,研究问题(E(ν)的解 与辅助问题解集的关系,从而在辅助间题的解集中搜索(κ(ν))的最优解 对于给定的w,定义问题(E(w)的最优解集为∏g(v),即 e(w)=TI T is a maximizer of (E(w))3 问题(E(w))的目标函数可以看成是E(xr)和E(x)的函数 0(E(x2),E(x)=E(x7)-wVar(x)=-wE(x27)+wE2(x)+E(xr) 显然,元是E(x2)和E(x)的凸涵数对间题(E(w),我们构造下面的辅助问题 (Aa, w): max E(- wx7+Xxi 0,1.2,…,T-1 辅助问题(A0,m)的显著特点是:在动态规划的意义下,(A0A,w)是可分的,同时,(A0A,w)目标函数 具有二次形式,而且系统的动态结构是线性的 时于给定的入和w,定义n4A,w)为问题(AA,w))的最优解集, n,a, w)=TT is a maximizer of (A, w))) d(n, w)- OU(E(XT, E(xn)) OE(xr) 1+2wE(x)|r 定理5如果Tn(v),则π((d(T,w),n) 上述定理的含义是:问题(E(w))的解集是问题(4^,w))的解集的子集这样,我们能够把难于处理 的不可分问题(E(w))入到易于处理的可分辅助问题(A,w)中 定理6假定TnAA,w),则T∈n(w)的必要条件是入=1+2vE(x)n 91994-2009ChinaAcademicournalElectronicPublishingHouse.Allrightsreservedhttp://www.cnki.net 系统工程理论与实践 2007年8月 辅助问题(Aλ,w)的最优解,能够用动态规划得到特别是终端财富的期望与方差,E(x),Var(κr) 都可表示为入的解析函数利用定理6我们可以预先求得入的最优值入∵.综上所述,辅助问题(AA w)的最优解给出问题(E(w))的解. 本节内容的更多细节可参考文献[9].用嵌入法解决动态投资问题在[14]中被进步用来控制投资过 程中的破产概率. 6结论 亳无疑义,动态规划是解决可分序列决策问题的最有效方法之一,也是对随机控制问题求解反馈策略 的唯一通用方法.在过去的一些年中,动态规划取得了不少可喜的进展虽然在克服被 Bellman称之为“维 数灾”的动态规划致命弱点的方面有一些工作10-,但是至今尚未取得突破性的进展所以当前一个 紧迫的研究课题是寻求克服维数灾的有效算法以能让动态规划在高维问题屮得到有效应用.其屮一个急 需解决的课题是动态规划在大规模可分非线性整数规划中的应用 可以想像求解不可分优化问题得到的最优策略并不满足最优性原理.这就是说,不可分优化问题的最 优策略不具备时间一致性.更深入想,这牽涉到不可分优化问题模型本身的合理性.因此怎样找岀(一纽) 可分优化问题来逼近一个给定的不可分优化问题具有它显然的重要性 参考文献: [1 Jacobson D Mayne D Differential Dynamic Programming[M]. Elsevier, New York, 1970 [2 Johnson S A, Stedinger JR, Shoemaker C A. Numerical solution of continuous- state dynamic programs using linear and spline interpolation[J]. Operations Research, 1993, 41: 484 [3] Larson R E. Dynamic programming with reduced computational requirements[J]. IEEE Transactions on Automatic Control, 1965 10:135-143 [4 Larson R e, Korsak A J. Dynamic programming successive approximations technique with convergence proofs[J]. Automitica, 1970 6:245 [5] Li D, Haimes YY. The envelope approach for multiobjective optimization problems[J]. IEEE Transactions on System, Man and Cybernetics,1987,17:1026-1038 [6] Li D, Haimes Y Y New appmach for unseparable dynamic programming problems [J]. Journal of Optimization Theory and pplications, 1990, 64: 311-330 [7 Li D, Haimes Y Y. Extension of dynamic programming to nonseparable dynamic optimization problems [J]. Computer Mathematics, 1991.21: 311-330 [8] Liao L Z, Li D. Adaptive differential dynamic programming for multiobjective optimal contol[J]. Automatica, 2002, 38: 1003 I015 [9]LiD, Ng W-L. Optimal dynamic portfolio selection Multi-period mear variance formulation[J]. Mathematical Finance, 2000 10:387-406. [10] Luus R Iterative dynamic programming: From curiosity to a practical optimization pocedure[J]. Control Intell Syst, 1998, 26: 1 8 [11 Mayne D. A second-order gradient method for determining optimal trajectories of norr linear discrete-time systems[J]. International Journal of Control. 19663: 85-95 [12] Morin T L, Esogbue A M O. The imbedded state space appoach to reducing dimensionality in dynamic programs of higher dimensions[j]. J math Anal Appl, 1974, 48: 801-810 [13 Yakowitz S, Rutherford B Computational aspects of discrete- time optimal control[J]. Appl Math Comput, 1984, 15: 29-45 14 Zhu SS, Li D, Wang S Y. Risk control over bankruptcy in dynamic portfolio selection: A generalized mear variance formulation U. IEEE Transactions on Automatic Control, 2004, 49: 447-457 91994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreservedhttp://www.cnki.net