A Distributional Interpretation of Robust Optimization

Mathematics of Operations Research - Tập 37 Số 1 - Trang 95-110 - 2012
Huan Xu1, Constantine Caramanis2, Shie Mannor3
1Department of Mechanical Engineering, National University of Singapore, Singapore 117575
2Department of Electrical and Computer Engineering, University of Texas at Austin, Austin, Texas, 78712
3Department of Electrical Engineering, Technion, Haifa 32000, Israel

Tóm tắt

Motivated by data-driven decision making and sampling problems, we investigate probabilistic interpretations of robust optimization (RO). We establish a connection between RO and distributionally robust stochastic programming (DRSP), showing that the solution to any RO problem is also a solution to a DRSP problem. Specifically, we consider the case where multiple uncertain parameters belong to the same fixed dimensional space and find the set of distributions of the equivalent DRSP problem. The equivalence we derive enables us to construct RO formulations for sampled problems (as in stochastic programming and machine learning) that are statistically consistent, even when the original sampled problem is not. In the process, this provides a systematic approach for tuning the uncertainty set. The equivalence further provides a probabilistic explanation for the common shrinkage heuristic, where the uncertainty set used in an RO problem is a shrunken version of the original uncertainty set.

Từ khóa


Tài liệu tham khảo

10.1017/CBO9780511624216

10.1016/S0167-6377(99)00016-4

10.1007/PL00011380

10.1515/9781400831050

10.1007/978-1-4757-3216-0_12

10.1287/msom.1050.0081

10.1007/s10107-003-0454-y

10.1287/opre.1030.0065

10.1137/080734510

Birge J. R., 1997, Introduction to Stochastic Programming

10.1145/130385.130401

10.1287/opre.1050.0254

10.1287/opre.1080.0685

10.1287/opre.1090.0741

Devroye L., 1985, Nonparametric Density Estimation: The l1 View

10.1007/978-1-4612-0711-5

10.1080/17442508708833436

10.1137/S0895479896298130

10.1287/opre.1090.0795

10.1007/BF02868641

Kall P., 1988, Advances in Mathematical Optimization, 86, 10.1515/9783112479926-009

King A. J., 1991, Stochast. Stochast. Reports, 34, 1045

Lanckriet G. R., 2003, J. Machine Learn. Res., 3, 555

10.1007/s10107-007-0149-x

10.1214/aoms/1177704472

10.1287/opre.1060.0353

10.1007/978-94-017-3087-7

10.1515/9781400873173

10.1214/aoms/1177728190

Scarf H., 1958, Studies in Mathematical Theory of Inventory and Production, 201

Schölkopf B., 2002, Learning with Kernels

10.1002/9780470316849

10.1007/BF02204815

10.1007/s10107-005-0680-6

10.1137/S1052623498349541

Shivaswamy P. K., 2006, J. Machine Learn. Res., 7, 1283

10.1287/opre.21.5.1154

10.1109/TIT.2004.839514

10.1111/j.2517-6161.1996.tb02080.x

Vapnik V. N., 1974, Theory of Pattern Recognition

Vapnik V. N., 1991, Pattern Recognition Image Anal., 1, 260

Xu H., 2007, Advances in Neural Information Processing Systems 19, 1537, 10.7551/mitpress/7503.003.0197

Xu H., 2009, J. Machine Learn. Res., 10, 1485

10.1109/TIT.2010.2048503

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

Mathematics of Operations Research

Tập 37 Số 1

95-110

Thông tin tác giả