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-122. 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-187.  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-149.  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-858. 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-88.  Google Scholar

[7]

R. Henrion, Qualitative stability of convex programs with probabilistic constraints, Lecture Notes in Econom. and Math. Systems, 481 (2000), 164-180.  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-274.  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-611. doi: 10.1007/s10107-004-0507-x.  Google Scholar

[10]

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

[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.  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-361. 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-914. doi: 10.1137/S1052623403431639.  Google Scholar

[14]

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

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

[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.  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 "Numerical Techniques for Stochastic Optimization" (eds. Y. Ermoliev and R. J.-B. Wets), Springer-Verlag, (1988), 229-235.  Google Scholar

[19]

T. Szántai, Evaluation of a special multivariate gamma distribution, Math. Program. Study, 27 (1986), 1-16. 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-101. doi: 10.1023/A:1019211000153.  Google Scholar

[21]

S. Uryasev, Derivatives of probability functions and some applications, Ann. Oper. Res., 56 (1995), 287-311. 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-122. 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-187.  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-149.  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-858. 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-88.  Google Scholar

[7]

R. Henrion, Qualitative stability of convex programs with probabilistic constraints, Lecture Notes in Econom. and Math. Systems, 481 (2000), 164-180.  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-274.  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-611. doi: 10.1007/s10107-004-0507-x.  Google Scholar

[10]

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

[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.  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-361. 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-914. doi: 10.1137/S1052623403431639.  Google Scholar

[14]

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

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

[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.  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 "Numerical Techniques for Stochastic Optimization" (eds. Y. Ermoliev and R. J.-B. Wets), Springer-Verlag, (1988), 229-235.  Google Scholar

[19]

T. Szántai, Evaluation of a special multivariate gamma distribution, Math. Program. Study, 27 (1986), 1-16. 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-101. doi: 10.1023/A:1019211000153.  Google Scholar

[21]

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

[1]

X. X. Huang, D. Li, Xiaoqi Yang. Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287
[2]

Victor Berdichevsky. Distribution of minimum values of stochastic functionals. Networks & Heterogeneous Media, 2008, 3 (3) : 437-460. doi: 10.3934/nhm.2008.3.437
[3]

Jingzhen Liu, Ka-Fai Cedric Yiu. Optimal stochastic differential games with VaR constraints. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1889-1907. doi: 10.3934/dcdsb.2013.18.1889
[4]

Xiantao Xiao, Jian Gu, Liwei Zhang, Shaowu Zhang. A sequential convex program method to DC program with joint chance constraints. Journal of Industrial & Management Optimization, 2012, 8 (3) : 733-747. doi: 10.3934/jimo.2012.8.733
[5]

Anurag Jayswala, Tadeusz Antczakb, Shalini Jha. Second order modified objective function method for twice differentiable vector optimization problems over cone constraints. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 133-145. doi: 10.3934/naco.2019010
[6]

Saeid Ansary Karbasy, Maziar Salahi. Quadratic optimization with two ball constraints. Numerical Algebra, Control & Optimization, 2020, 10 (2) : 165-175. doi: 10.3934/naco.2019046
[7]

K. T. Arasu, Manil T. Mohan. Optimization problems with orthogonal matrix constraints. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 413-440. doi: 10.3934/naco.2018026
[8]

Piermarco Cannarsa, Hélène Frankowska, Elsa M. Marchini. On Bolza optimal control problems with constraints. Discrete & Continuous Dynamical Systems - B, 2009, 11 (3) : 629-653. doi: 10.3934/dcdsb.2009.11.629
[9]

Meng Xue, Yun Shi, Hailin Sun. Portfolio optimization with relaxation of stochastic second order dominance constraints via conditional value at risk. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2581-2602. doi: 10.3934/jimo.2019071
[10]

Yanmei Sun, Yakui Huang. An alternate gradient method for optimization problems with orthogonality constraints. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021003
[11]

Arezu Zare, Mohammad Keyanpour, Maziar Salahi. On fractional quadratic optimization problem with two quadratic constraints. Numerical Algebra, Control & Optimization, 2020, 10 (3) : 301-315. doi: 10.3934/naco.2020003
[12]

Canghua Jiang, Zhiqiang Guo, Xin Li, Hai Wang, Ming Yu. An efficient adjoint computational method based on lifted IRK integrator and exact penalty function for optimal control problems involving continuous inequality constraints. Discrete & Continuous Dynamical Systems - S, 2020, 13 (6) : 1845-1865. doi: 10.3934/dcdss.2020109
[13]

Changjun Yu, Shuxuan Su, Yanqin Bai. On the optimal control problems with characteristic time control constraints. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021021
[14]

IvÁn Area, FaÏÇal NdaÏrou, Juan J. Nieto, Cristiana J. Silva, Delfim F. M. Torres. Ebola model and optimal control with vaccination constraints. Journal of Industrial & Management Optimization, 2018, 14 (2) : 427-446. doi: 10.3934/jimo.2017054
[15]

M. Delgado Pineda, E. A. Galperin, P. Jiménez Guerra. MAPLE code of the cubic algorithm for multiobjective optimization with box constraints. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407
[16]

X. X. Huang, Xiaoqi Yang, K. L. Teo. A smoothing scheme for optimization problems with Max-Min constraints. Journal of Industrial & Management Optimization, 2007, 3 (2) : 209-222. doi: 10.3934/jimo.2007.3.209
[17]

Chunyang Zhang, Shugong Zhang, Qinghuai Liu. Homotopy method for a class of multiobjective optimization problems with equilibrium constraints. Journal of Industrial & Management Optimization, 2017, 13 (1) : 81-92. doi: 10.3934/jimo.2016005
[18]

Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19
[19]

Stéphane Chrétien, Sébastien Darses, Christophe Guyeux, Paul Clarkson. On the pinning controllability of complex networks using perturbation theory of extreme singular values. application to synchronisation in power grids. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 289-299. doi: 10.3934/naco.2017019
[20]

Gui-Hua Lin, Masao Fukushima. A class of stochastic mathematical programs with complementarity constraints: reformulations and algorithms. Journal of Industrial & Management Optimization, 2005, 1 (1) : 99-122. doi: 10.3934/jimo.2005.1.99

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences