[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Distributionally robust optimization with polynomial densities: theory, models and algorithms

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

Abstract

In distributionally robust optimization the probability distribution of the uncertain problem parameters is itself uncertain, and a fictitious adversary, e.g., nature, chooses the worst distribution from within a known ambiguity set. A common shortcoming of most existing distributionally robust optimization models is that their ambiguity sets contain pathological discrete distributions that give nature too much freedom to inflict damage. We thus introduce a new class of ambiguity sets that contain only distributions with sum-of-squares (SOS) polynomial density functions of known degrees. We show that these ambiguity sets are highly expressive as they conveniently accommodate distributional information about higher-order moments, conditional probabilities, conditional moments or marginal distributions. Exploiting the theoretical properties of a measure-based hierarchy for polynomial optimization due to Lasserre (SIAM J Optim 21(3):864–885, 2011), we prove that certain worst-case expectation constraints are polynomial-time solvable under these new ambiguity sets. We also show how SOS densities can be used to approximately solve the general problem of moments. We showcase the applicability of the proposed approach in the context of a stylized portfolio optimization problem and a risk aggregation problem of an insurance company.

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
£29.99 /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 (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009)

    Book  MATH  Google Scholar 

  2. Bertsimas, D., Popescu, I.: On the relation between option and stock prices: a convex optimization approach. Oper. Res. 50(2), 358–374 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bertsimas, D., Popescu, I.: Optimal inequalities in probability theory: a convex optimization approach. SIAM J. Optim. 15(3), 780–804 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bertsekas, D.P.: Convex Optimization Theory. Athena Scientific, Belmont (2009)

    MATH  Google Scholar 

  5. Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer, New York (1997)

    MATH  Google Scholar 

  6. Cont, R.: Empirical properties of asset returns: stylized facts and statistical issues. Quant. Finance 1, 223–236 (2001)

    Article  MATH  Google Scholar 

  7. den 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)

    Article  Google Scholar 

  8. De Klerk, E., Laurent, M.: Comparison of Lasserre’s measure-based bounds for polynomial optimization to bounds obtained by simulated annealing. Math. Oper. Res. 43(4), 1317–1325 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  9. De Klerk, E., Laurent, M.: Worst-case examples for Lasserre’s measure–based hierarchy for polynomial optimization on the hypercube (2018). Preprint available at arXiv:1804.05524

  10. De Klerk, E., Laurent, M., Sun, Z.: Convergence analysis for Lasserre’s measure-based hierarchy of upper bounds for polynomial optimization. Math. Program. Ser. A 162(1), 363–392 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  11. Dantzig, G.B.: Linear programming under uncertainty. Manag. Sci. 1(3–4), 197–206 (1955)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  13. Doan, X.V., Li, X., Natarajan, K.: Robustness to dependency in portfolio optimization using overlapping marginals. Oper. Res. 63(6), 1468–1488 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  14. Doan, X.V., Natarajan, K.: On the complexity of nonoverlapping multivariate marginal bounds for probabilistic combinatorial optimization problems. Oper. Res. 60(1), 138–49 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  15. Fiala, J., Kočvara, M., Michael Stingl, M.: PENLAB: a MATLAB solver for nonlinear semidefinite optimization. http://arxiv.org/pdf/1311.5240v1.pdf (2013)

  16. Genz, A., Cools, R.: An adaptive numerical cubature algorithm for simplices. ACM Trans. Math. Softw. 29(3), 297–308 (2003)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  18. Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The John Hopkins University Press, Baltimore (1996)

    MATH  Google Scholar 

  19. Grant, M., Boyd, S.: CVX: Matlab Software for Disciplined Convex Programming. http://cvxr.com/cvx (2014)

  20. Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, New York (1988)

    Book  MATH  Google Scholar 

  21. Grundmann, A., Moeller, H.M.: Invariant integration formulas for the \(n\)-simplex by combinatorial methods. SIAM J. Numer. Anal. 15, 282–290 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  22. Hanasusanto, G.A., Roitch, V., Kuhn, D., Wiesemann, W.: A distributionally robust perspective on uncertainty quantification and chance constrained programming. Math. Program. Ser. B 151(1), 35–62 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  23. Hanasusanto, G.A., Roitch, V., Kuhn, D., Wiesemann, W.: Ambiguous joint chance constraints under mean and dispersion information. Oper. Res. 65(3), 751–767 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  24. Hanasusanto, G.A., Kuhn, D., Wallace, S.W., Zymler, S.: Distributionally robust multi-item newsvendor problems with multimodal demand distributions. Math. Program. Ser. A 152(1), 1–32 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  25. Kroo, A., Szilárd, R.: On Bernstein and Markov-type inequalities for multivariate polynomials on convex bodies. J. Approx. Theory 99(1), 134–152 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  26. Lasserre, J.B., Zeron, E.S.: Solving a class of multivariate integration problems via Laplace techniques. Appl. Math. 28(4), 391–405 (2001)

    MathSciNet  MATH  Google Scholar 

  27. Lasserre, J.B.: A semidefinite programming approach to the generalized problem of moments. Math. Program. Ser. B 112, 65–92 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  28. Lasserre, J.B.: A new look at nonnegativity on closed sets and polynomial optimization. SIAM J. Optim. 21(3), 864–885 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  29. Lasserre, J.B.: The \({\mathbf{K}}\)-moment problem for continuous linear functionals. Trans. Am. Math. Soc. 365(5), 2489–2504 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  30. Lasserre, J.B., Weisser, T.: Representation of distributionally robust chance-constraints (2018). Preprint available at arXiv:1803.11500

  31. Li, B., Jiang, R., Mathieu, J.L.: Ambiguous risk constraints with moment and unimodality information. Mathematical Programming Series A (to appear) (2017). Preprint available at http://www.optimization-online.org/DB_FILE/2016/09/5635.pdf

  32. Löfberg, J.: YALMIP: a toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD Conference (2004)

  33. McNeil, A., Frey, R., Embrechts, P.: Quantitative Risk Management: Concepts, Techniques and Tools. Princeton University Press, Princeton (2015)

    MATH  Google Scholar 

  34. Marichal, J.-L., Mossinghof, M.J.: Slices, slabs, and sections of the unit hypercube. Online J. Anal. Comb. 3, 1–11 (2008)

    MathSciNet  MATH  Google Scholar 

  35. Mevissen, M., Ragnoli, E., Yu, J.Y.: Data-driven distributionally robust polynomial optimization. In: Burges, C.J.C., Bottou, L., Welling, M., Ghahramani, Z., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems 26, pp. 37–45. Curran Associates, Inc. (2013)

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

    Article  MathSciNet  MATH  Google Scholar 

  37. Natarajan, K., Pachamanova, D., Sim, M.: Constructing risk measures from uncertainty sets. Oper. Res. 57(5), 1129–1141 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  38. Pflug, G.C., Pichler, A., Wozabal, D.: The \(1/N\) investment strategy is optimal under high model ambiguity. J. Bank. Finance 36(2), 410–417 (2012)

    Article  Google Scholar 

  39. Pflug, G.C., Wozabal, D.: Ambiguity in portfolio selection. Quant. Finance 7, 435–442 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  40. Popescu, I.: A semidefinite programming approach to optimal-moment bounds for convex classes of distributions. Math. Oper. Res. 30(3), 632–657 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  41. Prékopa, A.: Stochastic Programming. Kluwer Academic Publishers, Berlin (1995)

    Book  MATH  Google Scholar 

  42. Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)

    Book  MATH  Google Scholar 

  43. Rogosinski, W.W.: Moments of non-negative mass. Proc. R. Soc. A 245, 1–27 (1958)

    MathSciNet  MATH  Google Scholar 

  44. Scarf, H.: A min–max solution of an inventory problem. In: Scarf, H., Arrow, K., Karlin, S. (eds.) Studies in the Mathematical Theory of Inventory and Production, vol. 10, pp. 201–209. Stanford University Press, Redwood City (1958)

    Google Scholar 

  45. Sklar, A.: Fonctions de répartition à \(n\) dimensions et leurs marges. Publications de l’Institut de Statistique de L’Université de Paris 8, 229–231 (1959)

    MathSciNet  MATH  Google Scholar 

  46. Shapiro, A.: On duality theory of conic linear problems. In: Goberna, M.Á., López, M.A. (eds.) Semi-Infinite Programming: Recent Advances, pp. 135–165. Springer, New York (2001)

    Chapter  Google Scholar 

  47. Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on Stochastic Programming: Modeling and Theory. SIAM, Philadelphia (2009)

    Book  MATH  Google Scholar 

  48. Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. In: Optimization Methods and Software, pp. 11–12, 625–653 (1999)

  49. Van Parys, B.P.G., Goulart, P.J., Embrechts, P.: Fréchet inequalities via convex optimization (2016). Preprint available at http://www.optimization-online.org/DB_FILE/2016/07/5536.pdf

  50. Van Parys, B.P.G., Goulart, P.J., Kuhn, D.: Generalized Gauss inequalities via semidefinite programming. Math. Program. Ser. A 156(1–2), 271–302 (2016)

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  52. Žáčková, J.: On minimax solutions of stochastic linear programming problems. Časopis pro pěstování matematiky 91, 423–430 (1966)

    MathSciNet  MATH  Google Scholar 

  53. Zuluaga, L., Peña, J.F.: A conic programming approach to generalized Tchebycheff inequalities. Math. Oper. Res. 30(2), 369–388 (2005)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

Etienne de Klerk would like to thank Dorota Kurowicka and Jean Bernard Lasserre for valuable discussions and references. Daniel Kuhn gratefully acknowledges financial support from the Swiss National Science Foundation under grant BSCGI0_157733.

Author information

Authors and Affiliations

  1. Tilburg University, Tilburg, The Netherlands

    Etienne de Klerk

  2. EPFL, Lausanne, Switzerland

    Daniel Kuhn

  3. Erasmus University Rotterdam, Rotterdam, The Netherlands

    Krzysztof Postek

Authors
  1. Etienne de Klerk
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Daniel Kuhn
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Krzysztof Postek
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Daniel Kuhn.

Additional information

Publisher's Note

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

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

de Klerk, E., Kuhn, D. & Postek, K. Distributionally robust optimization with polynomial densities: theory, models and algorithms. Math. Program. 181, 265–296 (2020). https://doi.org/10.1007/s10107-019-01429-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-019-01429-5

Keywords

Mathematics Subject Classification

Search

Navigation