Title: 
On Multistage Stochastic and Distributionally Robust Optimization: New Algorithms, Complexity Analysis, and Performance

Advisor: 
Dr. Andy Sun, School of Management, Massachusetts Institute of Technology

Other Committee Members:
Dr. Santanu S. Dey, School of Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Daniel Molzahn, School of Electrical and Computer Engineering, Georgia Institute of Technology
Dr. Arkadi Nemirovski, School of Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Alexander Shapiro, School of Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Wolfram Wiesemann, Department of Computing, Imperial College Business School London

Date and Time: July 14, 10 am (eastern time)

Location (Meeting Link): https://mit.zoom.us/j/99569573140

Abstract:

Multistage optimization under uncertainty refers to sequential decision-making with the presence of uncertainty information that is revealed partially until the end of planning horizon. Depending on the uncertainty model, it is often studied as multistage stochastic optimization (MSO), where one seeks optimal decisions with minimum mean objective with respect to a certain probabilistic uncertainty model; or more generally multistage distributionally robust optimization (MDRO), where one seeks optimal decisions with respect to a worst-case probability distribution over a candidate set of distributions. Both approaches have found ubiquitous applications such as in energy system and production capacity planning.

In Chapter 2, we focus on MSO with possibly integer variables and nonlinear constraints. We develop dual dynamic programming (DDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. Several interesting classes of MSO problems are identified, where the new algorithms are guaranteed to obtain the global optimum without the assumption of complete recourse. We also characterize the iteration complexity of the proposed algorithms, which reveals that the iteration complexity depends polynomially on the number of stages. We further show that the iteration complexity depends linearly on the number of stages T, if all the state spaces are finite sets, or if we allow the optimality gap to scale with T. This complexity study resolves an question on the iteration complexity of DDP-type algorithms.

In Chapter 3, we propose a new class of algorithms for solving convex MDRO problems, 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 MDRO problems. We then define single stage subproblem oracles (SSSO) and provide a thorough complexity analysis of the new algorithms, proving both upper complexity bounds and a matching lower bound. Numerical examples on inventory problems and hydrothermal power system planning problems are given to show the effectiveness of the proposed regularization technique.

In Chapter 4, we consider convex MDRO with Wasserstein ambiguity sets constructed from stagewise independent empirical distributions. We show that these data-driven MDRO models have favorable out-of-sample performance guarantee and adjustable level of in-sample conservatism. Then we extend the DDP algorithm to the data-driven MDRO by proposing two SSSO realizations that are able to handle the Wasserstein ambiguity sets, exploiting either convexity or concavity of the uncertain cost functions. Extensive numerical experiments on inventory problems are then conducted to compare these data-driven MDRO models with the widely used risk-neutral and risk-averse multistage stochastic optimization models.