论文标题
Lipschitz多阶段随机编程的热带动态编程
Tropical Dynamic Programming for Lipschitz Multistage Stochastic Programming
论文作者
论文摘要
我们提出了一种称为热带动态编程（TDP）的算法，该算法在风险中性多阶段随机编程（MSP）中构建了钟尔曼价值的上和下近似值，并具有有限支持的独立声音。 为了应对维数的诅咒，近似动态编程的流行参数变体近似钟声值函数作为基础函数的线性组合。在这里，热带动态编程构建了给定值函数的上部（分别为下），作为“基本函数”的最小线性（分别最大值线性）组合。在每次迭代中，TDP在Baucke，Doushward和Zackeri在2018年提出的确定性标准之后，为当前组合添加了一个新的基本功能，以供随机双重动态编程变体。 对于每个Lipschitz MSP，我们证明了TDP生成的近似功能对钟尔曼值函数的渐近收敛性。我们用线性动力学和多面体成本在MSP上说明了这一结果。
We present an algorithm called Tropical Dynamic Programming (TDP) which builds upper and lower approximations of the Bellman value functions in risk-neutral Multistage Stochastic Programming (MSP), with independent noises of finite supports. To tackle the curse of dimensionality, popular parametric variants of Approximate Dynamic Programming approximate the Bellman value function as linear combinations of basis functions. Here, Tropical Dynamic Programming builds upper (resp. lower) approximations of a given value function as min-plus linear (resp. max-plus linear) combinations of "basic functions". At each iteration, TDP adds a new basic function to the current combination following a deterministic criterion introduced by Baucke, Downward and Zackeri in 2018 for a variant of Stochastic Dual Dynamic Programming. We prove, for every Lipschitz MSP, the asymptotic convergence of the generated approximating functions of TDP to the Bellman value functions on sets of interest. We illustrate this result on MSP with linear dynamics and polyhedral costs.
