×

zbMATH — the first resource for mathematics

Distributionally robust optimization with polynomial densities: theory, models and algorithms. (English) Zbl 07212155
Summary: 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.

MSC:
90C17 Robustness in mathematical programming
90C22 Semidefinite programming
90C26 Nonconvex programming, global optimization
90C15 Stochastic programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ben-Tal, A.; El Ghaoui, L.; Nemirovski, A., Robust Optimization (2009), Princeton: Princeton University Press, Princeton
[2] Bertsimas, D.; Popescu, I., On the relation between option and stock prices: a convex optimization approach, Oper. Res., 50, 2, 358-374 (2002) · Zbl 1163.91382
[3] Bertsimas, D.; Popescu, I., Optimal inequalities in probability theory: a convex optimization approach, SIAM J. Optim., 15, 3, 780-804 (2005) · Zbl 1077.60020
[4] Bertsekas, DP, Convex Optimization Theory (2009), Belmont: Athena Scientific, Belmont
[5] Birge, JR; Louveaux, F., Introduction to Stochastic Programming (1997), New York: Springer, New York · Zbl 0892.90142
[6] Cont, R., Empirical properties of asset returns: stylized facts and statistical issues, Quant. Finance, 1, 223-236 (2001) · Zbl 1408.62174
[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)
[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) · Zbl 1440.90044
[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 · Zbl 1442.90141
[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) · Zbl 1358.90092
[11] Dantzig, GB, Linear programming under uncertainty, Manag. Sci., 1, 3-4, 197-206 (1955) · Zbl 0995.90589
[12] Delage, E.; Ye, Y., Distributionally robust optimization under moment uncertainty with application to data-driven problems, Oper. Res., 58, 3, 595-612 (2010) · Zbl 1228.90064
[13] Doan, XV; Li, X.; Natarajan, K., Robustness to dependency in portfolio optimization using overlapping marginals, Oper. Res., 63, 6, 1468-1488 (2015) · Zbl 1347.91227
[14] Doan, XV; Natarajan, K., On the complexity of nonoverlapping multivariate marginal bounds for probabilistic combinatorial optimization problems, Oper. Res., 60, 1, 138-49 (2012) · Zbl 1245.90099
[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) · Zbl 1072.65032
[17] Goh, J.; Sim, M., Distributionally robust optimization and its tractable approximations, Oper. Res., 58, 4, 902-917 (2010) · Zbl 1228.90067
[18] Golub, GH; Van Loan, CF, Matrix Computations (1996), Baltimore: The John Hopkins University Press, Baltimore
[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 (1988), New York: Springer, New York · Zbl 0634.05001
[21] Grundmann, A.; Moeller, HM, Invariant integration formulas for the \(n\)-simplex by combinatorial methods, SIAM J. Numer. Anal., 15, 282-290 (1978) · Zbl 0376.65013
[22] Hanasusanto, GA; 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) · Zbl 1328.90090
[23] Hanasusanto, GA; Roitch, V.; Kuhn, D.; Wiesemann, W., Ambiguous joint chance constraints under mean and dispersion information, Oper. Res., 65, 3, 751-767 (2017) · Zbl 1387.90271
[24] Hanasusanto, GA; Kuhn, D.; Wallace, SW; Zymler, S., Distributionally robust multi-item newsvendor problems with multimodal demand distributions, Math. Program. Ser. A, 152, 1, 1-32 (2015) · Zbl 1327.90153
[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) · Zbl 0952.41012
[26] Lasserre, JB; Zeron, ES, Solving a class of multivariate integration problems via Laplace techniques, Appl. Math., 28, 4, 391-405 (2001) · Zbl 1008.65016
[27] Lasserre, JB, A semidefinite programming approach to the generalized problem of moments, Math. Program. Ser. B, 112, 65-92 (2008) · Zbl 1145.90049
[28] Lasserre, JB, A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim., 21, 3, 864-885 (2011) · Zbl 1242.90176
[29] Lasserre, JB, The \({\mathbf{K}} \)-moment problem for continuous linear functionals, Trans. Am. Math. Soc., 365, 5, 2489-2504 (2012) · Zbl 1275.44003
[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 · Zbl 1410.90139
[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 (2015), Princeton: Princeton University Press, Princeton · Zbl 1337.91003
[34] Marichal, J-L; Mossinghof, MJ, Slices, slabs, and sections of the unit hypercube, Online J. Anal. Comb., 3, 1-11 (2008) · Zbl 1189.52011
[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) · Zbl 1433.90095
[37] Natarajan, K.; Pachamanova, D.; Sim, M., Constructing risk measures from uncertainty sets, Oper. Res., 57, 5, 1129-1141 (2009) · Zbl 1233.91153
[38] Pflug, GC; Pichler, A.; Wozabal, D., The \(1/N\) investment strategy is optimal under high model ambiguity, J. Bank. Finance, 36, 2, 410-417 (2012)
[39] Pflug, GC; Wozabal, D., Ambiguity in portfolio selection, Quant. Finance, 7, 435-442 (2007) · Zbl 1190.91138
[40] Popescu, I., A semidefinite programming approach to optimal-moment bounds for convex classes of distributions, Math. Oper. Res., 30, 3, 632-657 (2005) · Zbl 1082.60011
[41] Prékopa, A., Stochastic Programming (1995), Berlin: Kluwer Academic Publishers, Berlin
[42] Rockafellar, RT, Convex Analysis (1970), Princeton: Princeton University Press, Princeton
[43] Rogosinski, WW, Moments of non-negative mass, Proc. R. Soc. A, 245, 1-27 (1958) · Zbl 0082.32404
[44] Scarf, H.; Scarf, H.; Arrow, K.; Karlin, S., A min-max solution of an inventory problem, Studies in the Mathematical Theory of Inventory and Production, 201-209 (1958), Redwood City: Stanford University Press, Redwood City
[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) · Zbl 0100.14202
[46] Shapiro, A.; Goberna, MÁ; López, MA, On duality theory of conic linear problems, Semi-Infinite Programming: Recent Advances, 135-165 (2001), New York: Springer, New York · Zbl 1055.90088
[47] Shapiro, A.; Dentcheva, D.; Ruszczyński, A., Lectures on Stochastic Programming: Modeling and Theory (2009), Philadelphia: SIAM, Philadelphia · Zbl 1183.90005
[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) · Zbl 0973.90526
[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, BPG; Goulart, PJ; Kuhn, D., Generalized Gauss inequalities via semidefinite programming, Math. Program. Ser. A, 156, 1-2, 271-302 (2016) · Zbl 1351.90125
[51] Wiesemann, W.; Kuhn, D.; Sim, M., Distributionally robust convex optimization, Oper. Res., 62, 6, 1358-1376 (2014) · Zbl 1327.90158
[52] Žáčková, J., On minimax solutions of stochastic linear programming problems, Časopis pro pěstování matematiky, 91, 423-430 (1966) · Zbl 0161.17102
[53] Zuluaga, L.; Peña, JF, A conic programming approach to generalized Tchebycheff inequalities, Math. Oper. Res., 30, 2, 369-388 (2005) · Zbl 1082.90089
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.