In this paper, we propose a semidefinite optimization (SDP) based model for the class of minimax two-stage stochastic linear optimization problems with risk aversion. The distribution of the second-stage random variables is assumed to be chosen from a set of multivariate distributions with known mean and second moment matrix. For the minimax stochastic problem with random objective, we provide a tight polynomial time solvable SDP formulation. For the minimax stochastic problem with random right-hand side, the problem is shown to be NP-hard in general. When the number of extreme points in the dual polytope of the second-stage stochastic problem is bounded by a function which is polynomial in the dimension, the problem can be solved in polynomial time. Explicit constructions of the worst case distributions for the minimax problems are provided. Applications in a production-transportation problem and a single facility minimax distance problem are provided to demonstrate our approach. In our computational experiments, the performance of minimax solutions is close to that of data-driven solutions under the multivariate normal distribution and is better under extremal distributions. The minimax solutions thus guarantee to hedge against these worst possible distributions while also providing a natural distribution to stress test stochastic optimization problems under distributional ambiguity.
Article
View Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion