Gradient estimates for Gaussian distribution functions: application to probabilistically constrained optimization problems

René Henrion

doi:10.3934/naco.2012.2.655

Article Contents

2012, Volume 2, Issue 4: 655-668. Doi: 10.3934/naco.2012.2.655

This issue Previous Article Preface Next Article The integrated size and price optimization problem

Gradient estimates for Gaussian distribution functions: application to probabilistically constrained optimization problems

René Henrion^1,

1.
Weierstrass Institute Berlin, Mohrenstr. 39, 10117 Berlin

Received: January 2012

Revised: September 2012

Published: November 2012

Abstract / Introduction Related Papers Cited by

Abstract

We provide lower estimates for the norm of gradients of Gaussian distribution functions and apply the results obtained to a special class of probabilistically constrained optimization problems. In particular, it is shown how the precision of computing gradients in such problems can be controlled by the precision of function values for Gaussian distribution functions. Moreover, a sensitivity result for optimal values with respect to perturbations of the underlying random vector is derived. It is shown that the so-called maximal increasing slope of the optimal value with respect to the Kolmogorov distance between original and perturbed distribution can be estimated explicitly from the input data of the problem.

Keywords:

Mathematics Subject Classification: 90C15; 90C31.

Citation:

Related Papers

Cited by

References

[1]	I. Deák, Subroutines for computing normal probabilities of sets - computer experiences, Ann. Oper. Res., 100 (2000), 103-122.doi: 10.1023/A:1019215116991.
[2]	E. De Giorgi, A. Marino and M. Tosques, Problems of evolution in metric spaces and maximal decreasing curve, Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis .Mat. Natur. (8), 68 (1980), 180-187.
[3]	M. Fabian, R. Henrion, A. Kruger and J. Outrata, Error bounds: necessary and sufficient conditions, Set-Valued Var. Anal., 18 (2010), 121-149.
[4]	J. Garnier, A. Omrane and Y. Rouchdy, Asymptotic formulas for the derivatives of probability functions and their monte carlo estimations, European J. Oper. Res., 198 (2009), 848-858.doi: 10.1016/j.ejor.2008.09.026.
[5]	A. Genz and F. Bretz, "Computation of Multivariate Mormal and Probabilities," Lecture Notes in Statist., 195 (2009).
[6]	R. Henrion and W. Römisch, Metric regularity and quantitative stability in stochastic programs with probabilistic constraints, Math. Program., 84 (1999), 55-88.
[7]	R. Henrion, Qualitative stability of convex programs with probabilistic constraints, Lecture Notes in Econom. and Math. Systems, 481 (2000), 164-180.
[8]	R. Henrion, Perturbation analysis of chance-constrained programs under variation of all constraint data, Lecture Notes in Econom. and Math. Systems, 532 (2004), 257-274.
[9]	R. Henrion and W. Römisch, Hölder and Lipschitz Stability of solution sets in programs with probabilistic constraints, Math. Program., 100 (2004), 589-611.doi: 10.1007/s10107-004-0507-x.
[10]	A. D. Ioffe, Metric regularity and subdifferential calculus, Russian Math. Surveys, 55 (2000), 501-558.doi: 10.1070/RM2000v055n03ABEH000292.
[11]	K. Marti, Differentiation of probability functions: the transformation method, Comput. Math. Appl., 30 (1995), 361-382.doi: 10.1016/0898-1221(95)00113-1.
[12]	N. Olieman and B. van Putten, Estimation method of multivariate exponential probabilities based on a simplex coordinates transform, J. Stat. Comput. Simul., 80 (2010), 355-361.doi: 10.1080/00949650802641833.
[13]	G. Pflug and H. Weisshaupt, Probability gradient estimation by set-valued calculus and applications in network design, SIAM J. Optim., 15 (2005), 898-914.doi: 10.1137/S1052623403431639.
[14]	A. Prékopa, "Stochastic Programming," Kluwer, Dordrecht, 1995.
[15]	A. Prékopa, Probabilistic programming, in "Stochastic Programming" (eds. A. Ruszczyński and A. Shapiro), Handbooks in Operations Research and Management Science, Elsevier, 10 (2003), 267-351.
[16]	W. Römisch, Stability of stochastic programming problems, in "Stochastic Programming" (eds. A. Ruszczyński and A. Shapiro), Handbooks in Operations Research and Management Science, Elsevier, 10 (2003), 483-554.
[17]	A. Shapiro, D. Dentcheva and A. Ruszczyński, "Lectures on Stochastic Programming," MPS/SIAM Ser. Optim., 9 (2009).
[18]	T. Szántai, A computer code for solution of probabilistic constrained stochastic programming problems, in "Numerical Techniques for Stochastic Optimization" (eds. Y. Ermoliev and R. J.-B. Wets), Springer-Verlag, (1988), 229-235.
[19]	T. Szántai, Evaluation of a special multivariate gamma distribution, Math. Program. Study, 27 (1986), 1-16.doi: 10.1007/BFb0121111.
[20]	T. Szántai, Improved bounds and simulation procedures on the value of the multivariate normal probability distribution function, Ann. Oper. Res., 100 (2000), 85-101.doi: 10.1023/A:1019211000153.
[21]	S. Uryasev, Derivatives of probability functions and some applications, Ann. Oper. Res., 56 (1995), 287-311.doi: 10.1007/BF02031712.