Randomized min-max optimization: The exact risk of multiple cost levels

In this paper, we present a theoretical result that applies to convex optimization problems in the presence of an uncertain stochastic parameter. We consider the min-max sample-based solution, i.e. the min-max solution computed over a finite sample of instances of the uncertain stochastic parameter, and the costs incurred by this solution in correspondence of the sampled parameter instances. Our goal is to evaluate the risks associated to the various costs, where the risk associated to a cost is the probability that the cost is exceeded when a new uncertainty instance is seen. The theoretical result proven in this paper is that the risks form a random vector whose probability distribution is always an ordered Dirichlet distribution, irrespective of the probability measure of the uncertain stochastic parameter. This evaluation characterizes completely the risks associated to the costs, and represents a full-fledged result on the reliability of the min-max sample-based solution.