Constructing Uncertainty Sets for Robust Linear Optimization

Dimitris Bertsimas () and David B. Brown ()
Additional contact information
Dimitris Bertsimas: Sloan School of Management and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
David B. Brown: The Fuqua School of Business, Duke University, Durham, North Carolina 27708

Operations Research, 2009, vol. 57, issue 6, 1483-1495

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

Keywords: robust optimization; uncertainty sets; coherent risk measures; distortion risk measures (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (90)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1080.0646 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:57:y:2009:i:6:p:1483-1495

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().