On Distributionally Robust Multistage Convex Optimization: New Algorithms and Complexity Analysis
This paper presents a novel algorithmic study with complexity analysis of distributionally robust multistage convex optimization (DR-MCO). We propose a new class of algorithms for solving DR-MCO, namely a consecutive dual dynamic programming (DDP) algorithm and a nonconsecutive version. The new algorithms generalize and strengthen existing DDP-type algorithms by introducing an important technique of regularization that enables the algorithms to handle much broader classes of DR-MCO problems. In particular, the proposed algorithms can safely handle fast growth of Lipschitz constants, a surprisingly prevalent phenomenon in multistage optimization, as well as 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 in such a general setting and it reveals, in a precise way, the dependence of the complexity of the 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, namely the reduction of the computation time or the number of subproblem oracle evaluations, and the capability of the algorithms to solve problems without relatively complete recourse.