Abstract
In many practical applications models exhibiting chance constraints play a role. Since, in practice one is also typically interesting in numerically solving the underlying optimization problems, an interest naturally arises in understanding analytical properties, such as differentiability, of probability functions. However in order to build nonlinear programming methods, not only knowledge of differentiability, but also explicit formulæ for gradients are important. Unfortunately, differentiability of probability functions cannot be taken for granted. In this paper, motivated by applications from energy management, wherein we face a variety of non-linear transforms of underlying Elliptical distributions, we investigate probability functions acting on decision dependent union of polyhedra. Union of polyhedra naturally occur as soon as one approaches the components of “difference-of-convex” (DC) functions with their respective cutting plane models. In this work, we will establish that the probability functions are locally Lipschitzian and exhibit explicit formulæ for “the” Clarke sub-gradients, under very mild conditions. We also highlight, on a numerical example, that the formulæ can be put to use “in practice”.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Prékopa, A.: Stochastic programming. Kluwer, Dordrecht (1995)
Prékopa, A.: Probabilistic programming. In: Ruszczyński, A., Shapiro, A. (eds.) Stochastic Programming, Handbooks in Operations Research and Management Science, vol. 10, pp. 267–351. Elsevier, Amsterdam (2003)
Dentcheva, D.: Optimisation models with probabilistic constraints. In: Shapiro, A., Dentcheva, D., Ruszczyński, A. (eds.) Lectures on Stochastic Programming. Modeling and Theory, MPS-SIAM series on optimization, vol. 9, pp. 87–154. SIAM and MPS, Philadelphia (2009)
Henrion, R.: Optimierungsprobleme mit wahrscheinlichkeitsrestriktionen: Modelle, struktur, numerik. Lect. Notes, 1–53 (2016)
Luedtke, J., Ahmed, S.: A sample approximation approach for optimization with probabilistic constraints. SIAM J. Optim. 19, 674–699 (2008)
Luedtke, J.: An integer programming and decomposition approach to general chance-constrained mathematical programs. In: Eisenbrand, F., Shepherd, F.B. (eds.) Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 6080, pp. 271–284. Springer (2010)
Luedtke, J., Ahmed, S., Nemhauser, G.L.: An integer programming approach for linear programs with probabilistic constraints. Math. Program. 122 (2), 247–272 (2010)
Luedtke, J.: A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support. Math. Program. 146(1-2), 219–244 (2014)
Liu, X., Küçükyavuz, S., Luedtke, J.: Decomposition algorithm for two-stage chance constrained programs. Math. Programm. Ser. B 157(1), 219–243 (2016). https://doi.org/10.1007/s10107-014-0832-7
Pagnoncelli, B., Ahmed, S., Shapiro, A.: Sample average approximation method for chance constrained programming: Theory and applications. J. Optim. Theory Appl 142, 399–416 (2009)
van Ackooij, W, Frangioni, A., de Oliveira, W.: Inexact stabilized Benders’ decomposition approaches: with application to chance-constrained problems with finite support. Comput. Optim. Appl. 65(3), 637–669 (2016). https://doi.org/10.1007/s10589-016-9851-z
Küçükyavuz, S.: On mixing sets arising in chance-constrained programming. Math. Program. 132(1-2), 31–56 (2012)
Kannan, R., Luedtke, J.: A stochastic approximation method for approximating the efficient frontier of chance-constrained nonlinear programs. Math. Program. Comput., 1–47. https://doi.org/10.1007/s12532-020-00199-y (2020)
n-Ordieres, A.P., Luedtke, J.R., Wächter, A.: Solving chance-constrained problems via a smooth sample-based nonlinear approximation. SIAM J. Optim. 30(3), 2221–2250 (2020)
Lejeune, M.A.: Pattern-based modeling and solution of probabilistically constrained optimization problems. Oper. Res. 60(6), 1356–1372 (2012)
Lejeune, M., Margot, F.: Solving chance-constrained optimization problems with stochastic quadratic inequalities. Oper. Res. 64(4), 939–957 (2016)
Dentcheva, D., Prékopa, A., Ruszczyński, A.: Concavity and efficient points for discrete distributions in stochastic programming. Math. Program. 89, 55–77 (2000)
Dentcheva, D., Lai, B., Ruszczyński, A.: Dual methods for probabilistic optimization problems. Math. Methods Oper. Res. 60(2), 331–346 (2004)
Dentcheva, D., Martinez, G.: Augmented lagrangian method for probabilistic optimization. Ann. Oper. Res. 200(1), 109–130 (2012)
Dentcheva, D., Martinez, G.: Regularization methods for optimization problems with probabilistic constraints. Math. Programm. (Ser. A) 138(1-2), 223–251 (2013)
Lejeune, M.A.: Pattern definition of the p-efficiency concept. Ann. Oper. Res. 200, 23–36 (2012)
Lejeune, M.A., Noyan, N.: Mathematical programming approaches for generating p-efficient points. Eur. J. Oper. Res. 207(2), 590–600 (2010)
van Ackooij, W, Berge, V., de Oliveira, W., Sagastizábal, C.: Probabilistic optimization via approximate p-efficient points and bundle methods. Comput. Oper. Res. 77, 177–193 (2017). https://doi.org/10.1016/j.cor.2016.08.002
Ben-Tal, A., Nemirovski, A.: Robust solutions of linear programming problems contaminated with uncertain data. Math. Programm. Ser. A 88, 411–424 (2000)
Ben-Tal, A., Ghaoui, L.E., Nemirovski, A.: Robust optimization. Princeton University Press (2009)
Ermoliev, Y.M., Ermolieva, T.Y., Macdonald, G.J., Norkin, V.I.: Stochastic optimization of insurance portfolios for managing exposure to catastrophic risk. Ann. Oper. Res. 99, 207–225 (2000)
Calafiore, G.C., Campi, M.C.: The scenario approach to robust control design. IEEE Trans. Automat. Control 51, 742–753 (2006)
Campi, M.C., Garatti, S.: A sampling-and-discarding approach to chance-constrained optimization: Feasibility and optimality. J. Optim. Theory Appl. 148(2), 257–280 (2011)
Nemirovski, A., Shapiro, A.: Convex approximations of chance constrained programs. SIAM J. Optim. 17(4), 969–996 (2006)
Hong, L.J., Yang, Y., Zhang, L.: Sequential convex approximations to joint chance constrained programed: A monte carlo approach. Oper. Res. 3(59), 617–630 (2011)
Geletu, A., Hoffmann, A., Klöppel, M., Li, P.: A tractable approximation of non-convex chance constrained optimization with non-gaussian uncertainties. Eng. Optim. 47(4), 495–520 (2015)
Hu, Z., Hong, L.J., Zhang, L.: A smooth monte carlo approach to joint chance-constrained programs. IIE Trans. 45(7), 716–735 (2013)
Tuy, H.: Convex analysis and global optimization, Nonconvex Optimization and Its Applications, vol. 22. Springer (2016)
Garnier, J., Omrane, A., Rouchdy, Y.: Asymptotic formulas for the derivatives of probability functions and their Monte Carlo estimations. Eur. J. Oper. Res. 198, 848–858 (2009). https://doi.org/10.1016/j.ejor.2008.09.026
Kibzun, A.I., Uryas’ev, S.: Differentiability of probability function. Stoch. Anal. Appl. 16, 1101–1128 (1998). https://doi.org/10.1080/07362999808809581
Marti, K.: Differentiation of probability functions : The transformation method. Comput. Math. Appl. 30, 361–382 (1995). https://doi.org/10.1016/0898-1221(95)00113-1
Pflug, G., Weisshaupt, H.: Probability gradient estimation by set-valued calculus and applications in network design. SIAM J. Optim. 15, 898–914 (2005). https://doi.org/10.1137/S1052623403431639
Raik, E.: The differentiability in the parameter of the probability function and optimization of the probability function via the stochastic pseudogradient method (russian). Izvestiya Akad. Nayk Est. SSR, Phis. Math. 24(1), 3–6 (1975)
Royset, J.O., Polak, E.: Implementable algorithm for stochastic optimization using sample average approximations. J. Optim. Theory Appl. 122(1), 157–184 (2004). https://doi.org/10.1023/B:JOTA.0000041734.06199.71
Royset, J.O., Polak, E.: Extensions of stochastic optimization results to problems with system failure probability functions. J. Optim. Theory Appl. 133(1), 1–18 (2007). https://doi.org/10.1007/s10957-007-9178-0
Uryas’ev, S.: Derivatives of probability functions and integrals over sets given by inequalities. J. Comput. Appl. Math. 56(1-2), 197–223 (1994). https://doi.org/10.1016/0377-0427(94)90388-3
Uryas’ev, S.: Derivatives of probability functions and some applications. Ann. Oper. Res. 56, 287–311 (1995). https://doi.org/10.1007/BF02031712
van Ackooij, W, Henrion, R.: Gradient formulae for nonlinear probabilistic constraints with Gaussian and Gaussian-like distributions. SIAM J. Optim. 24(4), 1864–1889 (2014). https://doi.org/10.1137/130922689
van Ackooij, W, Henrion, R.: (Sub-) Gradient formulae for probability functions of random inequality systems under Gaussian distribution. SIAM J. Uncertain. Quant. 5(1), 63–87 (2017). https://doi.org/10.1137/16M1061308
van Ackooij, W, Aleksovska, I., Zuniga, M.M.: (sub-)differentiability of probability functions with elliptical distributions. Set Valued Var. Anal. 26(4), 887–910 (2018). https://doi.org/10.1007/s11228-017-0454-3
van Ackooij, W., Malick, J.: Second-order differentiability of probability functions. Optim. Lett. 11(1), 179–194 (2017). https://doi.org/10.1007/s11590-016-1015-7
Hantoute, A., Henrion, R., Pérez-Aros, P.: Subdifferential characterization of continuous probability functions under Gaussian distribution. Math. Program. 174 (1-2), 167–194 (2019). https://doi.org/10.1007/s10107-018-1237-9
van Ackooij, W, Pérez-Aros, P.: Generalized differentiation of probability functions acting on an infinite system of constraints. SIAM J. Optim. 29 (3), 2179–2210 (2019)
van Ackooij, W., Henrion, R., Pérez-Aros, P.: Generalized gradients for probabilistic/robust (probust) constraints. Optimization 69(7-8), 1451–1479 (2020). https://doi.org/10.1080/02331934.2019.1576670
van Ackooij, W., Pérez-Aros, P.: Gradient formulae for nonlinear probabilistic constraints with non-convex quadratic forms. J. Optim. Theory Appl. 185 (1), 239–269 (2020). https://doi.org/10.1007/s10957-020-01634-9
van Ackooij, W., Pérez-Aros, P.: Generalized differentiation of probability functions: parameter dependent sets given by intersections of convex sets and complements of convex sets. Working paper (2021)
Fang, K., Kotz, S., Ng, K.W.: Symmetric multivariate and related distributions, 1st edn. Monographs on Statistics and Applied Probability, vol. 36. Springer-Science (1990)
Landsman, Z.M., Valdez, E.A.: Tail conditional expectations for elliptical distributions. North Amer. Actuarial J. 7(4), 55–71 (2013). https://doi.org/10.1080/10920277.2003.10596118
Elstrodt, J.: Maßund integrationstheorie, 7th edn. Springer (2011)
Farshbaf-Shaker, M.H., Henrion, R., Hömberg, D.: Properties of chance constraints in infinite dimensions with an application to pde constrained optimization. Set Valued Var. Anal. 26(4), 821–841 (2018). https://doi.org/10.1007/s11228-017-0452-5
van Ackooij, W., Minoux, M.: A characterization of the subdifferential of singular Gaussian distribution functions. Set Valued Var. Anal. 23(3), 465–483 (2015). https://doi.org/10.1007/s11228-015-0317-8
Henrion, R., Römisch, W.: Lipschitz and differentiability properties of quasi-concave and singular normal distribution functions. Ann. Oper. Res. 177, 115–125 (2010). https://doi.org/10.1007/s10479-009-0598-0
Henrion, R., Möller, A.: A gradient formula for linear chance constraints under Gaussian distribution. Math. Oper. Res. 37, 475–488 (2012). https://doi.org/10.1287/moor.1120.0544
van Ackooij, W., Henrion, R., Möller, A., Zorgati, R.: On joint probabilistic constraints with Gaussian Coefficient Matrix. Oper. Res. Lett. 39, 99–102 (2011). https://doi.org/10.1016/j.orl.2011.01.005
Clarke, F.H.: Optimisation and nonsmooth analysis, Classics in Applied Mathematics. Society for Industrial and Applied Mathematics (1987)
Jofre, A., Thibault, L.: D-representation of subdifferentials of directionally lipschitz functions. Proc. Amer. Math. Soc. 110(1), 117–123 (1990)
Correa, R., Hantoute, A., Pérez-Aros, P.: Subdifferential calculus rules for possibly nonconvex integral functions. SIAM J. Control Optim. 58(1), 462–484 (2020). https://doi.org/10.1137/18M1176476
Henrion, R.: Calmness as a constraint qualification for M-stationarity conditions in MPECs. In: Aussel, D., Latitha, C. (eds.) Generalized nash equilibrium problems, bilevel programming and MPEC, Forum for Interdisciplinary Mathematics, pp. 21–41. Springer Singapore (2017)
Surowiec, T.M.: Explicit stationarity conditions and solution characterization for equilibrium problems with equilibrium constraints. Ph.D. Thesis, Humboldt-Universität zu Berlin (2010)
van Ackooij, W., Malick, J.: Eventual convexity of probability constraints with elliptical distributions. Math. Program. 175(1), 1–27 (2019). https://doi.org/10.1007/s10107-018-1230-3
Kuo, F.Y., Sloan, I.H.: Quasi-Monte Carlo methods can be efficient for integration over products of spheres. J. Complex. 21, 196–210 (2005)
Heitsch, H.: On probability capacity maximization in a stationary gas network. Optimization 69(3), 575–604 (2020). https://doi.org/10.1080/02331934.2019.1625353
Gotzes, C., Heitsch, H., Henrion, R., Schultz, R.: On the quantification of nomination feasibility in stationary gas networks with random loads. Math. Methods Oper. Res. 84, 427–457 (2016). https://doi.org/10.1007/s00186-016-0564-y
van Ackooij, W., Henrion, R., Möller, A.s, Zorgati, R.: Joint chance constrained programming for hydro reservoir management. Optim. Eng. 15, 509–531 (2014). https://doi.org/10.1007/s11081-013-9236-4
Shapiro, A., Tekaya, W., da Costa, J.P., Soares, M.P.: Risk neutral and risk averse stochastic dual dynamic programming method. Eur. J. Oper. Res. 224(2), 375–391 (2013). https://doi.org/10.1016/j.ejor.2012.08.022
Bruhns, A., Deurveilher, G., Roy, J.S.: A non-linear regression model for mid-term load forecasting and improvements in seasonality. PSCC 2005 Luik (2005)
Bremer, I., Henrion, R., Möller, A.: Probabilistic constraints via SQP solver: Application to a renewable energy management problem. Comput. Manag. Sci. 12, 435–459 (2015)
Hager, W.W., Phan, D.T., Zhu, J.: Projection algorithms for nonconvex minimization with application to sparse principal component analysis. J. Glob. Optim. 65 (4), 657–676 (2016). https://doi.org/10.1007/s10898-016-0402-z
Acknowledgements
The third author was partially supported by: CONICYT GRANTS: FONDECYT REGULAR 1190110 AND FONDECYT REGULAR 1200283 AND PROGRAMA REGIONAL MATHAMSUD 20-MATH-08 CODE: MATH190003
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix
A An approximate projected gradient algorithm
We present in this Appendix a generic algorithm, similar to the one used in [67, Section 6] for solving the following problem:
where f is assumed to be affine, and ϕ is as defined in (1). We also assume that a point \(x_{0} \in X^{\prime } := \{x\in X : \mathbb {P}[ g(x,\xi ) \leq 0] \ge p\}\) is known (and therefore this set is not empty). Let us define \(\tau _{X^{\prime }}^{x_{0}} : X \mapsto [0,1]\) as follows:
and let us define \(P_{X^{\prime }}^{x_{0}} : X \rightarrow X^{\prime }\) as \(P_{X^{\prime }}^{x_{0}}(x) = (1-\tau _{X^{\prime }}^{x_{0}}(x))x + \tau _{X^{\prime }}^{x_{0}}(x) x_{0}\). Since \(X^{\prime }\) is a closed set, \(\tau _{X^{\prime }}^{x_{0}}\) and thus \(P_{X^{\prime }}^{x_{0}}\) are well defined. Since, it is not a proper projection, this algorithm is sometimes referred to as an approximate projected gradient algorithm. Convergence of such an algorithm is studied for example in [73]. Obtaining a numerical value for \(\tau _{X^{\prime }}^{x_{0}}\) can be done using a bisection method, having at each iteration k to compute \(\mathbb {P}[g((1-t_{k})x + t_{k} x_{0},\xi ) \le 0]\) and stopping when it reaches p up to a given tolerance.
The formulæ (33) can be exploited to compute ∇ϕ(xk) at a given trial point upon verifying condition (40).
Rights and permissions
About this article
Cite this article
van Ackooij, W., Javal, P. & Pérez-Aros, P. Derivatives of Probability Functions: Unions of Polyhedra and Elliptical Distributions. Set-Valued Var. Anal 30, 487–519 (2022). https://doi.org/10.1007/s11228-021-00598-w
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11228-021-00598-w