一种多维连续型动态规划的新算法-控制与决策.pdf

第26 卷 第8 期 控 制 与 决 策 2011 年 8 月 Vol. 26 No. 8 Control and Decision Aug. 2011 文章编号: 1001-0920 (2011) 08-1219-05 一种多维连续型动态规划的新算法 张 鹏 (武汉科技大学管理学院，武汉430081) 摘 要: 在求解一维连续型动态规划问题的自创算法—– 离散近似迭代法的基础上, 结合双收敛方法, 对多维连续 型动态规划问题进行计算. 该算法的基本思路为: 在给定其他状态向量序列的基础上, 每次对一个状态变量序列进行 离散近似迭代, 并找出该状态变量的最优序列, 直到所有状态向量序列都检查完. 当模型为非凸非凹动态规划时, 证 明了该算法的收敛性; 当模型为凸动态规划时, 证明了该算法的线性收敛性. 最后, 通过具体算例验证了该模型和算 法的有效性. 关键词: 动态规划问题；多维；离散近似迭代方法；双收敛法 中图分类号: O221.2 文献标识码: A New algorithm for multidimensional continuing dynamic programming ZHANG Peng (School of Management，Wuhan University of Science and Technology ，Wuhan 430081 ，China. E-mail ：zhangpeng 300478@) Abstract: The paper uses the discrete approximate iteration method and bi-convergent method to solve the multidimensional continuing convex dynamic programming model. Firstly, the state value of one of state equations is set to be unknown and the others be known. Then, discrete approximate iteration method is used to find the optimal value of the unknown state values until all state equations have found optimal values. If the objective function is non-concave and non-convex, the algorithm is proved convergent. If the objective function is convex, the algorithm is proved linear convergent. Finally, an example shows the effectiveness of the formation and the algorithm. Key words: dynamic programming ；multidimensional ；discrete approximate iteration ；bi-convergent method 1 引引引 言言言 相对而言, 对连续型动态规划问题的解法尚不完 Bellman[1]于上世纪50 年代提出了动态规划的 善. 一般是采用动态规划的递推关系式求解. 但是当 最优性原理, 为动态最优化的研究奠定了坚实的基础. 动态规划问题含有不等式约束条件时, 求解很不方便. 自该理论提出