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

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

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

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

[3]

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

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

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

[7]

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

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

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

[10]

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

[11]

K. Marti, Differentiation of probability functions: the transformation method,, Comput. Math. Appl., 30 (1995), 361. 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. 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. doi: 10.1137/S1052623403431639.

[14]

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

[15]

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

[16]

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

[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, (1988), 229.

[19]

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

[21]

S. Uryasev, Derivatives of probability functions and some applications,, Ann. Oper. Res., 56 (1995), 287. 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. 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.

[3]

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

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

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

[7]

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

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

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

[10]

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

[11]

K. Marti, Differentiation of probability functions: the transformation method,, Comput. Math. Appl., 30 (1995), 361. 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. 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. doi: 10.1137/S1052623403431639.

[14]

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

[15]

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

[16]

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

[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, (1988), 229.

[19]

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

[21]

S. Uryasev, Derivatives of probability functions and some applications,, Ann. Oper. Res., 56 (1995), 287. 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 & 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 & 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 & 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 & Management Optimization, 2012, 8 (3) : 733-747. doi: 10.3934/jimo.2012.8.733

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

Yongchao Liu, Hailin Sun, Huifu Xu. An approximation scheme for stochastic programs with second order dominance constraints. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 473-490. doi: 10.3934/naco.2016021

[14]

Yongchao Liu. Quantitative stability analysis of stochastic mathematical programs with vertical complementarity constraints. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 451-460. doi: 10.3934/naco.2018028

[15]

Alexander Tyatyushkin, Tatiana Zarodnyuk. Numerical method for solving optimal control problems with phase constraints. Numerical Algebra, Control & Optimization, 2017, 7 (4) : 481-492. doi: 10.3934/naco.2017030

[16]

Luís Tiago Paiva, Fernando A. C. C. Fontes. Adaptive time--mesh refinement in optimal control problems with state constraints. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4553-4572. doi: 10.3934/dcds.2015.35.4553

[17]

Theodore Tachim-Medjo. Optimal control of a two-phase flow model with state constraints. Mathematical Control & Related Fields, 2016, 6 (2) : 335-362. doi: 10.3934/mcrf.2016006

[18]

Vincenzo Basco, Piermarco Cannarsa, Hélène Frankowska. Necessary conditions for infinite horizon optimal control problems with state constraints. Mathematical Control & Related Fields, 2018, 8 (3&4) : 535-555. doi: 10.3934/mcrf.2018022

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

Jianling Li, Chunting Lu, Youfang Zeng. A smooth QP-free algorithm without a penalty function or a filter for mathematical programs with complementarity constraints. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 115-126. doi: 10.3934/naco.2015.5.115

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]