nips nips2013 nips2013-80 nips2013-80-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Martin Mevissen, Emanuele Ragnoli, Jia Yuan Yu
Abstract: We consider robust optimization for polynomial optimization problems where the uncertainty set is a set of candidate probability density functions. This set is a ball around a density function estimated from data samples, i.e., it is data-driven and random. Polynomial optimization problems are inherently hard due to nonconvex objectives and constraints. However, we show that by employing polynomial and histogram density estimates, we can introduce robustness with respect to distributional uncertainty sets without making the problem harder. We show that the optimum to the distributionally robust problem is the limit of a sequence of tractable semidefinite programming relaxations. We also give finite-sample consistency guarantees for the data-driven uncertainty sets. Finally, we apply our model and solution method in a water network optimization problem. 1
[1] J. B. Lasserre. A semidefinite programming approach to the generalized problem of moments. Math. Programming, 112:65–92, 2008. 8
[2] A. Schied. Optimal investments for robust utility functionals in complete market models. Math. Oper. Research, 30(3):750–764, 2005.
[3] E. Delage and Y. Ye. Distributionally robust optimization under moment uncertainty with applications to data-driven problems. Operations Research, 2009.
[4] D. Bertsimas, X. V. Doan, K. Natarajan, and C.-P. Teo. Models for minimax stochastic linear optimization problems with risk aversion. Math. Oper. Res., 35(3):580–602, 2010.
[5] S. Mehrotra and H. Zhang. Models and algorithms for distributionally robust least squares problems. Preprint, 2011.
[6] D. Bertsimas and I. Popescu. Optimal inequalities in probability theory: a convex optimization approach. SIAM J. Optimization, 15:780–804, 2000.
[7] P. R. Halmos. The theory of unbiased estimation. The Annals of Mathematical Statistics, 17(1):34–43, 1946.
[8] B.W. Silverman. Density Estimation for Statistics and Data Analysis. Chapman & Hall/CRC, 1998.
[9] L. Devroye and L. Györfi. Nonparametric Density Estimation. Wiley, 1985.
[10] P. Hall. On the rate of convergence of orthogonal series density estimators. Journal of the Royal Statistical Society. Series B, 48(1):115–122, 1986.
[11] G. Pflug and D. Wozabal. Ambiguity in portfolio selection. Quantitative Finance, 7(4):435– 442, 2007.
[12] A. Shapiro and S. Ahmed. On a class of minimax stochastic programs. SIAM J. Optim., 14(4):1237–1249, 2004.
[13] A. Ben-Tal, D. den Hertog, A. de Waegenaere, B. Melenerg, and G. Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 2012.
[14] H. Xu and S. Mannor. Distributionally robust markov decision processes. Mathematics of Operations Research, 37(2):288–300, 2012.
[15] R. Laraki and J. B. Lasserre. Semidefinite programming for min-max problems and games. Math. Programming A, 131:305–332, 2010.
[16] P. Massart. The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality. Annals of Probability, 18(3):1269–1283, 1990.
[17] B. J. Eck and M. Mevissen. Valve placement in water networks. Technical report, IBM Research, 2012. Report No. RC25307 (IRE1209-014).
[18] A. Sterling and A. Bargiela. Leakage reduction by optimised control of valves in water networks. Transactions of the Institute of Measurement and Control, 6(6):293–298, 1984.
[19] H. Waki, S. Kim, M. Kojima, M. Muramatsu, and H. Sugimoto. SparsePOP: a sparse semidefinite programming relaxation of polynomial optimization problems. ACM Transactions on Mathematical Software, 35(2), 2008.
[20] M. Yamashita, K. Fujisawa, K. Nakata, M. Nakata, M. Fukuda, K. Kobayashi, and K. Goto. A high-performance software package for semidefinite programs: SDPA 7. Technical report, Tokyo Institute of Technology, 2010.
[21] A. Waechter and L. T. Biegler. On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Mathematical Programming, 106(1):25–57, 2006.
[22] M. Schweighofer. Optimization of polynomials on compact semialgebraic sets. SIAM J. Optimization, 15:805–825, 2005. 9