Session: Special Session in Honor of Suvrajeet Sen: Sampling-based Methods in Stochastic Programming
Chair: Harsha Gangammanavar
Cluster: Optimization Under Uncertainty and Data-driven Optimization
Talk 1: A Stochastic Decomposition Method for Multistage Distributionally Robust Optimization under Streaming Data
Speaker: Tian Xia
Abstract: Multistage Stochastic Programming (MSP) is a fundamental framework for modeling sequential decision-making under uncertainty. However, challenges such as curse of dimensionality and random variable’s unknown probability distribution make MSP difficult to solve in practice. In this talk, under the streaming data setting, we present a Multistage Distributionally Robust Optimization (MDRO) framework to approximate the original MSP, where the radius of the ambiguity set of distributions shrink as more data is obtained. We propose a Stochastic Decomposition (SD) method specifically tailored to MDRO under streaming data, i.e., an online environment, named as MDRSD. Within the streaming data-driven paradigm, we construct the ambiguity sets using the Wasserstein distance with shrinking radii and develop efficient approximations for both value functions and solutions to MSP. We show conditions under which the sequence of incumbent solutions generated by MDRSD converge asymptotically to those of the original MSP. As an additional theoretical result, we establish that the optimal value of the MDRO converges asymptotically to that of the MSP under our problem setting. Finally in numerical experiments, we validate the efficiency of MDRSD in solving real-world applications under streaming data.
Talk 2: An Adaptive Stochastic Dual Progressive Hedging Algorithm for Stochastic Programming
Speaker: Di Zhang
Abstract: The Progressive Hedging Algorithm (PHA) is a cornerstone in tackling large-scale stochastic programming (SP) challenges. However, its traditional implementation is hindered by several limitations, including the requirement to solve all scenario subproblems in each iteration, reliance on an explicit probability distribution, and a convergence process that is highly sensitive to the choice of penalty parameters. Our project introduces a stochastic dual PH algorithm (SDPH) that aims to overcome these limitations. Our approach employs a dynamic selection process for the number of scenario subproblems solved per iteration. It incorporates adaptive sequential sampling for determining sample sizes, stochastic conjugate subgradient methods for direction finding, and a line-search technique to update the dual variables. We present two alternative approaches to study its convergence: one based on a fixed-point theorem similar as in the original PH paper, whereas the other utilizes a stochastic stopping-time framework. Experimental results demonstrate that this novel algorithm not only addresses the bottlenecks of the conventional PHA but also potentially surpasses its scalability, representing a substantial improvement in the field of stochastic programming.
Talk 3: Sequential Sampling-based Algorithms in Stochastic Programming and their Applications
Speaker: Harsha Gangammanavar
Abstract: Multistage stochastic programming provides a practical framework for handling sequential decision-making under uncertainty. For solving such problems, particularly when the underlying stochastic process has continuous support, stochastic decomposition (SD)-based methods have proven to be very effective. Since its inception in Higle and Sen (1991), SD has inspired several algorithm designs for various stochastic programming settings and several large-scale applications. This talk previews some of these SD-inspired algorithms, including those for multistage stochastic programming and distributionally robust optimization. We will highlight the salient features in their design that lead to computational advantages and their analysis. The talk will also present the application of these SD-based methods in solving large-scale decision-making problems in infrastructure systems planning and operations.
