Forward-Backward Quantization of Scenario Processes in Multi-Stage Stochastic Optimization

Multi-stage stochastic optimization lies at the core of decision-making under uncertainty. As the analytical solution is available only in exceptional cases, dynamic optimization aims to efficiently find approximations but often neglects non-Markovian time-interdependencies. Methods on scenario trees can represent such interdependencies but are subject to the curse of dimensionality. To ease this problem, researchers typically approximate the uncertainty by smaller but more accurate trees. In this article, we focus on multi-stage optimal tree quantization methods of time-interdependent stochastic processes, for which we develop novel bounds and demonstrate that the upper bound can be minimized via projected gradient descent incorporating the tree structure as linear constraints. Consequently, we propose an efficient quantization procedure, which improves forward-looking samples using a backward step on the tree. We apply the results to the multi-stage inventory control with time-interdependent demand. For the case with one product, we benchmark the approximation because the problem allows a solution in closed-form. For the multi-dimensional problem, our solution found by optimal discrete approximation demonstrates the importance of holding mitigation inventory in different phases of the product life cycle.