Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion
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 stoc...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute for Operations Research and the Management Sciences
2012
|
| Online Access: | http://hdl.handle.net/1721.1/69922 https://orcid.org/0000-0002-1985-1003 |
| _version_ | 1826191434829529088 |
|---|---|
| author | Doan, Xuan Vinh Natarajan, Karthik Teo, Chung-Piaw Bertsimas, Dimitris J |
| author2 | Massachusetts Institute of Technology. Operations Research Center |
| author_facet | Massachusetts Institute of Technology. Operations Research Center Doan, Xuan Vinh Natarajan, Karthik Teo, Chung-Piaw Bertsimas, Dimitris J |
| author_sort | Doan, Xuan Vinh |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T08:55:48Z |
| format | Article |
| id | mit-1721.1/69922 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:55:48Z |
| publishDate | 2012 |
| publisher | Institute for Operations Research and the Management Sciences |
| record_format | dspace |
| spelling | mit-1721.1/699222023-03-01T02:06:46Z Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion Doan, Xuan Vinh Natarajan, Karthik Teo, Chung-Piaw Bertsimas, Dimitris J Massachusetts Institute of Technology. Operations Research Center Sloan School of Management Bertsimas, Dimitris J. Doan, Xuan Vinh Bertsimas, Dimitris J. 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. Singapore-MIT Alliance for Research and Technology National University of Singapore. Dept. of Mathematics 2012-04-04T15:25:39Z 2012-04-04T15:25:39Z 2010-08 2009-04 Article http://purl.org/eprint/type/JournalArticle 0364-765X 1526-5471 http://hdl.handle.net/1721.1/69922 Bertsimas, D. et al. “Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion.” Mathematics of Operations Research 35.3 (2010): 580–602. https://orcid.org/0000-0002-1985-1003 en_US http://dx.doi.org/10.1287/moor.1100.0445 Mathematics of Operations Research Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute for Operations Research and the Management Sciences Prof. Bertsimas via Alex Caracuzzo |
| spellingShingle | Doan, Xuan Vinh Natarajan, Karthik Teo, Chung-Piaw Bertsimas, Dimitris J Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion |
| title | Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion |
| title_full | Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion |
| title_fullStr | Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion |
| title_full_unstemmed | Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion |
| title_short | Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion |
| title_sort | models for minimax stochastic linear optimization problems with risk aversion |
| url | http://hdl.handle.net/1721.1/69922 https://orcid.org/0000-0002-1985-1003 |
| work_keys_str_mv | AT doanxuanvinh modelsforminimaxstochasticlinearoptimizationproblemswithriskaversion AT natarajankarthik modelsforminimaxstochasticlinearoptimizationproblemswithriskaversion AT teochungpiaw modelsforminimaxstochasticlinearoptimizationproblemswithriskaversion AT bertsimasdimitrisj modelsforminimaxstochasticlinearoptimizationproblemswithriskaversion |