Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion

Mathematics of Operations Research - Tập 35 Số 3 - Trang 580-602 - 2010
Dimitris Bertsimas1, Xuan Vinh Doan2, Karthik Natarajan3, Chung‐Piaw Teo4
1MIT, Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
2Operations Research Center , Massachusetts Institute of Technology , Cambridge, Massachusetts, 02139
3Department of Management Sciences, College of Business, City University of Hong Kong, Kowloon Tong, Hong Kong
4Department of Decision Sciences, NUS Business School, National University of Singapore, Singapore 117591

Tóm tắt

We propose a semidefinite optimization (SDP) model for the class of minimax two-stage stochastic linear optimization problems with risk aversion. The distribution of second-stage random variables belongs to a set of multivariate distributions with known first and second moments. For the minimax stochastic problem with random objective, we provide a tight SDP formulation. The problem with random right-hand side is NP-hard in general. In a special case, the problem can be solved in polynomial time. Explicit constructions of the worst-case distributions are provided. Applications in a production-transportation problem and a single facility minimax distance problem are provided to demonstrate our approach. In our experiments, the performance of minimax solutions is close to that of data-driven solutions under the multivariate normal distribution and better under extremal distributions. The minimax solutions thus guarantee to hedge against these worst possible distributions and provide a natural distribution to stress test stochastic optimization problems under distributional ambiguity.

Từ khóa


Tài liệu tham khảo

10.1007/s10107-005-0638-8

10.1287/mnsc.32.11.1445

10.1111/j.1467-9965.2007.00311.x

10.1007/BF01300861

10.1287/mnsc.26.1.113

10.1287/opre.1090.0741

10.1287/moor.1040.0136

10.1080/17442508708833436

10.1007/3-540-35262-7_2

Edmundson H. P., 1956, Acta Mathematica, 30, 175

10.1137/040605217

10.1016/0098-1354(90)80020-C

10.1007/s00186-007-0161-1

10.1007/978-3-642-97881-4

10.1007/BF02868641

10.1007/BF02418571

Kall P., 1994, Stochastic Programming

10.1109/CACSD.2004.1393890

10.1214/aoms/1177706203

10.1137/0607052

10.1016/j.ejor.2003.09.033

10.1287/opre.21.1.377

10.1137/S1052623403434012

10.1080/1055678021000034008

10.2140/pjm.1958.8.171

10.1080/10556789908805766

10.1287/opre.24.4.643

Žáčková J., 1966, Časopis pro Pěstování Matematiky, 91, 423, 10.21136/CPM.1966.117583

Thông tin
Thông tin xuất bản

Mathematics of Operations Research

Tập 35 Số 3

580-602

Thông tin tác giả