连续型凸动态规划的离散近似迭代法研究

张鹏

系统科学与数学 ›› 2011, Vol. 31 ›› Issue (8) : 943-951.

PDF(396 KB)
PDF(396 KB)
系统科学与数学 ›› 2011, Vol. 31 ›› Issue (8) : 943-951. DOI: 10.12341/jssms11678
论文

连续型凸动态规划的离散近似迭代法研究

    张鹏
作者信息 +

THE DISCRETE APPROXIMATE ITERATION METHOD ON THE  CONTINUING CONVEX DYNAMIC PROGRAMMING

    ZHANG Peng
Author information +
文章历史 +

摘要

为解决连续型凸动态规划的``维数灾" 问题, 提出了一种新的算法---离散近似迭代法. 该算法的基本思路为: 首先, 将连续型状态变量离散化, 根据网络图的构造方法将动态规划问题转化为多阶段有向赋权图; 其次, 运用极大代数求出起点至终点的最短路, 即获得模型的一个可行解; 最后, 以该可行解为基础, 继续迭代直到前后两个可行解非常接近. 文章还证明了该算法的收敛性和线性收敛, 并以一个具体例子验证了算法的有效性.

Abstract

In order to solve the ``dimension curse", the paper proposes  a new  discrete approximate iteration method  to solve the continuing convex dynamic programming model. Firstly, according to the network approach,  the state variables are discretized and   the model is transformed  into multiperiod weighted digraph. Secondly,  the max-plus algebra and the max-plus algebra are used to solve the shortest path that  is the admissible  solution. Thirdly, based on the admissible solution, the iteration is continued until the two admissible  solutions are close each other. The method is proved to be convergent and linearly convergent.  Finally, an example shows that the method is highly effective.

关键词

凸动态规划问题 /   / 离散近似迭代方法 / 极大代数 /   / 旋转算法

Key words

Convex dynamic programming /  discrete approximate iteration /  max-plus algebra / pivoting algorithm

引用本文

导出引用
张鹏. 连续型凸动态规划的离散近似迭代法研究. 系统科学与数学, 2011, 31(8): 943-951. https://doi.org/10.12341/jssms11678
ZHANG Peng. THE DISCRETE APPROXIMATE ITERATION METHOD ON THE  CONTINUING CONVEX DYNAMIC PROGRAMMING. Journal of Systems Science and Mathematical Sciences, 2011, 31(8): 943-951 https://doi.org/10.12341/jssms11678
中图分类号: 90C35   
PDF(396 KB)

Accesses

Citation

Detail

段落导航
相关文章

/