  


Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion
Dimitris Bertsimas(dbertsimmit.edu) Abstract: In this paper, we propose a semidefinite optimization (SDP) based model for the class of minimax twostage stochastic linear optimization problems with risk aversion. The distribution of the secondstage 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 righthand side, the problem is shown to be NPhard in general. When the number of extreme points in the dual polytope of the secondstage 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 productiontransportation 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 datadriven 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. Keywords: Minimax stochastic optimization; Moments; Risk aversion; Semidefinite optimization Category 1: Stochastic Programming Category 2: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: Download: [PDF] Entry Submitted: 05/12/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  