×

Discrete approximation and quantification in distributionally robust optimization. (English) Zbl 1440.90041

Summary: Discrete approximation of probability distributions is an important topic in stochastic programming. In this paper, we extend the research on this topic to distributionally robust optimization (DRO), where discretization is driven by either limited availability of empirical data (samples) or a computational need for improving numerical tractability. We start with a one-stage DRO where the ambiguity set is defined by generalized prior moment conditions and quantify the discrepancy between the discretized ambiguity set and the original one by employing the Kantorovich/Wasserstein metric. The quantification is achieved by establishing a new form of Hoffman’s lemma for moment problems under a general class of metrics – namely, \( \zeta \)-structures. We then investigate how the discrepancy propagates to the optimal value in one-stage DRO and discuss further the multistage DRO under nested distance. The technical results lay down a theoretical foundation for various discrete approximation schemes to be applied to solve one-stage and multistage distributionally robust optimization problems.

MSC:

90C17 Robustness in mathematical programming
90C15 Stochastic programming
90C31 Sensitivity, stability, parametric optimization
90C47 Minimax problems in mathematical programming

References:

[1] Analui B, Pflug G (2014) On distributionally robust multiperiod stochastic optimization. Comput. Management Sci. 11(3):197-220.Crossref, Google Scholar · Zbl 1328.90089 · doi:10.1007/s10287-014-0213-y
[2] Anderson E, Xu H, Zhang D (2016) Varying confidence levels for CVaR risk measures and minimax limits. Working paper, University of Sydney, Sydney, NSW, Australia.Google Scholar
[3] Athreya KB, Lahiri SN (2006) Measure Theory and Probability Theory (Springer Science+Business Media, New York).Google Scholar · Zbl 1125.60001
[4] Bertsimas D, Popescu I (2005) Optimal inequalities in probability theory: A convex optimization approach. SIAM J. Optim. 15(3):780-804.Crossref, Google Scholar · Zbl 1077.60020 · doi:10.1137/S1052623401399903
[5] Delage E, Ye YY (2010) Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper. Res. 58(3):595-612.Link, Google Scholar · Zbl 1228.90064
[6] Dudley RM (1969) The speed of mean Glivenko-Cantelli convergence. Ann. Math. Statist. 40(1):40-50.Crossref, Google Scholar · Zbl 0184.41401 · doi:10.1214/aoms/1177697802
[7] Esfahani TSPM, Lygeros J (2015) Performance bounds for the scenario approach and an extension to a class of non-convex program. IEEE Trans. Automatic Control 60(1):46-58.Crossref, Google Scholar · Zbl 1360.90251 · doi:10.1109/TAC.2014.2330702
[8] Gibbs AL, Su FE (2002) On choosing and bounding probability metrics. Internat. Statist. Rev. 70(3):419-435.Crossref, Google Scholar · Zbl 1217.62014 · doi:10.1111/j.1751-5823.2002.tb00178.x
[9] Graf S, Luschgy H (2000) Foundations of Quantization for Probability Distributions, Lecture Notes in Mathematics, vol. 1730 (Springer-Verlag, Berlin).Crossref, Google Scholar · Zbl 0951.60003 · doi:10.1007/BFb0103945
[10] Hoffman AJ (1952) On approximate solutions of systems of linear inequalities. J. Res. Natl. Bur. Stand. 49(4):263-265.Crossref, Google Scholar · doi:10.6028/jres.049.027
[11] Iyengar GN (2005) Robust dynamic programming. Math. Oper. Res. 30(2):257-280.Link, Google Scholar · Zbl 1082.90123
[12] Kallenberg O (2002) Foundations of Modern Probability (Springer, New York).Crossref, Google Scholar · Zbl 0996.60001 · doi:10.1007/978-1-4757-4015-8
[13] Kelley JE Jr (1960) The cutting-plane method for solving convex programs. J. Soc. Indust. Appl. Math. 8(4):703-712.Crossref, Google Scholar · Zbl 0098.12104 · doi:10.1137/0108053
[14] Liu Y, Meskarian R, Xu H (2017) A semi-infinite programming approach for distributionally robust reward-risk ratio optimization with matrix moments constraints. SIAM J. Optim. 27(2):957-985.Crossref, Google Scholar · Zbl 1365.90179 · doi:10.1137/16M106114X
[15] Mehrotra S, Papp D (2014) A cutting surface algorithm for semi-infinite convex programming with an application to moment robust optimization. SIAM J. Optim. 24(4):1670-1697.Crossref, Google Scholar · Zbl 1330.90119 · doi:10.1137/130925013
[16] Nilim A, Ghaoui LE (2005) Robust control of Markov decision processes with uncertain transition matrices. Oper. Res. 53(5):780-798.Link, Google Scholar · Zbl 1165.90674
[17] Pflug G, Pichler A (2011) Approximations for probability distributions and stochastic optimization problems. Bertocchi M, Consigli G, Dempster MAH, eds. Stochastic Optimization Methods in Finance and Energy, International Series in Operations Research and Management Science, vol. 163 (Springer, New York), 343-387.Crossref, Google Scholar · Zbl 1405.90093 · doi:10.1007/978-1-4419-9586-5_15
[18] Pflug G, Pichler A (2014) Multistage Stochastic Optimization, Springer Series in Operations Research and Financial Engineering (Springer International Publishing AG, Cham, Switzerland).Crossref, Google Scholar · Zbl 1317.90220 · doi:10.1007/978-3-319-08843-3
[19] Pflug G, Wozabal D (2007) Ambiguity in portfolio selection. Quant. Finance 7(4):435-442.Crossref, Google Scholar · Zbl 1190.91138 · doi:10.1080/14697680701455410
[20] Popescu I (2005) A semidefinite programming approach to optimal-moment bounds for convex classes of distributions. Math. Oper. Res. 30(3):632-657.Link, Google Scholar · Zbl 1082.60011
[21] Rachev ST (1991) Probability Metrics and the Stability of Stochastic Models (John Wiley & Sons, West Sussex, UK).Google Scholar · Zbl 0744.60004
[22] Robinson SM (1975) An application of error bounds for convex programming in a linear space. SIAM J. Control 13(2):271-273.Crossref, Google Scholar · Zbl 0297.90072 · doi:10.1137/0313015
[23] Römisch W (2003) Stability of stochastic programming problems. Ruszczyński A, Shapiro A, eds. Stochastic Programming, Handbooks in Operations Research and Management Science, vol. 10 (Elsevier, Amsterdam), 483-554.Crossref, Google Scholar · Zbl 1115.90001 · doi:10.1016/S0927-0507(03)10008-4
[24] Savage SL (2009) The Flaw of Averages: Why We Underestimate Risk in the Face of Uncertainty (John Wiley & Sons, Hoboken, NJ).Google Scholar
[25] Scarf H (1958) A min-max solution of an inventory problem. Arrow KJ, Karlin S, eds. Studies in the Mathematical Theory of Inventory and Production (Stanford University Press, Stanford, CA), 201-209.Google Scholar
[26] Shapiro A (2001) On duality theory of conic linear problems. Goberna MÁ, López MA, eds. Semi-Infinite Programming: Recent Advances (Springer, New York), 135-165.Crossref, Google Scholar · Zbl 1055.90088 · doi:10.1007/978-1-4757-3403-4_7
[27] Shapiro A (2003) Monte Carlo sampling methods. Ruszczyński A, Shapiro A, eds. Stochastic Programming, Handbooks in Operations Research and Management Science, vol. 10 (Elsevier, Amsterdam), 353-425.Crossref, Google Scholar · Zbl 1115.90001 · doi:10.1016/S0927-0507(03)10006-0
[28] Shapiro A (2012) Minimax and risk averse multistage stochastic programming. Eur. J. Oper. Res. 219(3):719-726.Crossref, Google Scholar · Zbl 1253.90181 · doi:10.1016/j.ejor.2011.11.005
[29] Shapiro A, Xu H (2008) Stochastic mathematical programs with equilibrium constraints, modeling and sample average approximation. Optimization 57(3):395-418.Crossref, Google Scholar · Zbl 1145.90047 · doi:10.1080/02331930801954177
[30] So AM-C (2011) Moment inequalities for sums of random matrices and their applications in optimization. Math. Programming 130(1):125-151.Crossref, Google Scholar · Zbl 1231.60007 · doi:10.1007/s10107-009-0330-5
[31] Sun H, Xu H (2016) Convergence analysis for distributionally robust optimization and equilibrium problems. Math. Oper. Res. 41(2):377-401.Link, Google Scholar · Zbl 1338.90288
[32] Wiesemann W, Kuhn D, Rustem B (2013) Robust Markov decision processes. Math. Oper. Res. 38(1):153-183.Link, Google Scholar · Zbl 1291.90295
[33] Wiesemann W, Kuhn D, Sim M (2014) Distributionally robust convex optimization. Oper. Res. 62(6):1358-1376.Link, Google Scholar · Zbl 1327.90158
[34] Xin L, Goldberg D (2013) Time (in)consistency of multistage distributionally robust inventory models with moment constraints. Optimization Online. Accessed August 20, 2018, http://www.optimization-online.org/DB_HTML/2013/04/3824.html.Google Scholar
[35] Xu H, Liu Y, Sun H (2018) Distributionally robust optimization with matrix moment constraints: Lagrange duality and cutting plane method. Math. Programming 169(2):489-529.Crossref, Google Scholar · Zbl 1391.90449 · doi:10.1007/s10107-017-1143-6
[36] Zhang J, Xu H, Zhang LW (2016) Quantitative stability analysis for distributionally robust optimization with moment constraints. SIAM J. Optim. 26(3):1855-1882.Crossref, Google Scholar · Zbl 1346.90650 · doi:10.1137/15M1038529
[37] Zhao C, Guan Y (2015) Data-driven risk-averse two-stage stochastic program with ζ-structure probability metrics. Working paper, University of Florida, Gainesville.Google Scholar
[38] Zhigljavsky A, Žilinskas A (2008) Stochastic Global Optimization (Springer, New York).Google Scholar · Zbl 1136.90003
[39] Zolotarev VM (1983) Probability metrics. Theory Probab. Appl. 28(2):264-287.Google Scholar · Zbl 0514.60026
[40] Zymler S, · Zbl 1286.90103 · doi:10.1007/s10107-011-0494-7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.