An SDDP Algorithm for Multistage Stochastic Programs with Decision-Dependent Uncertainty

Stochastic programming provides mathematical models and algorithms for optimizing decisions under uncertainty. In formulating a stochastic program we typically assume that the probability distributions governing the random parameters are independent of the problem's decisions. Here, we study a multistage stochastic program with decision-dependent uncertainty. At each stage, binary decisions choose from a set of probability distributions and can increase the likelihood of favorable outcomes at a certain cost. We develop a variant of the stochastic dual dynamic programming (SDDP) algorithm to approximately solve this class of problems, using a convex relaxation of the algorithm's subproblems. This allows us to handle a type of large-scale multistage decision-dependent stochastic program, which was previously inaccessible. We provide computational results for a multi-product newsvendor problem with binary marketing options.