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

THE DISCRETE APPROXIMATE ITERATION METHOD ON THE CONTINUING CONVEX DYNAMIC PROGRAMMING

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

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.