*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
