In this paper, we consider multi-stage robust convex optimization problems of the minimax type. We assume that the total uncertainty set is the cartesian product of stagewise compact uncertainty sets and approximate the given problem by a sampled subproblem. Instead of looking for the worst case among the infinite and typically uncountable set of uncertain parameters, we consider only the worst case among a randomly selected subset of parameters.
By adopting such a strategy, two main questions arise: (1) Can we quantify the error committed by the random approximation, especially as a function of the sample size?
(2) If the sample size tends to infinity, does the optimal value converge to the “true” optimal value? Both questions will be answered in this paper.
An explicit bound on the probability of violation is given and chain of lower bounds on the original multi-stage robust optimization problem provided. Numerical results dealing with a multi-stage inventory management problem
show that the proposed approach works well, given that the sample size is large enough. Due to the fact that we solve a very complex problem and not a surrogate with no quality guarantee, large sample sizes cannot be avoided.
Citation
Submitted for publication in international journal on November 19th 2019.