Gradient formulae for probability functions depending on a heterogenous family of constraints
Open Journal of Mathematical Optimization, Volume 2 (2021) , article no. 7, 29 p.

Probability functions measure the degree of satisfaction of certain constraints that are impacted by decisions and uncertainty. Such functions appear in probability or chance constraints ensuring that the degree of satisfaction is sufficiently high. These constraints have become a very popular modelling tool and are indeed intuitively easy to understand. Optimization problems involving probabilistic constraints have thus arisen in many sectors of the industry, such as in the energy sector. Finding an efficient solution methodology is important and first order information of probability functions play a key role therein. In this work we are motivated by probability functions measuring the degree of satisfaction of a potentially heterogenous family of constraints. We suggest a framework wherein each individual such constraint can be analyzed structurally. Our framework then allows us to establish formulae for the generalized subdifferential of the probability function itself. In particular we formally establish a (sub)-gradient formulæ for probability functions depending on a family of non-convex quadratic inequalities. The latter situation is relevant for gas-network applications.

Received:
Revised:
Accepted:
Published online:
DOI: https://doi.org/10.5802/ojmo.9
Classification: 90C15
Keywords: Stochastic optimization, probabilistic constraints, chance constraints, generalized gradients
@article{OJMO_2021__2__A7_0,
     author = {Wim van Ackooij and Pedro P\'erez-Aros},
     title = {Gradient formulae for probability functions depending on a heterogenous family of constraints},
     journal = {Open Journal of Mathematical Optimization},
     eid = {7},
     publisher = {Universit\'e de Montpellier},
     volume = {2},
     year = {2021},
     doi = {10.5802/ojmo.9},
     language = {en},
     url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.9/}
}
Wim van Ackooij; Pedro Pérez-Aros. Gradient formulae for probability functions depending on a heterogenous family of constraints. Open Journal of Mathematical Optimization, Volume 2 (2021) , article  no. 7, 29 p. doi : 10.5802/ojmo.9. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.9/

[1] Denis Adelhütte; Dnis Aßmann; Tatiana Gonzàlez-Gradòn; Martin Gugat; Holger Heitsch; René Henrion; Frauke Liers; Sabrina Nitsche; Rüdiger Schultz; Michael Stingl; David Wintergerst Joint model of probabilistic (probust) constraints with application to gas network optimization, Vietnam J. Math., Volume Online (2020), pp. 1-34 | Article

[2] Vladimir I. Bogachev Measure theory. Vol. I and II, Springer, 2007, xviii+500 pp. and xiv+575 pages | Article | Zbl 1120.28001

[3] Ingo Bremer; René Henrion; Andris Möller Probabilistic constraints via SQP solver: Application to a renewable energy management problem, Comput. Manag. Sci., Volume 12 (2015) no. 3, pp. 435-459

[4] Alexander Bruhns; Gilles Deurveilher; Jean-Sébastien. Roy A non-linear regression model for mid-term load forecasting and improvements in seasonality, 2005 (PSCC 2005 Luik)

[5] Frank H. Clarke Optimisation and Nonsmooth Analysis, Classics in Applied Mathematics, Society for Industrial and Applied Mathematics, 1987, 320 pages | Article

[6] Donald L. Cohn Measure theory, Birkhäuser Advanced Texts. Basler Lehrbücher, Birkhäuser, 2013, xxi+457 pages | Article

[7] Darinka Dentcheva Optimisation models with probabilistic constraints, Lectures on Stochastic Programming. Modeling and Theory (MPS/SIAM Series on Optimization), Volume 9, Society for Industrial and Applied Mathematics, 2009, pp. 87-154

[8] Jürgen Elstrodt Maß und Integrationstheorie, Springer-Lehrbuch, Springer, 2011, 451 pages | Article

[9] Kai-Tai Fang; Samuel Kotz; Kai-Wang Ng Symmetric multivariate and related distributions, Monographs on Statistics and Applied Probability, 36, Chapman & Hall, 1990, x+220 pages

[10] Josselin Garnier; Abdennebi Omrane; Youssef Rouchdy Asymptotic formulas for the derivatives of probability functions and their Monte Carlo estimations, Eur. J. Oper. Res., Volume 198 (2009), pp. 848-858 | Article

[11] Alan Genz Numerical computation of multivariate normal probabilities, J. Comput. Graph. Stat., Volume 1 (1992), pp. 141-149

[12] Claudia Gotzes; Holger Heitsch; René Henrion; Rüdiger Schultz On the quantification of nomination feasibility in stationary gas networks with random loads, Math. Methods Oper. Res., Volume 84 (2016) no. 2, pp. 427-457 | Article

[13] Abderrahim Hantoute; René Henrion; Pedro Pérez-Aros Subdifferential characterization of continuous probability functions under Gaussian distribution, Math. Program., Volume 174 (2019) no. 1-2, pp. 167-194 | Article

[14] Holger Heitsch On probabilistic capacity maximization in a stationary gas network, Optimization, Volume 69 (2020) no. 3, pp. 575-604 | Article

[15] René Henrion Optimierungsprobleme mit Wahrscheinlichkeitsrestriktionen: Modelle, Struktur, Numerik, 2016

[16] René Henrion; Werner Römisch Lipschitz and differentiability properties of quasi-concave and singular normal distribution functions, Ann. Oper. Res., Volume 177 (2010), pp. 115-125 | Article

[17] Andrey Kibzun; Stanislav Uryasev Differentiability of Probability function, Stochastic Anal. Appl., Volume 16 (1998), pp. 1101-1128 | Article

[18] Zinoviy M. Landsman; Emiliano A. Valdez Tail Conditional Expectations for Elliptical distributions, N. Am. Actuar. J., Volume 7 (2003) no. 4, pp. 55-71 | Article

[19] Kurt Marti Differentiation formulas for probability functions: The transformation method, Math. Program., Volume 75 (1996) no. 2, pp. 201-220

[20] Boris S. Mordukhovich Variational Analysis and Applications, Springer Monographs in Mathematics, Springer, 2018, xix+622 pages | Article

[21] András Prékopa Stochastic Programming, Kluwer Academic Publishers, 1995 | Article

[22] András Prékopa Probabilistic programming, Stochastic Programming (A. Ruszczyński; A. Shapiro, eds.) (Handbooks in Operations Research and Management Science), Volume 10, Elsevier, 2003, pp. 267-351

[23] R. Tyrrell Rockafellar; Roger J.-B. Wets Variational Analysis, Grundlehren der Mathematischen Wissenschaften, 317, Springer, 2009, 734 pages | Article

[24] Johannes O. Royset; Elijah Polak Implementable algorithm for stochastic optimization using sample average approximations, J. Optim. Theory Appl., Volume 122 (2004) no. 1, pp. 157-184 | Article

[25] Johannes O. Royset; Elijah Polak Extensions of stochastic optimization results to problems with system failure probability functions, J. Optim. Theory Appl., Volume 133 (2007) no. 1, pp. 1-18 | Article

[26] Walter Rudin Real and complex analysis, McGraw-Hill Series in Higher Mathematics, McGraw-Hill, 1987, xiv+416 pages

[27] Stanislav Uryasev Derivatives of probability and Integral functions: General Theory and Examples, Encyclopedia of Optimization, Springer, 2009, pp. 658-663

[28] Wim van Ackooij A discussion of probability functions and constraints from a variational perspective, Set-Valued Var. Anal., Volume 28 (2020) no. 4, pp. 585-609 | Article

[29] Wim van Ackooij; Ivana Aleksovska; M. Munoz-Zuniga (Sub-)Differentiability of probability functions with elliptical distributions, Set-Valued Var. Anal., Volume 26 (2018) no. 4, pp. 887-910 | Article | Zbl 1416.90028

[30] Wim van Ackooij; Irène Danti Lopez; Antonio Frangioni; Fabrizio Lacalandra; Milad Tahanan Large-scale Unit Commitment under uncertainty: an updated literature survey, Ann. Oper. Res., Volume 271 (2018) no. 1, pp. 11-85 | Article

[31] Wim van Ackooij; René Henrion Gradient formulae for nonlinear probabilistic constraints with Gaussian and Gaussian-like distributions, SIAM J. Optim., Volume 24 (2014) no. 4, pp. 1864-1889 | Article

[32] Wim van Ackooij; René Henrion (Sub-)gradient formulae for probability functions of random inequality systems under Gaussian distribution, SIAM/ASA J. Uncertain. Quantif., Volume 5 (2017) no. 1, pp. 63-87 | Article

[33] Wim van Ackooij; René Henrion; Pedro Pérez-Aros Generalized gradients for probabilistic/robust (probust) constraints, Optimization, Volume 69 (2020) no. 7-8, pp. 1451-1479 | Article

[34] Wim van Ackooij; Paul Javal; Pedro Pérez-Aros Derivatives of probability functions acting on parameter dependent unions of polyhedra, Set-Valued Var. Anal. (2021), pp. 1-33 | Article

[35] Wim van Ackooij; Jérôme Malick Eventual convexity of probability constraints with elliptical distributions, Math. Program., Volume 175 (2019) no. 1-2, pp. 1-627 | Article

[36] Wim van Ackooij; Pedro Pérez-Aros Generalized differentiation of probability functions acting on an infinite system of constraints, SIAM J. Optim., Volume 29 (2019) no. 3, pp. 2179-2210

[37] Wim van Ackooij; Pedro Pérez-Aros Gradient formulae for nonlinear probabilistic constraints with non-convex quadratic forms, J. Optim. Theory Appl., Volume 185 (2020) no. 1, pp. 239-269 | Article

[38] Wim van Ackooij; Pedro Pérez-Aros Generalized differentiation of probability functions: parameter dependent sets given by intersections of convex sets and complements of convex sets. (2021) (working paper)