学习笔记 动态规划解非线性规划问题静态规划问题

动态规划解非线性规划问题

初识动态规划,感觉很新鲜,方法也很巧妙。

把多阶段过程转化为一系列单阶段问题,逐个求解,解决这类问题的方法称为动态规划,它是一种方法、考察问题的一种途径,但不是一种特殊的算法。

虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。

1.动态规划的思路:


2.与静态规划相比,动态规划的优越性在于:
(i)能够得到全局最优解。由于约束条件确定的约束集合往往很复杂,即使指标函数较简单,用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为一系列结构相似的子问题,每个子问题的变量个数大大减少,约束集合也简单得多,易于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的优化问题,可以对每个子过程用枚举法求解,而约束条件越多,决策的搜索范围越小,求解也越容易。对于这类问题,动态规划通常是求全局最优解的唯一方法。
(ii)可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同,动态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。有些实际问题需要这样的解族,即使不需要,它们在分析最优策略和最优值对于状态的稳定性时也是很有用的。当最优策略由于某些原因不能实现时,这样的解族可以用来寻找次优策略。
[学习笔记]动态规划解非线性规划问题(静态规划问题)
(iii)能够利用经验提高求解效率。如果实际问题本身就是动态的,由于动态规划方法反映了过程逐段演变的前后联系和动态特征,在计算中可以利用实际知识和经验提高求解效率。如在策略迭代法中,实际经验能够帮助选择较好的初始策略,提高收敛速度。

3.动态规划的主要缺点是:
(i)没有统一的标准模型,也没有构造模型的通用方法,甚至还没有判断一个问题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析,构造具体的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵活的技巧性,这就带来了应用上的局限性。
(ii)用数值方法求解时存在维数灾(curse of dimensionality)。若一维状态变量有m个取值,那么对于n维问题,状态x_k就有m^n个值,对于每个状态值都要计算、存储函数f_k(x_k),对于n稍大的实际问题的计算往往是不现实的。目前还没有克服维数灾的有效的一般方法。
4.下面是一个例子




  

爱华网本文地址 » http://www.413yy.cn/a/25101012/133316.html

更多阅读

盗墓笔记长评 解雨臣三部曲之三:解雨臣面具下之猜想

解雨臣面具下之猜想by 平淡达人(沉溺深蓝)一直想围绕《盗墓笔记》中解雨臣这个人物写点东西,一直没落下笔。结果一旦写起来就一发不可收拾,又是原著角色评,又是同人衍生作,现在还扬言要揭开解雨臣的面具看看下面到底是啥——当然原著是

中小学教师职业道德规范学习笔记

中小学教师职业道德规范学习笔记一、依法执教。学习和宣传马列主义、毛泽东思想和邓--同志建设有中国特色社会主义理论,拥护党的基本路线,全面贯彻国家教育方针,自觉遵守《教师法》等法律法规,在教育教学中同党和国家的方针政策保持一

C++读书笔记(一)指针初始化相关问题 社会成本问题读书笔记

小芳前几天问了我一个问题,是关于指针初始化的。她当时给一个未初始化的字符串指针赋值,结果当然是错的(其实这句话是值得商量的)。虽然当时我发现了她的错误,但是我自己也不明白这为什么是错的。很是惭愧啊,辜负了小芳的期望。当天晚上我

伤寒学习笔记(下

伤寒学习笔记---14,桂枝用量问题?学习仲景药法,涉及用量问题。深入考证,固然不必,简单了解,实属必要。仅以桂枝为例,整理如下:基本资料:《现代中医药应用与研究大系》1985年版,简称《大系》。药法:凡例里说:“将其折合今之用量---,并结合笔者临床

声明:《学习笔记 动态规划解非线性规划问题静态规划问题》为网友木槿何溪分享!如侵犯到您的合法权益请联系我们删除