Constructing Uncertainty Sets for Robust Linear Optimization

被引:233
作者
Bertsimas, Dimitris [1 ,2 ]
Brown, David B. [3 ]
机构
[1] MIT, Alfred P Sloan Sch Management, Cambridge, MA 02139 USA
[2] MIT, Ctr Operat Res, Cambridge, MA 02139 USA
[3] Duke Univ, Fuqua Sch Business, Durham, NC 27708 USA
关键词
RISK; REPRESENTATION; APPROXIMATIONS;
D O I
10.1287/opre.1080.0646
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
In this paper, we propose a methodology for constructing uncertainty sets within the framework of robust optimization for linear optimization problems with uncertain parameters. Our approach relies on decision maker risk preferences. Specifically, we utilize the theory of coherent risk measures initiated by Artzner et al. (1999) [Artzner, P., F. Delbaen, J. Eber, D. Heath. 1999. Coherent measures of risk. Math. Finance 9 203-228.], and show that such risk measures, in conjunction with the support of the uncertain parameters, are equivalent to explicit uncertainty sets for robust optimization. We explore the structure of these sets in detail. In particular, we study a class of coherent risk measures, called distortion risk measures, which give rise to polyhedral uncertainty sets of a special structure that is tractable in the context of robust optimization. In the case of discrete distributions with rational probabilities, which is useful in practical settings when we are sampling from data, we show that the class of all distortion risk measures (and their corresponding polyhedral sets) are generated by a finite number of conditional value-at-risk (CVaR) measures. A subclass of the distortion risk measures corresponds to polyhedral uncertainty sets symmetric through the sample mean. We show that this subclass is also finitely generated and can be used to find inner approximations to arbitrary, polyhedral uncertainty sets.
引用
收藏
页码:1483 / 1495
页数:13
相关论文
共 32 条
[1]   Spectral measures of risk: A coherent representation of subjective risk aversion [J].
Acerbi, C .
JOURNAL OF BANKING & FINANCE, 2002, 26 (07) :1505-1518
[2]   On the coherence of expected shortfall [J].
Acerbi, C ;
Tasche, D .
JOURNAL OF BANKING & FINANCE, 2002, 26 (07) :1487-1503
[3]  
[Anonymous], 2008, Stochastic Finance
[4]   Coherent measures of risk [J].
Artzner, P ;
Delbaen, F ;
Eber, JM ;
Heath, D .
MATHEMATICAL FINANCE, 1999, 9 (03) :203-228
[5]   Robust solutions of Linear Programming problems contaminated with uncertain data [J].
Ben-Tal, A ;
Nemirovski, A .
MATHEMATICAL PROGRAMMING, 2000, 88 (03) :411-424
[6]   Robust solutions of uncertain linear programs [J].
Ben-Tal, A ;
Nemirovski, A .
OPERATIONS RESEARCH LETTERS, 1999, 25 (01) :1-13
[7]   Tractable approximations to robust conic optimization problems [J].
Bertsimas, D ;
Sim, M .
MATHEMATICAL PROGRAMMING, 2006, 107 (1-2) :5-36
[8]   Robust linear optimization under general norms [J].
Bertsimas, D ;
Pachamanova, D ;
Sim, M .
OPERATIONS RESEARCH LETTERS, 2004, 32 (06) :510-516
[9]   Shortfall as a risk measure: properties, optimization and applications [J].
Bertsimas, D ;
Lauprete, GJ ;
Samarov, A .
JOURNAL OF ECONOMIC DYNAMICS & CONTROL, 2004, 28 (07) :1353-1381
[10]   Uncertain convex programs: randomized solutions and confidence levels [J].
Calafiore, G ;
Campi, MC .
MATHEMATICAL PROGRAMMING, 2005, 102 (01) :25-46