The discrete moment problem with nonconvex shape constraints. (English) Zbl 1470.90060

Summary: The discrete moment problem is a foundational problem in distribution-free robust optimization, where the goal is to find a worst-case distribution that satisfies a given set of moments. This paper studies the discrete moment problems with additional shape constraints that guarantee the worst-case distribution is either log-concave (LC), has an increasing failure rate (IFR), or increasing generalized failure rate (IGFR). These classes of shape constraints have not previously been studied in the literature, in part due to their inherent nonconvexities. Nonetheless, these classes are useful in practice, with applications in revenue management, reliability, and inventory control. We characterize the structure of optimal extreme point distributions under these constraints. We show, for example, that an optimal extreme point solution to a moment problem with \(m\) moments and LC shape constraints is piecewise geometric with at most \(m\) pieces. This optimality structure allows us to design an exact algorithm for computing optimal solutions in a low-dimensional space of parameters. We also leverage this structure to study a robust newsvendor problem with shape constraints and compute optimal solutions.
The e-companion is available at https://doi.org/10.1287/opre.2020.1990.


90C17 Robustness in mathematical programming


ROME; logcondiscr
Full Text: DOI arXiv


[1] Aliprantis C, Border K (2006) Infinite Dimensional Analysis: A Hitchhiker’s Guide, 3rd ed. (Springer Verlag, Berlin, Heidelberg).Google Scholar
[2] An M (1997) Log-concave probability distributions: Theory and statistical testing. Working paper, Duke University, Durham, NC.Google Scholar
[3] Bagnoli M, Bergstrom T (2005) Log-concave probability and its applications. Econom. Theory 26(2):445-469.Crossref, Google Scholar · Zbl 1077.60012
[4] Bagnoli M, Salant SW, Swierzbinski JE (1989) Durable-goods monopoly with discrete demand. J. Political Econom. 97(6):1459-1478.Crossref, Google Scholar
[5] Balabdaoui F, Jankowski H, Rufibach K, Pavlides M (2011) Asymptotics of the discrete log-concave maximum likelihood estimator and related applications. J. Royal Statist. Soc. Ser. A 75(4):769-790.Crossref, Google Scholar · Zbl 1411.62119
[6] Banciu M, Mirchandani P (2013) New results concerning probability distributions with increasing generalized failure rates. Oper. Res. 61(4):925-931.Link, Google Scholar · Zbl 1291.90078
[7] Bandi C, Bertsimas D (2012) Tractable stochastic analysis in high dimensions via robust optimization. Math. Programming 134:23-70.Crossref, Google Scholar · Zbl 1263.90001
[8] Barlow R, Proschan F (1996) Mathematical Theory of Reliability, volume 17 (SIAM, Philadelphia).Crossref, Google Scholar · Zbl 0132.39302
[9] Baron DP, Myerson RB (1982) Regulating a monopolist with unknown costs. Econometrica 50(4):911-930.Google Scholar · Zbl 0483.90019
[10] 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
[11] Bertsimas D, Gupta V, Kallus N (2018) Data-driven robust optimization. Math. Programming 167(2):235-292.Crossref, Google Scholar · Zbl 1397.90298
[12] Bertsimas D, Natarajan K, Teo CP (2006) Persistence in discrete optimization under data uncertainty. Math. Programming 108(2):251-274.Crossref, Google Scholar · Zbl 1130.90365
[13] Burer S (2009) On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Programming 120(2):479-495.Crossref, Google Scholar · Zbl 1180.90234
[14] Canonne CL, Diakonikolas I, Gouleakis T, Rubinfeld R (2018) Testing shape restrictions of discrete distributions. Theory Comput. Systems 62(1):4-62.Crossref, Google Scholar · Zbl 1386.68215
[15] Chakraborty S (2015) Generating discrete analogues of continuous probability distributions—A survey of methods and constructions. J. Statist. Distributed Appl. 2(1):article 6.Google Scholar · Zbl 1359.62053
[16] Chen Z, Sim M, Xu H (2019) Distributionally robust optimization with infinitely constrained ambiguity sets. Oper. Res. 67(5):1328-1344.Google Scholar · Zbl 1455.90117
[17] Dai T, Jerath K (2016) Impact of inventory on quota-bonus contracts with rent sharing. Oper. Res. 64(1):94-98.Link, Google Scholar · Zbl 1338.90024
[18] Delage E, Ye Y (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
[19] Dennis J, Jr, Schnabel R (1996) Numerical Methods for Unconstrained Optimization and Nonlinear Equations, volume 16 (SIAM, Philadelphia).Crossref, Google Scholar
[20] Duembgen L, Huesler A, Rufibach K (2011) Active set and EM algorithms for log-concave densities based on complete and censored data. arXiv preprint arXiv:0707.4643v4.Google Scholar
[21] Gao R, Kleywegt AJ (2016) Distributionally robust stochastic optimization with Wasserstein distance. arXiv preprint arXiv:1604.02199.Google Scholar
[22] Gao R, Chen X, Kleywegt AJ (2017) Wasserstein distributional robustness and regularization in statistical learning. arXiv preprint arXiv:1712.06050.Google Scholar
[23] Gavirneni S, Kapuscinski R, Tayur S (1999) Value of information in capacitated supply chains. Management Sci. 45(1):16-24.Link, Google Scholar · Zbl 1231.90088
[24] Goh J, Sim M (2010) Distributionally robust optimization and its tractable approximations. Oper. Res. 58(4-part-1):902-917.Google Scholar · Zbl 1228.90067
[25] Han Q, Du D, Zuluaga LF (2014) Technical note: A risk and ambiguity-averse extension of the max-min newsvendor order formula. Oper. Res. 62(3):535-542.Link, Google Scholar · Zbl 1304.90012
[26] Hanasusanto GA, Kuhn D (2018) Conic programming reformulations of two-stage distributionally robust linear programs over Wasserstein balls. Oper. Res. 66(3):849-869.Link, Google Scholar · Zbl 1455.90121
[27] Hanasusanto GA, Kuhn D, Wallace SW, Zymler S (2015) Distributionally robust multi-item newsvendor problems with multimodal demand distributions. Math. Programming 152(1):1-32.Crossref, Google Scholar · Zbl 1327.90153
[28] He S, Zhang J, Zhang S (2010) Bounding probability of small deviation: A fourth moment approach. Math. Oper. Res. 35(1):208-232.Link, Google Scholar · Zbl 1217.60015
[29] Hillestad R, Jacobsen S (1980) Reverse convex programming. Appl. Math. Optim. 6(1):63-78.Crossref, Google Scholar · Zbl 0448.90044
[30] Horst R, Thoai N (1999) DC programming: Overview. J. Optim. Theory Appl. 103(1):1-43.Crossref, Google Scholar · Zbl 1073.90537
[31] Jiang R, Wang J, Guan Y (2012) Robust unit commitment with wind power and pumped storage hydro. IEEE Trans. Power Systems 27(2):800-810.Crossref, Google Scholar
[32] Johnson O, Goldschmidt C (2006) Preservation of log-concavity on summation. ESAIM Probab. Statist. 10:206-215.Crossref, Google Scholar · Zbl 1185.60016
[33] Johnson O, Kontoyiannis I, Madiman M (2013) Log-concavity, ultra-log-concavity, and a maximum entropy property of discrete compound Poisson measures. Discrete Appl. Math. 161(9):1232-1250.Crossref, Google Scholar · Zbl 1282.60016
[34] Laffont JJ, Tirole J (1988) The dynamics of incentive contracts. Econometrica 56(5):1153-1175.Crossref, Google Scholar · Zbl 0663.90014
[35] Lam H, Mottet C (2017) Tail analysis without parametric models: A worst-case perspective. Oper. Res. 65(6):1696-1711.Link, Google Scholar · Zbl 1405.62145
[36] Lariviere M (2006) A note on probability distributions with increasing generalized failure rates. Oper. Res. 54(3):602-604.Link, Google Scholar · Zbl 1167.60309
[37] Lewis TR, Sappington DEM (1988) Regulating a monopolist with unknown demand. Amer. Econom. Rev. 78(5):986-998.Google Scholar
[38] Li B, Jiang R, Mathieu JL (2017) Ambiguous risk constraints with moment and unimodality information. Math. Programming 173.(1-2):151-192.Google Scholar · Zbl 1410.90139
[39] Long DZ, Qi J (2014) Distributionally robust discrete optimization with entropic value-at-risk. Oper. Res. Lett. 42(8):532-538.Crossref, Google Scholar · Zbl 1408.90218
[40] Matthews S (1987) Comparing auctions for risk averse buyers: A buyer’s point of view. Econometrica 55(3):633-646.Crossref, Google Scholar · Zbl 0612.90018
[41] Meyer R (1970) The validity of a family of optimization methods. SIAM J. Control 8(1):41-54.Crossref, Google Scholar · Zbl 0194.20501
[42] Myerson RB, Satterthwaite MA (1983) Efficient mechanisms for bilateral trading. J. Econom. Theory 29(2):265-281.Crossref, Google Scholar · Zbl 0523.90099
[43] Natarajan K, Sim M, Uichanco J (2017) Asymmetry and ambiguity in newsvendor models. Management Sci. 64(7):3146-3167.Link, Google Scholar
[44] Natarajan K, Teo CP, Zheng Z (2011) Mixed 0-1 linear programs under objective uncertainty: A completely positive representation. Oper. Res. 59(3):713-728.Link, Google Scholar · Zbl 1231.90304
[45] Ninh A, Hu H, Allen D (2019) Robust newsvendor problems: Effect of discrete demands. Ann. Oper. Res. 275(2):607-621.Crossref, Google Scholar · Zbl 1423.90013
[46] Peña J, Vera J, Zuluaga L (2015) Completely positive reformulations for polynomial optimization. Math. Programming 151(2):405-431.Crossref, Google Scholar · Zbl 1328.90114
[47] Perakis G, Roels G (2008) Regret in the newsvendor model with partial information. Oper. Res. 56(1):188-203.Link, Google Scholar · Zbl 1167.90350
[48] 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
[49] Prékopa A (1990) Sharp bounds on probabilities using linear programming. Oper. Res. 38(2):227-239.Link, Google Scholar · Zbl 0727.90049
[50] Prékopa A (2013) Stochastic Programming, vol. 324 (Springer Science & Business Media, Berlin, Heidelberg).Google Scholar
[51] Prékopa A, Boros E (1991) On the existence of a feasible flow in a stochastic transportation network. Oper. Res. 39(1):119-129.Link, Google Scholar · Zbl 0747.90041
[52] Prékopa A, Long J, Szantai T (2004) New bounds and approximations for the probability distribution of the length of the critical path. Dynamic Stochastic Optimization (Springer Verlag, Berlin, Heidelberg), 293-320.Crossref, Google Scholar · Zbl 1190.90255
[53] Prékopa A, Ninh A, Alexe G (2016) On the relationship between the discrete and continuous bounding moment problems and their numerical solutions. Ann. Oper. Res. 238(1-2):521-575.Crossref, Google Scholar · Zbl 1334.90184
[54] Rujeerapaiboon N, Kuhn D, Wiesemann W (2018) Chebyshev inequalities for products of random variables. Math. Oper. Res. 43(3):887-918.Link, Google Scholar · Zbl 1433.60011
[55] Saghafian S, Tomlin B (2016) The newsvendor under demand ambiguity: Combining data with moment and tail information. Oper. Res. 64(1):167-185.Link, Google Scholar · Zbl 1336.90053
[56] Saumard A, Wellner JA (2014) Log-concavity and strong log-concavity: A review. Statist. Surveys 8:45-114.Crossref, Google Scholar · Zbl 1360.62055
[57] Scarf H, Arrow K, Karlin S (1958) A min-max solution of an inventory problem. Studies in the Mathematical Theory of Inventory and Production (RAND Corporation, Santa Monica, CA), 201-209.Google Scholar
[58] Subasi E, Subasi M, Prékopa A (2009) Discrete moment problems with distributions known to be unimodal. Math. Inequalities Appl. 12(3):587-610.Crossref, Google Scholar · Zbl 1168.60321
[59] Sudheesh K, Anisha P, Deemat C (2015) A simple approach for testing constant failure rate against different ageing classes for discrete data. Statist. Methodology 25:74-88.Crossref, Google Scholar · Zbl 07035730
[60] Swaminathan JM, Shanthikumar JG (1999) Supplier diversification: Effect of discrete demand. Oper. Res. Lett. 24(5):213-221.Crossref, Google Scholar · Zbl 0967.90006
[61] Tian R, Cox SH, Zuluaga LF (2017) Moment problem and its applications to risk assessment. North Amer. Actuarial J. 21(2):242-266.Crossref, Google Scholar · Zbl 1414.91236
[62] Walther G (2000) Inference and modeling with log-concave distributions. Statist. Sci. 24(3):319-327.Crossref, Google Scholar · Zbl 1329.62192
[63] Wellner JA (2013) Strong log-concavity is preserved by convolution. High Dimensional Probability, vol. 6 (Springer Verlag, Berlin, Heidelberg), 95-102.Crossref, Google Scholar · Zbl 1271.60034
[64] Xu G, Burer S (2018) A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides. Comput. Optim. Appl. 70(1):33-59.Crossref, Google Scholar · Zbl 1417.90150
[65] Ziya S, Ayhan H, Foley RD (2004) Relationships among three assumptions in revenue management. Oper. Res. 52(5):804-809.Link, Google Scholar · Zbl 1165.90445
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.