This paper presents a novel algorithmic study and complexity analysis of distributionally robust multistage convex optimization (DR-MCO). We propose a new class of algorithms for solving DR-MCO, namely a sequential dual dynamic programming (Seq-DDP) algorithm and its nonsequential version (NDDP). The new algorithms generalize and strengthen existing DDP-type algorithms by introducing the technique of regularization that enables the algorithms to handle 1) fast growth of Lipschitz constants, which is a common phenomenon in multistage optimization, and 2) problems without relatively complete recourse. We then provide a thorough complexity analysis of the new algorithms, proving both upper complexity bounds and a matching lower bound. To the best of our knowledge, this is the first complexity analysis of DDP-type algorithms for DR-MCO problems, quantifying the dependence of the oracle complexity of DDP-type algorithms on the number of stages, the dimension of the decision space, and various regularity characteristics of DR-MCO. Numerical examples are also given to show the effectiveness of the proposed regularization technique on reducing computation time or the number of oracle evaluations and on solving problems without relatively complete recourse.
Citation
H. Milton Stewart School of Industrial and Systems Engineering 755 Ferst Drive, NW, Atlanta, GA 30332 October 2020