[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Nonlinear distributionally robust optimization

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

This article focuses on a class of distributionally robust optimization (DRO) problems where, unlike the growing body of the literature, the objective function is potentially nonlinear in the distribution. Existing methods to optimize nonlinear functions in probability space use the Frechet derivatives, which present both theoretical and computational challenges. Motivated by this, we propose an alternative notion for the derivative and corresponding smoothness based on Gateaux (G)-derivative for generic risk measures. These concepts are explained via three running risk measure examples of variance, entropic risk, and risk on finite support sets. We then propose a G-derivative based Frank–Wolfe (FW) algorithm for generic nonlinear optimization problems in probability spaces and establish its convergence under the proposed notion of smoothness in a completely norm-independent manner. We use the set-up of the FW algorithm to devise a methodology to compute a saddle point of the nonlinear DRO problem. Finally, we validate our theoretical results on two cases of the entropic and variance risk measures in the context of portfolio selection problems. In particular, we analyze their regularity conditions and “sufficient statistic”, compute the respective FW-oracle in various settings, and confirm the theoretical outcomes through numerical validation.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Algorithm 1
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Notes

  1. A function \( f: {\mathcal {S}} \rightarrow \mathbb {R} \) is said to affine if \( f(x + \theta (y - x)) = f(x) + \theta (f(y) - f(x)) \) for every \( x,y \in {\mathcal {S}} \) and \( \theta \in [0,1] \).

  2. \( \nabla _1 F(x,\mathbb {P}) :==\big ( \nicefrac {\partial F}{\partial x} \big ) (x, \mathbb {P}) \) denotes the partial derivative of \( F \) w.r.t. \( x \) evaluated at \( (x,\mathbb {P}) \).

  3. The coloured figures are available in online version.

References

  1. Bertsimas, D., Brown, D.B., Caramanis, C.: Theory and applications of robust optimization. SIAM Rev. 53, 464–501 (2011)

    Article  MathSciNet  Google Scholar 

  2. Smith, J.E., Winkler, R.L.: The optimizer’s curse: skepticism and postdecision surprise in decision analysis. Manage. Sci. 52, 311–322 (2006)

    Article  Google Scholar 

  3. Scarf, H.: A min max solution of an inventory problem. In: Studies in the Mathematical Theory of Inventory and Production (1958)

  4. Delage, E., Ye, Y.: Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper. Res. 58, 595–612 (2010)

    Article  MathSciNet  Google Scholar 

  5. Goh, J., Sim, M.: Distributionally robust optimization and its tractable approximations. Oper. Res. 58, 902–917 (2010)

    Article  MathSciNet  Google Scholar 

  6. Wiesemann, W., Kuhn, D., Sim, M.: Distributionally robust convex optimization. Oper. Res. 62, 1358–1376 (2014)

    Article  MathSciNet  Google Scholar 

  7. Erdoğan, E., Iyengar, G.: Ambiguous chance constrained problems and robust optimization. Math. Program. 107, 37–61 (2006)

    Article  MathSciNet  Google Scholar 

  8. Jiang, R., Guan, Y.: Data-driven chance constrained stochastic program. Math. Program. 158, 291–327 (2016)

    Article  MathSciNet  Google Scholar 

  9. Duchi, J.C., Namkoong, H.: Learning models with uniform performance via distributionally robust optimization. Ann. Stat. 49, 1378–1406 (2021)

    Article  MathSciNet  Google Scholar 

  10. Mohajerin Esfahani, P., Kuhn, D.: Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations. Math. Program. 171, 115–166 (2018)

    Article  MathSciNet  Google Scholar 

  11. Blanchet, J., Murthy, K., Zhang, F.: Optimal transport-based distributionally robust optimization: structural properties and iterative schemes. Math. Oper. Res. 47, 1500–1529 (2022)

    Article  MathSciNet  Google Scholar 

  12. Gao, R.: Finite-sample guarantees for Wasserstein distributionally robust optimization: breaking the curse of dimensionality. Oper. Res. (2022)

  13. Gao, R., Kleywegt, A.: Distributionally robust stochastic optimization with Wasserstein distance. Math. Oper. Res. (2022)

  14. Wang, J., Gao, R., Xie, Y.: Sinkhorn distributionally robust optimization. preprint available at arXiv:2109.11926 (2021)

  15. Rahimian, H., Mehrotra, S., Distributionally robust optimization: a review. preprint available at arXiv:1908.05659 (2019)

  16. Kuhn, D., Mohajerin Esfahani, P., Nguyen, V.A., Shafieezadeh-Abadeh, S.: Wasserstein distributionally robust optimization: theory and applications in machine learning. In: Operations Research & Management Science in the Age of Analytics, Informs, pp. 130–166 (2019)

  17. Postek, K., den Hertog, D., Melenberg, B.: Computationally tractable counterparts of distributionally robust constraints on risk measures. SIAM Rev. 58, 603–650 (2016)

    Article  MathSciNet  Google Scholar 

  18. Zymler, S., Kuhn, D., Rustem, B.: Worst-case value at risk of nonlinear portfolios. Manage. Sci. 59, 172–188 (2013)

    Article  Google Scholar 

  19. Rujeerapaiboon, N., Kuhn, D., Wiesemann, W.: Robust growth-optimal portfolios. Manage. Sci. 62, 2090–2109 (2016)

    Article  Google Scholar 

  20. Shafieezadeh-Abadeh, S., Esfahani, P.M., Kuhn, D.: Distributionally robust logistic regression. Adv. Neural Inf. Process. Syst. 28 (2015)

  21. Cai, J., Li, J., Mao, T.: Distributionally robust optimization under distorted expectations. Available at SSRN 3566708 (2020)

  22. Zhen, J., Kuhn, D., Wiesemann, W.: Mathematical foundations of robust and distributionally robust optimization. preprint available at arXiv:2105.00760 (2021)

  23. Nguyen, V.A., Abadeh, S.S., Filipović, D., Kuhn, D.: Mean-covariance robust risk measurement. preprint available at arXiv:2112.09959 (2021)

  24. Blanchet, J., Chen, L., Zhou, X.Y.: Distributionally robust mean-variance portfolio selection with Wasserstein distances. Manage. Sci. 68, 6382–6410 (2022)

    Article  Google Scholar 

  25. Chen, Y., Hu, Y.: Multivariate coherent risk measures induced by multivariate convex risk measures. Positivity 24, 711–727 (2020)

    Article  MathSciNet  Google Scholar 

  26. Song, H., Zeng, X., Chen, Y., Hu, Y.: Multivariate shortfall and divergence risk statistics. Entropy 21, 1031 (2019)

    Article  MathSciNet  Google Scholar 

  27. Shafieezadeh-Abadeh, S., Aolaritei, L., Dörfler, F., Kuhn, D.: New perspectives on regularization and computation in optimal transport-based distributionally robust optimization. preprint available at arXiv:2303.03900 (2023)

  28. Jaggi, M.: Revisiting Frank-Wwolfe: projection-free sparse convex optimization. In: International Conference on Machine Learning, PMLR, pp. 427–435 (2013)

  29. Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Res. Logist. Quart. 3, 95–110 (1956)

    Article  MathSciNet  Google Scholar 

  30. Clarkson, K.L.: Coresets, sparse greedy approximation, and the Frank–Wolfe algorithm. ACM Trans. Algorithms (TALG) 6, 1–30 (2010)

    Article  MathSciNet  Google Scholar 

  31. Kent, C., Blanchet, J., Glynn, P.: Frank–Wolfe methods in probability space. preprint available at arXiv:2105.05352 (2021)

  32. Liu, L., Zhang, Y., Yang, Z., Babanezhad, R., Wang, Z.: Infinite-dimensional optimization for zero-sum games via variational transport. In: International Conference on Machine Learning, PMLR, pp. 7033–7044 (2021)

  33. Nemirovski, A.: Prox-method with rate of convergence o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15, 229–251 (2004)

    Article  MathSciNet  Google Scholar 

  34. Hamedani, E.Y., Jalilzadeh, A., Aybat, N.S., Shanbhag, U.V.: Iteration complexity of randomized primal-dual methods for convex-concave saddle point problems. arXiv preprint arXiv:1806.04118, 5 (2018)

  35. Nguyen, D. H., Sakurai, T.: A particle-based algorithm for distributional optimization on\(\backslash \)Constrained Domains via variational transport and mirror descent. arXiv preprint arXiv:2208.00587 (2022)

  36. Nemirovskij, A., Yudin, D.: Problem Complexity and Method Efficiency in Optimization. New York (1983)

  37. Sheriff, M., Mohajerin Esfahani, P.: Distributionally Robust Optimization. https://github.com/MRayyanS/DRO (2024)

  38. Bertsekas, D.P.: Control of uncertain systems with a set-membership description of the uncertainty., PhD thesis, Massachusetts Institute of Technology, (1971)

  39. Lanzetti, N., Bolognani, S., Dörfler, F., First-order conditions for optimization in the Wasserstein space. arXiv preprint arXiv:2209.12197 (2022)

  40. Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course, vol. 87. Springer Science & Business Media, Berlin (2003)

    Google Scholar 

  41. Gao, R., Chen, X., Kleywegt, A.J.: Wasserstein distributionally robust optimization and variation regularization. Oper. Res. (2022)

  42. Demyanov, A.M.V., Rubinov, F.: Approximate methods in optimization problems. Modern Anal. Comput. Methods Sci. Math. (1970)

  43. Dem’yanov, A.M.V., Rubinov, F.: Minimization of functionals in normed spaces. SIAM J. Control 6, 73–88 (1968)

    Article  MathSciNet  Google Scholar 

  44. Pedregosa, F., Negiar, G., Askari, A., Jaggi, M.: Linearly convergent Frank-Wolfe with backtracking line-search. In: International Conference on Artificial Intelligence and Statistics, PMLR, pp. 1–10 (2020)

  45. Nguyen, V.A., Shafieezadeh-Abadeh, S., Kuhn, D., Mohajerin Esfahani, P.: Bridging Bayesian and minimax mean square error estimation via Wasserstein distributionally robust optimization. Math. Oper. Res. 48, 1–37 (2023)

  46. Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imag. Sci. 2, 183–202 (2009)

    Article  MathSciNet  Google Scholar 

  47. Nesterov, Y.: A method of solving a convex programming problem with convergence rate o (1/k** 2). Dokl. Akad. Nauk SSSR 269, 543 (1983)

    MathSciNet  Google Scholar 

  48. Korpelevich, G.M.: The extragradient method for finding saddle points and other problems. Matecon 12, 747–756 (1976)

    MathSciNet  Google Scholar 

  49. Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103, 127–152 (2005)

    Article  MathSciNet  Google Scholar 

  50. Markowitz, H.M.: Portfolio selection. J. Financ. 7 (1), (1952)

  51. Pflug, G., Wozabal, D.: Ambiguity in portfolio selection. Quantit. Financ. 7, 435–442 (2007)

    Article  MathSciNet  Google Scholar 

  52. Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)

    Book  Google Scholar 

  53. Uhlig, F.: A recurring theorem about pairs of quadratic forms and extensions: a survey. Linear Algebra Appl. 25, 219–237 (1979)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Delft Center for Systems and Control, Delft University of Technology, Delft, The Netherlands

    Mohammed Rayyan Sheriff & Peyman Mohajerin Esfahani

Authors
  1. Mohammed Rayyan Sheriff
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Peyman Mohajerin Esfahani
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Peyman Mohajerin Esfahani.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The authors acknowledge the fruitful discussions with Armin Eftekhari. This research is supported by the European Research Council (ERC) under the grant TRUST-949796.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sheriff, M.R., Mohajerin Esfahani, P. Nonlinear distributionally robust optimization. Math. Program. (2024). https://doi.org/10.1007/s10107-024-02151-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10107-024-02151-7

Keywords

Mathematics Subject Classification

Search

Navigation