Robust Linear Optimization and Coherent Risk Measures

David Brown
Department of Electrical Engineering and Computer Science
Massachusetts Institute of Technology


Friday, October 21, 2005
1:30 - 2:45 PM
Terman Engineering Center, Room 453


Abstract:

The field of robust optimization is relatively silent on the issue of how to construct uncertainty sets; in this work, we propose an axiomatic methodology for constructing uncertainty sets within the framework of robust linear optimization. We take as primitive for such problems a coherent risk measure, and utilize a well-known duality theorem for these measures to construct corresponding uncertainty sets in the robust optimization framework. Our approach focuses on the practical scenario in which we only have observations of the uncertain data but no detailed distributional information. We study classes of risk measures which give rise to polyhedral uncertainty sets. A subclass of these measures corresponds to centrally symmetric, polyhedral uncertainty sets and naturally induces a norm space. We show that the class of risk measures corresponding to tail moments leads to robust optimization problems with norm-bounded uncertainty sets. We also find that the converse construction holds; that is, given a convex uncertainty set, there exists a corresponding coherent risk measure which is equivalent. Finally, we show some computational evidence illustrating the value of this approach.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html