Robust Dual Dynamic Programming



We propose a robust dual dynamic programming (RDDP) scheme for multi-stage robust optimization problems. The RDDP scheme takes advantage of the decomposable nature of these problems by bounding the costs arising in the future stages through inner and outer approximations. In contrast to Stochastic Dual Dynamic Programming, we refine the approximations deterministically, using our inner approximations as a devise to determine the points of refinement. RDDP converges deterministically in finite time. Numerical results illustrate the good practical performance of the algorithm.