Generalized Gauss inequalities via semidefinite programming. (English) Zbl 1351.90125
The authors consider the problem of the estimating bounds for the probability of a random vector to fall outside a polytope. A special assumption made by the authors is the unimodality of the density of the distribution of random vectors. It is shown, by using the concepts from Choquet theory, that both the Chebyshev and Gauss bounds can be obtained via semidefinite programming.
Reviewer: Antanas Žilinskas (Vilnius)
References:
| [1] | 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 · doi:10.1287/opre.50.2.358.424 |
| [2] | Bertsimas, D., Popescu, I.: Optimal inequalities in probability theory: a convex optimization approach. SIAM J. Optim. 15(3), 780-804 (2005) · Zbl 1077.60020 · doi:10.1137/S1052623401399903 |
| [3] | Bienaymé, I.J.: Considérations à l’appui de la découverte de Laplace sur la loi de probabilité dans la méthode des moindres carrés. Comptes Rendus de l’Académie des Sciences 37, 159-184 (1853) |
| [4] | Billingsley, P.: Convergence of probability measures. In: Barnett, V., Cressie, N.A., Fisher, N.I., Johnstone, I.M., Kadane, J.B., Kendall, D.G., Scott, D.W., Silverman, B.W., Smith, A.F.M., Teugels, J.L., Bradley, R.A., Hunter, J.S. (eds.) Wiley Series in Probability and Statistics, vol. 493. Wiley, New York (2009) |
| [5] | Birnbaum, Z., Raymond, J., Zuckerman, H.: A generalization of Tshebyshev’s inequality to two dimensions. Ann. Math. Stat. 18(1), 70-79 (1947) · Zbl 0032.03402 · doi:10.1214/aoms/1177730493 |
| [6] | Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049 · doi:10.1017/CBO9780511804441 |
| [7] | Chebyshev, P.: Des valeurs moyennes. Journal de Mathématiques Pures et Appliquées 12(2), 177-184 (1867) |
| [8] | Cheng, J., Delage, E., Lisser, A.: Distributionally Robust Stochastic Knapsack Problem. Technical report, HEC Montréal (2013) · Zbl 1336.90071 |
| [9] | 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 · doi:10.1287/opre.1090.0741 |
| [10] | Dharmadhikari, S., Joag-Dev, K.: Unimodality, Convexity, and Applications, Probability and Mathematical Statistics, vol. 27. Academic Press, London (1988) · Zbl 0646.62008 |
| [11] | Gauss, C.: Theoria combinationis observationum erroribus minimis obnoxiae, pars prior. Commentationes Societatis Regiae Scientiarum Gottingensis Recentiores 33, 321-327 (1821) |
| [12] | Gnedenko, B., Kolmogorov, A., Chung, K., Doob, J.: Limit distributions for sums of independent random variables. In: Addison-Wesley Series in Statistics, vol. 233. Addison-Wesley, Cambridge (1968) |
| [13] | Grundy, B.: Option prices and the underlying asset’s return distribution. J. Financ. 46(3), 1045-1069 (1991) · doi:10.1111/j.1540-6261.1991.tb03776.x |
| [14] | Hadamard, J.: Sur les problèmes aux dérivées partielles et leur signification physique. Princet. Univ. Bull. 13, 49-52 (1902) |
| [15] | Isii, K.: On sharpness of Tchebycheff-type inequalities. Ann. Inst. Stat. Math. 14(1), 185-197 (1962) · Zbl 0245.60014 · doi:10.1007/BF02868641 |
| [16] | Lanckriet, G., El Ghaoui, L., Bhattacharyya, C., Jordan, M.: A robust minimax approach to classification. J. Mach. Learn. Res. 3, 555-582 (2003) · Zbl 1084.68657 |
| [17] | Lasserre, J.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796-817 (2001) · Zbl 1010.90061 · doi:10.1137/S1052623400366802 |
| [18] | Lo, A.: Semi-parametric upper bounds for option prices and expected payoffs. J. Financ. Econ. 19(2), 373-387 (1987) · doi:10.1016/0304-405X(87)90010-9 |
| [19] | Löfberg, J.: Yalmip: A toolbox for modeling and optimization in matlab. In: Proceedings of the CACSD Conference, pp. 284-289 (2004) · Zbl 1040.90030 |
| [20] | Markov, A.: On Certain Applications of Algebraic Continued Fractions. Ph.D. thesis, St. Petersburg (1884) · Zbl 1138.91485 |
| [21] | Meaux, L., Seaman Jr, J., Boullion, T.: Calculation of multivariate Chebyshev-type inequalities. Comput. Math. Appl. 20(12), 55-60 (1990) · Zbl 0713.60023 · doi:10.1016/0898-1221(90)90164-F |
| [22] | Natarajan, K., Song, M., Teo, C.P.: Persistency model and its applications in choice modeling. Manag. Sci. 55(3), 453-469 (2009) · Zbl 1232.91139 · doi:10.1287/mnsc.1080.0951 |
| [23] | Nesterov, Y., Nemirovskii, A.: Interior-point polynomial algorithms in convex programming. In: Studies in Applied and Numerical Mathematics, vol. 13. SIAM, Philadelphia (1994) · Zbl 0824.90112 |
| [24] | Olshen, R., Savage, L.: A Generalized Unimodality. Technical report 143, Stanford University (1969) · Zbl 0193.45102 |
| [25] | Phelps, R. (ed.): Lectures on Choquet’s Theorem.In: Lecture Notes in Mathematics, vol. 1757. Springer, Berlin (2001) · Zbl 0997.46005 |
| [26] | Pólik, I., Terlaky, T.: A survey of the S-lemma. SIAM Rev. 49(3), 371-418 (2007) · Zbl 1128.90046 · doi:10.1137/S003614450444614X |
| [27] | 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 · doi:10.1287/moor.1040.0137 |
| [28] | Rockafellar, R., Wets, R.B.: Variational Analysis, Grundlehren der mathematischen Wissenschaften, vol. 317. Springer, Berlin (1998) · Zbl 0888.49001 |
| [29] | Rogosinski, W.: Moments of non-negative mass. Proc. R. Soc. Lond. Ser. A Math. Phys. Sci. 245(1240), 1-27 (1958) · Zbl 0082.32404 · doi:10.1098/rspa.1958.0062 |
| [30] | Sellke, T.: Generalized Gauss-Chebyshev inequalities for unimodal distributions. Metrika 43(1), 107-121 (1996) · Zbl 0854.60018 · doi:10.1007/BF02613901 |
| [31] | Shapiro, A.: On duality theory of conic linear problems. Nonconvex Optim. Appl. 57, 135-155 (2001) · Zbl 1055.90088 · doi:10.1007/978-1-4757-3403-4_7 |
| [32] | Shapiro, A., Kleywegt, A.: Minimax analysis of stochastic problems. Optim. Methods Softw. 17(3), 523-542 (2002) · Zbl 1040.90030 · doi:10.1080/1055678021000034008 |
| [33] | Smith, J.: Generalized Chebychev inequalities: theory and applications in decision analysis. Oper. Res. 43(5), 807-825 (1995) · Zbl 0842.90002 · doi:10.1287/opre.43.5.807 |
| [34] | Stellato, B.: Data-Driven Chance Constrained Optimization (2014). doi:10.3929/ethz-a-010266857 |
| [35] | Tütüncü, R., Toh, K., Todd, M.: Solving semidefinite-quadratic-linear programs using SDPT3. Math. Progr. 95(2), 189-217 (2003) · Zbl 1030.90082 · doi:10.1007/s10107-002-0347-5 |
| [36] | Van Parys, B., Kuhn, D., Goulart, P., Morari, M.: Distributionally Robust Control of Constrained Stochastic Systems. Technical report, ETH Zürich (2013) · Zbl 1359.93542 |
| [37] | Vandenberghe, L., Boyd, S., Comanor, K.: Generalized Chebyshev bounds via semidefinite programming. SIAM Rev. 49(1), 52-64 (2007) · Zbl 1151.90512 · doi:10.1137/S0036144504440543 |
| [38] | Vorobyov, S., Chen, H., Gershman, A.: On the relationship between robust minimum variance beamformers with probabilistic and worst-case distortionless response constraints. IEEE Trans. Signal Process. 56(11), 5719-5724 (2008) · Zbl 1390.94458 · doi:10.1109/TSP.2008.929866 |
| [39] | Xu, H., Caramanis, C., Mannor, S.: Optimization under probabilistic envelope constraints. Oper. Res. 60(3), 682-699 (2012) · Zbl 1251.90301 · doi:10.1287/opre.1120.1054 |
| [40] | Yamada, Y., Primbs, J.: Value-at-risk estimation for dynamic hedging. Int. J. Theor. Appl. Financ. 5(4), 333-354 (2002) · Zbl 1138.91485 · doi:10.1142/S0219024902001468 |
| [41] | Ye, Y.: Interior point algorithms: theory and analysis. In: Graham, R.L., Lenstra, J.K. (eds.) Wiley Series in Discrete Mathematics and Optimization, vol. 44. Wiley, New York (2011) |
| [42] | Yu, Y.L., Li, Y., Schuurmans, D., Szepesvári, C.: A general projection property for distribution families. In: Bengio, Y., Schuurmans, D., Lafferty, J.D., Williams, C.K.I., Culotta, A. (eds.) Advances in Neural Information Processing Systems. Wiley, New York, pp. 2232-2240 (2009) |
| [43] | Zymler, S., Kuhn, D., Rustem, B.: Distributionally robust joint chance constraints with second-order moment information. Math. Progr. 137(1-2), 167-198 (2013) · Zbl 1286.90103 · doi:10.1007/s10107-011-0494-7 |
| [44] | Zymler, S., Kuhn, D., Rustem, B.: Worst-case value-at-risk of non-linear portfolios. Manag. Sci. 59(1), 172-188 (2013) · doi:10.1287/mnsc.1120.1615 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
