Data-driven Stochastic Programming with Distributionally Robust Constraints Under Wasserstein Distance: Asymptotic Properties

doi:10.1007/s40305-020-00313-w

Journal of the Operations Research Society of China ›› 2021, Vol. 9 ›› Issue (3): 525-542.doi: 10.1007/s40305-020-00313-w

Previous Articles Next Articles

Data-driven Stochastic Programming with Distributionally Robust Constraints Under Wasserstein Distance: Asymptotic Properties

Yu Mei^1,2, Zhi-Ping Chen^1,2, Bing-Bing Ji^1,2, Zhu-Jia Xu^1,2, Jia Liu^1,2

1 Department of Computing Science, School of Mathematics and Statistics, Xi'an Jiaotong University, Xi'an 710049, China;
2 Center for Optimization Technique and Quantitative Finance, Xi'an International Academy for Mathematics and Mathematical Technology, Xi'an 710049, China

Received:2019-11-17 Revised:2020-06-12 Online:2021-09-30 Published:2021-09-26
Contact: Zhi-Ping Chen,zchen@mail.xjtu.edu.cn;Yu Mei,meiyu414@stu.xjtu.edu.cn;Bing-Bing Ji,bingji0225@stu.xjtu.edu.cn;Zhu-Jia Xu,xzj19930326@163.com;Jia Liu,jialiu@xjtu.edu.cn E-mail:zchen@mail.xjtu.edu.cn;meiyu414@stu.xjtu.edu.cn;bingji0225@stu.xjtu.edu.cn;xzj19930326@163.com;jialiu@xjtu.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (Nos. 11991023, 11901449, 11735011).

Abstract

Abstract: Distributionally robust optimization is a dominant paradigm for decision-making problems where the distribution of random variables is unknown. We investigate a distributionally robust optimization problem with ambiguities in the objective function and countably infinite constraints. The ambiguity set is defined as a Wasserstein ball centered at the empirical distribution. Based on the concentration inequality of Wasserstein distance, we establish the asymptotic convergence property of the datadriven distributionally robust optimization problem when the sample size goes to infinity. We show that with probability 1, the optimal value and the optimal solution set of the data-driven distributionally robust problem converge to those of the stochastic optimization problem with true distribution. Finally, we provide numerical evidences for the established theoretical results.

Key words: Distributionally robust optimization, Wasserstein distance, Ambiguity set, Asymptotic analysis, Empirical distribution

CLC Number:

90C59
90C34

Yu Mei, Zhi-Ping Chen, Bing-Bing Ji, Zhu-Jia Xu, Jia Liu. Data-driven Stochastic Programming with Distributionally Robust Constraints Under Wasserstein Distance: Asymptotic Properties[J]. Journal of the Operations Research Society of China, 2021, 9(3): 525-542.

TrendMD

References

[1] Shapiro, A., Dentcheva, D., Ruszczyński, A.:Lectures on Stochastic Programming:Modeling and Theory. Society for Industrial and Applied Mathematics and Mathematical Programming Society, Philadelphia (2009)
[2] Noyan, N., Rudolf, G.:Optimization with stochastic preferences based on a general class of scalarization functions. Oper. Res. 66(2), 463-486(2018)
[3] Ji, Y., Qu, S., Wu, Z., Liu, Z.:A fuzzy-robust weighted approach for multicriteria bilevel games. IEEE Trans. Ind. Inf. (2020). https://doi.org/10.1109/TII.2020.2969456
[4] Dentcheva, D., Ruszczyński, A.:Optimization with stochastic dominance constraints. SIAM J. Optim. 14(2), 548-566(2003)
[5] Liu, Y., Xu, H.:Stability analysis of stochastic programs with second order dominance constraints. Math. Prog. 142, 435-460(2013)
[6] Liu, Y., Sun, H., Xu, H.:An approximation scheme for stochastic programs with second order dominance constraints. Numer. Algeb. Control Optim. 6(4), 473-490(2016)
[7] Sun, H., Xu, H., Wang, Y.:A smoothing penalized sample average approximation method for stochastic programs with second-order stochastic dominance constraints. Asia-Pacific J. Oper. Res. 30(3), 548-554(2013)
[8] Arrow, K.J., Karlin, S., Scarf, H.:Studies in the mathematical theory of inventory and production. Rev. Econ. Stat. 14(69), 64-108(1958)
[9] Žáčková, J.:On minimax solutions of stochastic linear programming problems. Čas. Pěst. Mat. 91(4), 423-430(1966)
[10] Ben-Tal, A., den Hertog, D., De Waegenaere, A., Melenberg, B., Rennen, G.:Robust solutions of optimization problems affected by uncertain probabilities. Manag. Sci. 59(2), 341-357(2013)
[11] Delage, E., Ye, Y.:Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper. Res. 58(3), 595-612(2010)
[12] Goh, J., Sim, M.:Distributionally robust optimization and its tractable approximations. Oper. Res. 58(4), 902-917(2010)
[13] Wiesemann, W., Kuhn, D., Sim, M.:Distributionally robust convex optimization. Oper. Res. 62(6), 1358-1376(2014)
[14] Ling, A., Sun, J., Xiu, N., Yang, X.:Robust two-stage stochastic linear optimization with risk aversion. Eur. J. Oper. Res. 256(1), 215-229(2017)
[15] Guo, S., Xu, H., Zhang, L.:Probability approximation schemes for stochastic programs with distributionally robust second-order dominance constraints. Optim. Methods Software 32(4), 770-789(2016)
[16] Erdoǧan, E., Iyengar, G.:Ambiguous chance constrained problems and robust optimization. Math. Prog. 107(1), 37-61(2006)
[17] Gao, R., J.Kleywegt, A.:Distributionally robust stochastic optimization with Wasserstein distance, Working Paper. (2016). arXiv:1604.02199
[18] Zhao, C., Guan, Y.:Data-driven risk-averse stochastic optimization with Wasserstein metric. Oper. Res. Lett. 46, 262-267(2018)
[19] Bayraksan, G., Love, D.K.:Data-driven stochastic programming using phi-divergences. Turorials Oper. Res. (2015). https://doi.org/10.1287/educ.2015.0134
[20] Huang, R., Qu, S., Yang, X., Liu, Z.:Multi-stage distributionally robust optimization with risk aversion. J. Ind. Manag. Optim. 13, 1-27(2017)
[21] Pflug, G.C., Pichler, A., Wozabal, D.:The 1/n investment strategy is optimal under high model ambiguity. J. Bank. Finance 36, 410-417(2012)
[22] Mohajerin Esfahani, P., Kuhn, D.:Data-driven distributionally robust optimization using the Wassersteinmetric:performanceguaranteesandtractablereformulations.Math.Program. 171(1-2),115-166(2018)
[23] Rachev, S.T., Rüschendorf, L.:Mass Transportation Problems. Springer, New York (1998)
[24] Fournier, N., Guillin, A.:On the rate of convergence in Wasserstein distance of the empirical measure. Probab. Theory Relat. Fields 162(3), 707-738(2015)
[25] Guo, S., Xu, H.:Distributionally robust shortfall risk optimization model and its approximation. Math. Program. 174(1-2), 473-498(2019)
[26] Kallenberg, O.:Foundations of Modern Probability. Springer, New York (1997)
[27] Pagnoncelli, B.K., Ahmed, S., Shapiro, A.:Sample average approximation method for chance constrained programming:theory and applications. J. Optim. Theory Appl. 142(2), 399-416(2009)

Data-driven Stochastic Programming with Distributionally Robust Constraints Under Wasserstein Distance: Asymptotic Properties

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

Comments

[1]	John Gunnar Carlsson, Ye Wang. Distributions with Maximum Spread Subject to Wasserstein Distance Constraints [J]. Journal of the Operations Research Society of China, 2019, 7(1): 69-106.
[2]	Jia Liu, Zhi-Ping Chen, Yong-Chang Hui. Time Consistent Multi-period Worst-Case Risk Measure in Robust Portfolio Selection [J]. Journal of the Operations Research Society of China, 2018, 6(1): 138-158.