American Institute of Mathematical Sciences

Advanced
2012, 2(4): 655-668. doi: 10.3934/naco.2012.2.655

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

René Henrion 1,

1. 

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

Received  January 2012 Revised  September 2012 Published  November 2012

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: Gaussian distribution function, sensitivity of optimal values., stochastic optimization, Probabilistic constraints, chance constraints.
Mathematics Subject Classification: 90C15; 90C3.
Citation: René Henrion. Gradient estimates for Gaussian distribution functions: application to probabilistically constrained optimization problems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 655-668. doi: 10.3934/naco.2012.2.655
References:
[1]

I. Deák, Subroutines for computing normal probabilities of sets - computer experiences,, Ann. Oper. Res., 100 (2000), 103.  doi: 10.1023/A:1019215116991.  Google Scholar

[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.   Google Scholar

[3]

M. Fabian, R. Henrion, A. Kruger and J. Outrata, Error bounds: necessary and sufficient conditions,, Set-Valued Var. Anal., 18 (2010), 121.   Google Scholar

[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.  doi: 10.1016/j.ejor.2008.09.026.  Google Scholar

[5]

A. Genz and F. Bretz, "Computation of Multivariate Mormal and Probabilities,", Lecture Notes in Statist., 195 (2009).   Google Scholar

[6]

R. Henrion and W. Römisch, Metric regularity and quantitative stability in stochastic programs with probabilistic constraints,, Math. Program., 84 (1999), 55.   Google Scholar

[7]

R. Henrion, Qualitative stability of convex programs with probabilistic constraints,, Lecture Notes in Econom. and Math. Systems, 481 (2000), 164.   Google Scholar

[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.   Google Scholar

[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.  doi: 10.1007/s10107-004-0507-x.  Google Scholar

[10]

A. D. Ioffe, Metric regularity and subdifferential calculus,, Russian Math. Surveys, 55 (2000), 501.  doi: 10.1070/RM2000v055n03ABEH000292.  Google Scholar

[11]

K. Marti, Differentiation of probability functions: the transformation method,, Comput. Math. Appl., 30 (1995), 361.  doi: 10.1016/0898-1221(95)00113-1.  Google Scholar

[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.  doi: 10.1080/00949650802641833.  Google Scholar

[13]

G. Pflug and H. Weisshaupt, Probability gradient estimation by set-valued calculus and applications in network design,, SIAM J. Optim., 15 (2005), 898.  doi: 10.1137/S1052623403431639.  Google Scholar

[14]

A. Prékopa, "Stochastic Programming,", Kluwer, (1995).   Google Scholar

[15]

A. Prékopa, Probabilistic programming,, in, 10 (2003), 267.   Google Scholar

[16]

W. Römisch, Stability of stochastic programming problems,, in, 10 (2003), 483.   Google Scholar

[17]

A. Shapiro, D. Dentcheva and A. Ruszczyński, "Lectures on Stochastic Programming,", MPS/SIAM Ser. Optim., 9 (2009).   Google Scholar

[18]

T. Szántai, A computer code for solution of probabilistic constrained stochastic programming problems,, in, (1988), 229.   Google Scholar

[19]

T. Szántai, Evaluation of a special multivariate gamma distribution,, Math. Program. Study, 27 (1986), 1.  doi: 10.1007/BFb0121111.  Google Scholar

[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.  doi: 10.1023/A:1019211000153.  Google Scholar

[21]

S. Uryasev, Derivatives of probability functions and some applications,, Ann. Oper. Res., 56 (1995), 287.  doi: 10.1007/BF02031712.  Google Scholar

show all references

References:
[1]

I. Deák, Subroutines for computing normal probabilities of sets - computer experiences,, Ann. Oper. Res., 100 (2000), 103.  doi: 10.1023/A:1019215116991.  Google Scholar

[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.   Google Scholar

[3]

M. Fabian, R. Henrion, A. Kruger and J. Outrata, Error bounds: necessary and sufficient conditions,, Set-Valued Var. Anal., 18 (2010), 121.   Google Scholar

[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.  doi: 10.1016/j.ejor.2008.09.026.  Google Scholar

[5]

A. Genz and F. Bretz, "Computation of Multivariate Mormal and Probabilities,", Lecture Notes in Statist., 195 (2009).   Google Scholar

[6]

R. Henrion and W. Römisch, Metric regularity and quantitative stability in stochastic programs with probabilistic constraints,, Math. Program., 84 (1999), 55.   Google Scholar

[7]

R. Henrion, Qualitative stability of convex programs with probabilistic constraints,, Lecture Notes in Econom. and Math. Systems, 481 (2000), 164.   Google Scholar

[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.   Google Scholar

[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.  doi: 10.1007/s10107-004-0507-x.  Google Scholar

[10]

A. D. Ioffe, Metric regularity and subdifferential calculus,, Russian Math. Surveys, 55 (2000), 501.  doi: 10.1070/RM2000v055n03ABEH000292.  Google Scholar

[11]

K. Marti, Differentiation of probability functions: the transformation method,, Comput. Math. Appl., 30 (1995), 361.  doi: 10.1016/0898-1221(95)00113-1.  Google Scholar

[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.  doi: 10.1080/00949650802641833.  Google Scholar

[13]

G. Pflug and H. Weisshaupt, Probability gradient estimation by set-valued calculus and applications in network design,, SIAM J. Optim., 15 (2005), 898.  doi: 10.1137/S1052623403431639.  Google Scholar

[14]

A. Prékopa, "Stochastic Programming,", Kluwer, (1995).   Google Scholar

[15]

A. Prékopa, Probabilistic programming,, in, 10 (2003), 267.   Google Scholar

[16]

W. Römisch, Stability of stochastic programming problems,, in, 10 (2003), 483.   Google Scholar

[17]

A. Shapiro, D. Dentcheva and A. Ruszczyński, "Lectures on Stochastic Programming,", MPS/SIAM Ser. Optim., 9 (2009).   Google Scholar

[18]

T. Szántai, A computer code for solution of probabilistic constrained stochastic programming problems,, in, (1988), 229.   Google Scholar

[19]

T. Szántai, Evaluation of a special multivariate gamma distribution,, Math. Program. Study, 27 (1986), 1.  doi: 10.1007/BFb0121111.  Google Scholar

[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.  doi: 10.1023/A:1019211000153.  Google Scholar

[21]

S. Uryasev, Derivatives of probability functions and some applications,, Ann. Oper. Res., 56 (1995), 287.  doi: 10.1007/BF02031712.  Google Scholar

[1]

Junkee Jeon. Finite horizon portfolio selection problems with stochastic borrowing constraints. Journal of Industrial & Management Optimization, 2021, 17 (2) : 733-763. doi: 10.3934/jimo.2019132
[2]

Nan Zhang, Linyi Qian, Zhuo Jin, Wei Wang. Optimal stop-loss reinsurance with joint utility constraints. Journal of Industrial & Management Optimization, 2021, 17 (2) : 841-868. doi: 10.3934/jimo.2020001
[3]

Stefan Doboszczak, Manil T. Mohan, Sivaguru S. Sritharan. Pontryagin maximum principle for the optimal control of linearized compressible navier-stokes equations with state constraints. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020110
[4]

Xuemei Chen, Julia Dobrosotskaya. Inpainting via sparse recovery with directional constraints. Mathematical Foundations of Computing, 2020, 3 (4) : 229-247. doi: 10.3934/mfc.2020025
[5]

Manuel de León, Víctor M. Jiménez, Manuel Lainz. Contact Hamiltonian and Lagrangian systems with nonholonomic constraints. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2021001
[6]

Yuan Tan, Qingyuan Cao, Lan Li, Tianshi Hu, Min Su. A chance-constrained stochastic model predictive control problem with disturbance feedback. Journal of Industrial & Management Optimization, 2021, 17 (1) : 67-79. doi: 10.3934/jimo.2019099
[7]

Fengwei Li, Qin Yue, Xiaoming Sun. The values of two classes of Gaussian periods in index 2 case and weight distributions of linear codes. Advances in Mathematics of Communications, 2021, 15 (1) : 131-153. doi: 10.3934/amc.2020049
[8]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117
[9]

Xin Zhao, Tao Feng, Liang Wang, Zhipeng Qiu. Threshold dynamics and sensitivity analysis of a stochastic semi-Markov switched SIRS epidemic model with nonlinear incidence and vaccination. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021010
[10]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017
[11]

Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100
[12]

Giulia Cavagnari, Antonio Marigonda. Attainability property for a probabilistic target in wasserstein spaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 777-812. doi: 10.3934/dcds.2020300
[13]

Jingrui Sun, Hanxiao Wang. Mean-field stochastic linear-quadratic optimal control problems: Weak closed-loop solvability. Mathematical Control & Related Fields, 2021, 11 (1) : 47-71. doi: 10.3934/mcrf.2020026
[14]

Kalikinkar Mandal, Guang Gong. On ideal $ t $-tuple distribution of orthogonal functions in filtering de bruijn generators. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020125
[15]

Hui Zhao, Zhengrong Liu, Yiren Chen. Global dynamics of a chemotaxis model with signal-dependent diffusion and sensitivity. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021011
[16]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296
[17]

Jie Zhang, Yuping Duan, Yue Lu, Michael K. Ng, Huibin Chang. Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020071
[18]

Huyuan Chen, Dong Ye, Feng Zhou. On gaussian curvature equation in $ \mathbb{R}^2 $ with prescribed nonpositive curvature. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3201-3214. doi: 10.3934/dcds.2020125
[19]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443
[20]

Raimund Bürger, Christophe Chalons, Rafael Ordoñez, Luis Miguel Villada. A multiclass Lighthill-Whitham-Richards traffic model with a discontinuous velocity function. Networks & Heterogeneous Media, 2021  doi: 10.3934/nhm.2021004

 Impact Factor: 

Tools

Metrics

  • PDF downloads (53)
  • HTML views (0)
  • Cited by (7)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences