Optimization Online


Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion

Dimitris Bertsimas(dbertsim***at***mit.edu)
Xuan Vinh Doan(vanxuan***at***mit.edu)
Karthik Natarajan(matkbn***at***nus.edu.sg)
Chung-Piaw Teo(teocp***at***nus.edu.sg)

Abstract: 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.

Keywords: Minimax stochastic optimization; Moments; Risk aversion; Semidefinite optimization

Category 1: Stochastic Programming

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )


Download: [PDF]

Entry Submitted: 05/12/2008
Entry Accepted: 05/13/2008
Entry Last Modified: 05/12/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society