Abstract
This paper considers distributionally robust formulations of a two stage stochastic programming problem with the objective of minimizing a distortion risk of the minimal cost incurred at the second stage. We carry out a stability analysis by looking into variations of the ambiguity set under the Wasserstein metric, decision spaces at both stages and the support set of the random variables. In the case when the risk measure is risk neutral, the stability result is presented with the variation of the ambiguity set being measured by generic metrics of \(\zeta \)-structure, which provides a unified framework for quantitative stability analysis under various metrics including total variation metric and Kantorovich metric. When the ambiguity set is structured by a \(\zeta \)-ball, we find that the Hausdorff distance between two \(\zeta \)-balls is bounded by the distance of their centers and difference of their radii. The findings allow us to strengthen some recent convergence results on distributionally robust optimization where the center of the Wasserstein ball is constructed by the empirical probability distribution.
Similar content being viewed by others
Notes
In some references, it is called Wasserstein metric or Kantorovich–Wasserstein metric, see commentary by Villani [57]. Here we call it Kantorovich metric to distinguish it from Wasserstein metric to be defined later on.
The Dirac-measure is defined by \( \delta _{\xi }(A)=\mathbb {1}_A(\xi )={\left\{ \begin{array}{ll} 1 &{}\quad \text {if }\quad \xi \in A,\\ 0 &{}\quad \text {if }\quad \xi \not \in A. \end{array}\right. }\)
References
Acerbi, B.: Spectral measures of risk: a coherent representation of subjective risk aversion. J. Bank. Finance 26, 1505–1518 (2002)
Armbruster, B., Delage, E.: Decision making under uncertainty when preference information is incomplete. Manag. Sci. 61, 111–128 (2015)
Athreya, K.B., Lahiri, S.N.: Measure Theory and Probability Theory. Springer, Berlin (2006)
Ben-Tal, A., Ghaoui, L.E., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009)
Billingsley, P.: Convergence of Probability Measures. Wiley, New York (1968)
Castaing, C., Valadier, M.: Convex Analysis and Measurable Multifunctions, Lecture Notes in Mathematics. Springer, Berlin (1977)
Chen, X., Sun, H., Xu, H.: Discrete approximation of two-stage stochastic and distributionally robust linear complementarity problems. Math. Program. (2018). https://doi.org/10.1007/s10107-018-1266-4
Denneberg, D.: Distorted probabilities and insurance premiums. Methods Oper. Res. 63, 21–42 (1990)
Dentcheva, D., Penev, S., Ruszczyński, A.: Kusuoka representation of higher order dual risk measures. Ann. Oper. Res. 181, 325–335 (2010). https://doi.org/10.1007/s10479-010-0747-5
Dentcheva, D., Penev, S., Ruszczynski, A.: Statistical estimation of composite risk functionals and risk optimization problems. Ann. Inst. Stati. Math. 69, 737–760 (2017)
Dowd, K., Cotter, J., Sorwar, G.: Spectral risk measures: properties and limitations. J. Finance Serv. Res. 34, 61–75 (2008)
Dupačová, J.: Stability in stochastic programming with recourse contaminated distributions. In: Prékopa, A., Wets, R.J.B. (eds.) Stochastic Programming 84 Part I, pp. 133–144. Springer, Berlin (2009). https://doi.org/10.1007/bfb0121117
Dupačová, J., Gröwe-Kuska, N., Römisch, W.: Scenario reduction in stochastic programming. Math. Program. Ser. A 95(3), 493–511 (2003). https://doi.org/10.1007/s10107-002-0331-0
Esfahani, P.M., Kuhn, D.: Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations. Math. Program. 171, 115–166 (2018)
Fan, K.: Minimax theorems. Proc. Natl. Acad. Sci. U. S. A. 39(1), 42 (1953)
Fournier, N., Guilline, A.: On the rate of convergence in Wasserstein distance of the empirical measure. Probab. Theory Relat. Fields 162, 707–738 (2015). https://doi.org/10.1007/s00440-014-0583-7
Gao, R., Kleywegt, A.: Distributionally robust stochastic optimization with wasserstein distance. (2016) Preprint arXiv:1604.02199
Gibbs, A.L., Su, F.E.: On choosing and bounding probability metrics. Int. Stat. Rev. 70, 419–435 (2002)
Graf, S., Luschgy, H.: Foundations of Quantization for Probability Distributions, Volume 1730 of Lecture Notes in Mathematics. Springer, Berlin (2000). https://doi.org/10.1007/BFb0103945
Gröwe, N.: Estimated stochastic programs with chance constraints. Eur. J. Oper. Res. 101(2), 285–305 (1997). https://doi.org/10.1016/S0377-2217(96)00398-0
Guo, S., Xu, H.: Distributionally Robust Shortfall Risk Optimization Model and Its Approximation. Mathematical Programming Series B. Springer, Berlin (2018). https://doi.org/10.1007/s10107-018-1307-z
Hanasusanto, D.K., A., G., Wiesemann, W.: K-adaptability in two-stage robust binary programming. Oper. Res. 63, 877–891 (2015)
Hanasusanto, D.K., A., G., Wiesemann, W.: K-adaptability in two-stage distributionally robust binary programming. Oper. Res. Lett. 44, 6–11 (2016)
Hanasusanto GA, Kuhn D (2018) Conic programming reformulations of two-stage distributionally robust linear programs over wasserstein balls. Oper. Res. https://doi.org/10.1287/opre.2017.1698
Haskell, W.B., Huang, W., Xu, H.: Preference elicitation and robust optimization with multi-attribute quasi-concave choice functions (2018). Preprint arXiv:1805.06632
Heitsch, H., Römisch, W.: Scenario reduction algorithms in stochastic programming. Comput. Optim. Appl. Stoch. Program. 24(2–3), 187–206 (2003). https://doi.org/10.1023/A:1021805924152
Heitsch, H., Römisch, W.: A note on scenario reduction for two-stage stochastic programs. Oper. Res. Lett. 6, 731–738 (2007)
Hoeffding, W.: Maßstabinvariante Korrelationstheorie. Schr. Math. Inst. Univ. Berlin 5, 181–233 (1940). German
Homem de Mello, T.: On rates of convergence for stochastic optimization problems under non-iid sampling. SIAM J. Optim. 19, 524–551 (2008)
Hörmander, L.: Sur la fonction d’appui des ensembles convexes dans un espace localement convexe. Ark. Mat. 3(2), 181–186 (1955). https://doi.org/10.1007/BF02589354. In French
Kantorovich, L.V., Rubinshtein, G.S.: On a space of totally additive functions. Vestnik Leningr. Univ. 13, 52–59 (1958)
Kelley, J.E.: The cutting-plane method for solving convex programs. J. Soc. Ind. Appl. Math. 8, 703–712 (1960)
Klatte, D.: A note on quantitative stability results in nonlinear optimization. Seminarbericht, Sektion Mathematik, Humboldt-Universität zu Berlin, Berlin 90, 77–86 (1987)
Kovacevic, R.M., Pichler, A.: Tree approximation for discrete time stochastic processes: a process distance approach. Ann. Oper. Res. 235, 395–421 (2015). https://doi.org/10.1007/s10479-015-1994-2
Kusuoka, S.: Chapter 4: on law invariant coherent risk measures. In: Kusuoka, S., Maruyama, T. (eds.) Advances in Mathematical Economics, vol. 3, pp. 83–95. Springer, Berlin (2001). https://doi.org/10.1007/978-4-431-67891-5
Liu, Y., Xu, H.: Stability and sensitivity analysis of stochastic programs with second order dominance constraintss. Math. Program. Ser. A 142, 435–460 (2013)
Liu, Y., Pichler, A., Xu, H.: Discrete approximation and quantification in distributionally robust optimization Math. Oper. Res. (2017). https://doi.org/10.1287/moor.2017.0911
Mehrotra, S., Papp, D.: A cutting surface algorithm for semi-infinite convex programming with an application to moment robust optimization. SIAM J. Optim. 24, 1670–1697 (2014). https://doi.org/10.1137/130925013
Norkin, V.I., Keyzer, M.A.: On convergence of kernel learning estimators. SIAM J. Optim. 20(3), 1205–1223 (2009). https://doi.org/10.1137/070696817
Pagès, G.: A space quantization method for numerical integration. J. Comput. Appl. Math. 89(1), 1–38 (1998). https://doi.org/10.1016/S0377-0427(97)00190-8. (ISSN 0377-0427)
Pflug, G., Pichler, A.: Approximations for probability distributions and stochastic optimization problems. In: Bertocchi, M., Consigli, G., Dempster, M.A.H. (eds.) Stochastic Optimization Methods in Finance and Energy Volume 163 of International Series in Operations Research & Management Science, chapter 15, pp. 343–387. Springer, New York (2011). https://doi.org/10.1007/978-1-4419-9586-5. (ISBN 978-1-4419-9586-5)
Pflug, Ch. G., Pichler. A.: Multistage Stochastic Optimization. Springer Series in Operations Research and Financial Engineering. Springer, Berlin (2014). https://doi.org/10.1007/978-3-319-08843-3. https://books.google.com/books?id=q_VWBQAAQBAJ. (ISBN 978-3-319-08842-6)
Pflug, G.C., Pichler, A.: From empirical observations to tree models for stochastic optimization: convergence properties. SIAM J. Optim. 26(3), 1715–1740 (2016). https://doi.org/10.1137/15M1043376
Pflug, Ch G., Wozabal, D.: Ambiguity in portfolio selection. Quant. Finance 7(4), 435–442 (2007). https://doi.org/10.1080/14697680701455410
Pichler, A.: The natural Banach space for version independent risk measures. Insur. Math. Econ. 53(2), 405–415 (2013). https://doi.org/10.1016/j.insmatheco.2013.07.005
Pichler, A., Shapiro, A.: Minimal representations of insurance prices. Insur. Math. Econ. 62, 184–193 (2015). https://doi.org/10.1016/j.insmatheco.2015.03.011
Pólik, I., Terlaky, T.: A survey of the S-lemma. SIAM Rev. 49, 371–418 (2007). https://doi.org/10.2307/20453987
Prokhorov, Y.V.: Convergence of random processes and limit theorems in probability theory. Theory Probab. Appl. 1, 157–214 (1956)
Rachev, S.T.: Probability Metrics and the Stability of Stochastic Models. Wiley, West Sussex (1991). http://books.google.com/books?id=5grvAAAAMAAJ
Rachev, S.T., Römisch, W.: Quantitative stability in stochastic programming: the method of probability metrics. Math. Oper. Res. 27(4), 792–818 (2002). https://doi.org/10.1287/moor.27.4.792.304
Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)
Römisch, W.: Stability of stochastic programming problems. In: Ruszczyński, A., Shapiro, A. (eds.) Stochastic Programming, Handbooks in Operations Research and Management Science, volume 10, chapter 8. Elsevier, Amsterdam (2003)
Shapiro, A.: On Kusuoka representation of law invariant risk measures. Math. Oper. Res. 38(1), 142–152 (2013). https://doi.org/10.1287/moor.1120.0563
Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on Stochastic Programming. MOS-SIAM Series on Optimization, 2nd edn. SIAM, Philadelphia (2014). https://doi.org/10.1137/1.9780898718751
Skorokhod, A.V.: Basic Principles and Applications of Probability Theory. Springer, New York (1989)
Sun, H., Xu, H.: Convergence analysis for distributionally robust optimization and equilibrium problems. Math. Oper. Res. 41, 377–401 (2015)
Villani, C.: Topics in Optimal Transportation, volume 58 of Graduate Studies in Mathematics. American Mathematical Society, Providence (2003). https://doi.org/10.1090/gsm/058. (ISBN 0-821-83312-X)
Wiesemann, W., Kuhn, D., Sim, M.: Distributionally robust convex optimization. Oper. Res. 62, 1358–1376 (2014)
Xu, H., Liu, Y., Sun, H.: Distributionally robust optimization with matrix moment constraints: Lagrange duality and cutting plane method (2017)
Žáčková, J.: On minimax solutions of stochastic linear programming problems. Časopis pro pěstování mathematiky 91, 423–430 (1966)
Zhang, J., Xu, H., Zhang, L.W.: Quantitative stability analysis for distributionally robust optimization with moment constraints (2016)
Zhang, J., Xu, H., Zhang, L.W.: Quantitative stability analysis of stochastic quasi-variational inequality problems and applications (2017)
Zhao, C., Guan, Y.: Data-driven risk-averse two-stage stochastic program with \(\zeta \)-structure probability metrics. Optim. Online. http://www.optimization-online.org/DB_HTML/2015/07/5014.html
Zhao, C., Guan, Y.: Data-driven risk-averse stochastic optimization with wasserstein metrics. Optimization Online. http://www.optimization-online.org/DB_HTML/2015/05/4902.html
Zolotarev, V.M.: Probability metrics. Teoriya Veroyatnostei i ee Primeneniya 28, 264–287 (1983)
Zymler, S., Kuhn, D., Rustem, B.: Distributionally robust joint chance constraints with second-order moment information. Mathem. Program. 137, 167–198 (2013)
Acknowledgements
We would like to thank Jie Zhang for an initial proof of Theorem 1 and Shaoyan Guo for careful reading of the paper. We would also like to thank the guest editor and the two anonymous referees for insightful comments which help us significantly strengthen this paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Pichler, A., Xu, H. Quantitative stability analysis for minimax distributionally robust risk optimization. Math. Program. 191, 47–77 (2022). https://doi.org/10.1007/s10107-018-1347-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-018-1347-4