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

Previous Article
The integrated size and price optimization problem
NACO Home
This Issue
Next Article
Preface

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

Abstract
Related Papers

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 and 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.
[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.

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

[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 and Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287
[2]	Jingzhen Liu, Ka-Fai Cedric Yiu. Optimal stochastic differential games with VaR constraints. Discrete and Continuous Dynamical Systems - B, 2013, 18 (7) : 1889-1907. doi: 10.3934/dcdsb.2013.18.1889
[3]	Victor Berdichevsky. Distribution of minimum values of stochastic functionals. Networks and Heterogeneous Media, 2008, 3 (3) : 437-460. doi: 10.3934/nhm.2008.3.437
[4]	Xiantao Xiao, Jian Gu, Liwei Zhang, Shaowu Zhang. A sequential convex program method to DC program with joint chance constraints. Journal of Industrial and 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 and 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 and 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 and 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 and 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 and Management Optimization, 2020, 16 (6) : 2581-2602. doi: 10.3934/jimo.2019071
[10]	Arezu Zare, Mohammad Keyanpour, Maziar Salahi. On fractional quadratic optimization problem with two quadratic constraints. Numerical Algebra, Control and Optimization, 2020, 10 (3) : 301-315. doi: 10.3934/naco.2020003
[11]	Yanmei Sun, Yakui Huang. An alternate gradient method for optimization problems with orthogonality constraints. Numerical Algebra, Control and Optimization, 2021, 11 (4) : 665-676. doi: 10.3934/naco.2021003
[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 and Continuous Dynamical Systems - S, 2020, 13 (6) : 1845-1865. doi: 10.3934/dcdss.2020109
[13]	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 and Management Optimization, 2018, 14 (2) : 427-446. doi: 10.3934/jimo.2017054
[14]	Changjun Yu, Shuxuan Su, Yanqin Bai. On the optimal control problems with characteristic time control constraints. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1305-1320. doi: 10.3934/jimo.2021021
[15]	Yu Chen, Yonggang Li, Bei Sun, Chunhua Yang, Hongqiu Zhu. Multi-objective chance-constrained blending optimization of zinc smelter under stochastic uncertainty. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021169
[16]	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 and Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407
[17]	X. X. Huang, Xiaoqi Yang, K. L. Teo. A smoothing scheme for optimization problems with Max-Min constraints. Journal of Industrial and Management Optimization, 2007, 3 (2) : 209-222. doi: 10.3934/jimo.2007.3.209
[18]	Chunyang Zhang, Shugong Zhang, Qinghuai Liu. Homotopy method for a class of multiobjective optimization problems with equilibrium constraints. Journal of Industrial and Management Optimization, 2017, 13 (1) : 81-92. doi: 10.3934/jimo.2016005
[19]	Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19
[20]	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 and Optimization, 2017, 7 (3) : 289-299. doi: 10.3934/naco.2017019

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
René Henrion
on Google Scholar
René Henrion

[Back to Top]