In this seminar, Francesco Giliberto will give a talk about Optimal Information Relaxation Bounds for Multi-Stage Stochastic Optimization.
This paper addresses the computation of tight optimistic bounds for multi-stage stochastic optimization problems using information relaxation duality. We introduce a specific class of penalty functions, bi-linear in decisions and the innovations of the underlying stochastic process, to penalize anticipative policies. Our approach provides a generic framework for deriving such bounds, notably without requiring explicit knowledge or approximation of the problem’s value functions. We formulate a minimax problem to find the optimal penalty parameters within this specific class, yielding the tightest bound achievable with these penalties. We show that for convex problems, this minimax problem can be equivalently reformulated as a standard stochastic program with expectation constraints. Furthermore, we propose an iterative algorithm to solve the minimax problem directly. The methodology offers a computationally tractable approach to generate bounds that are stronger than simple perfect information relaxations, thereby improving the evaluation of heuristic policies.