Abstract
Joint probability function refers to the probability function that requires multiple conditions to satisfy simultaneously. It appears naturally in chance-constrained programs. In this paper, we derive closed-form expressions of the gradient and Hessian of joint probability functions and develop Monte Carlo estimators of them. We then design a Monte Carlo algorithm, based on these estimators, to solve chance-constrained programs. Our numerical study shows that the algorithm works well, especially only with the gradient estimators.
Similar content being viewed by others
Notes
There are technical conditions for interchanging the order of differentiations (see, for instance, Marsden and Hoffman [31]). The conditions are weak and typically satisfied by practical problems. To avoid too much technicality, we implicitly assume that the order can be interchanged throughout the paper.
References
Dentcheva, D., Lai, B., Ruszczyński, A.: Dual methods for probabilistic optimization problems. Math. Methods Oper. Res. 60(2), 331–346 (2004)
Prékopa, A., Rapcsák, T., Zsuffa, I.: Serially linked reservoir system design using stochastic programming. Water Resour. Res. 12(4), 672–678 (1978)
Charnes, A., Cooper, W.W., Symonds, G.H.: Cost horizons and certainty equivalents: an approach to stochastic programming of heating oil. Manag. Sci. 4(3), 235–263 (1958)
Miller, L.B., Wagner, H.: Chance-constrained programming with joint constraints. Oper. Res. 13(6), 930–945 (1965)
Prékopa, A.: Probabilistic programming. In: Ruszczynski, A., Shapiro, A. (eds.) Handbooks in Operations Research and Management Science, volume 10, chapter 5, pp. 267–351. Elsevier, Amsterdam (2003)
Lagoa, C.M., Li, X., Sznaier, M.: Probabilistically constrained linear programs and risk-adjusted controller design. SIAM J. Optim. 15(3), 938–951 (2005)
Ben-Tal, A., Nemirovski, A.: Robust solutions of linear programming problems contaminated with uncertain data. Math. Program. 88(3), 411–424 (2000)
Rockafellar, R.T., Uryasev, S.P.: Optimization of conditional value-at-risk. J. Risk 2(3), 21–41 (2000)
Nemirovski, A., Shapiro, A.: Convex approximations of chance constrained programs. SIAM J. Optim. 17(4), 969–996 (2006)
Prékopa, A.: Stochastic Programming. Springer, Netherlands (1995)
Chen, W., Sim, M., Sun, J., Teo, C.-P.: From CVaR to uncertainty set: implications in joint chance-constrained optimization. Oper. Res. 58(2), 470–485 (2010)
Uryasev, S.P.: A differentiation formula for integrals over sets given by inclusion. Numer. Funct. Anal. Optim. 10(7), 827–841 (1989)
Marti, K.: Stochastic Optimization Methods. Springer, Berlin (2005)
Calafiore, G., Campi, M.C.: Uncertain convex programs: randomized solutions and confidence levels. Math. Program. 102(1), 25–46 (2005)
Calafiore, G., Campi, M.C.: The scenario approach to robust control design. IEEE Trans. Automat. Control 51(5), 742–753 (2006)
Hong, L.J., Yang, Y., Zhang, L.: Sequential convex approximations to joint chance constrained programs: A Monte Carlo approach. Oper. Res. 59(3), 617–630 (2011)
Hong, L.J., Hu, Z., Zhang, L.: Conditional value-at-risk approximation to value-at-risk constrained programs: A remedy via Monte Carlo. INFORMS J. Comput. 26(2), 385–400 (2014)
Meng, F.W., Sun, J., Goh, M.: Stochastic optimization problems with CVaR risk measure and their sample average approximation. J. Optim. Theory Appl. 146(2), 399–418 (2010)
Sun, H., Xu, H., Wang, Y.: Asymptotic analysis of sample average approximation for stochastic optimization problems with joint chance constraints via conditional value at risk and difference of convex functions. J. Optim. Theory Appl. 161(1), 257–284 (2014)
Hu, Z., Hong, L.J., Zhang, L.: A smooth Monte Carlo approach to joint chance-constrained programs. IIE Trans. 45(7), 716–735 (2013)
Fu, M.C.: Gradient estimation. In: Henderson, S.G., Nelson, B.L. (eds.), Handbooks in Operations Research and Management Science, volume 13, chapter 19, pp. 575–616. Elsevier, Amsterdam, (2006)
Ho, Y.C., Cao, X.-R.: Perturbation analysis and optimization of queueing networks. J. Optim. Theory Appl. 40(4), 559–582 (1983)
Glasserman, P.: Gradient Estimation via Perturbation Analysis. Kluwer Academic Publishers, Norwell (1991)
Fu, M.C., Hu, J.Q.: Conditional Monte Carlo: Gradient Estimation and Optimization Applications. Kluwer Academic Publishers, Norwell (1997)
Reiman, M.I., Weiss, A.: Sensitivity analysis for simulations via likelihood ratios. Oper. Res. 37(5), 830–844 (1989)
Glynn, P.W.: Likelihood ratio gradient estimation for stochastic systems. Commun. ACM 33(10), 75–84 (1990)
Hong, L.J., Liu, G.: Pathwise estimation of probability sensitivities through terminating and steady-state simulations. Oper. Res. 58(2), 357–370 (2010)
Hong, L.J.: Estimating quantile sensitivities. Oper. Res. 57(1), 118–130 (2009)
Fu, M.C., Hong, L.J., Hu, J.Q.: Conditional Monte Carlo estimation of quantile sensitivities. Oper. Res. 55(12), 2019–2027 (2009)
Durrett, R.: Probability: Theory and Examples, 2nd edn. Duxury Press, Belmont (1995)
Marsden, J.E., Hoffman, M.J.: Elementary Classical Analysis, 2nd edn. W. H. Freeman and Co., New York (1993)
Bosq, D.: Nonparametric Statistics for Stochastic Processes: Estimation and Prediction. Springer, New York (1998)
Liu, G., Hong, L.J.: Kernel estimation of quantile sensitivities. Nav. Res. Log. 56, 511–525 (2009)
Parzen, E.: On estimation of a probability density function and mode. Ann. Math. Stat. 33(3), 1065–1076 (1962)
Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on Stochastic Programming: Modeling and Theory. SIAM, Philadelphia (2009)
Hong, L.J., Liu, G.: Simulating sensitivities of conditional value-at-risk. Manag. Sci. 55(2), 281–293 (2009)
Lam, H.: Recovering best statistical guarantees via the empirical divergence-based distributionally robust optimization. arXiv:1605.09349 (2016)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported by the Hong Kong Research Grants Council (No. GRF 613213).
Rights and permissions
About this article
Cite this article
Hong, L.J., Jiang, GX. Gradient and Hessian of Joint Probability Function with Applications on Chance-Constrained Programs. J. Oper. Res. Soc. China 5, 431–455 (2017). https://doi.org/10.1007/s40305-017-0154-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40305-017-0154-6