Abstract

In decision-making problems under uncertainty, probabilistic constraints are a valuable tool to express safety of decisions. They result from taking the probability measure of a given set of random inequalities depending on the decision vector. Even if the original set of inequalities is convex, this favourable property is not immediately transferred to the probabilistically constrained feasible set and may in particular depend on the chosen safety level. In this paper, we provide results guaranteeing the convexity of feasible sets to probabilistic constraints when the safety level is greater than a computable threshold. Our results extend all the existing ones and also cover the case where decision vectors belong to Banach spaces. The key idea in our approach is to reveal the level of underlying convexity in the nominal problem data (e.g., concavity of the probability function) by auxiliary transforming functions. We provide several examples illustrating our theoretical developments.

Author information

Contact details are reproduced from the original publication and may be historical.

Guilherme Matiussi Ramalho

Federal University of Santa Catarina, LABPLAN, Santa Catarina, Brazil

matiussipoli@gmail.com

Keywords

  • Probability constraints
  • convex analysis
  • elliptical distributions
  • stochastic optimization

Mathematics Subject Classification

90C15, 90C25

References

  1. S. Ahmed, W. Xie: Relaxations and approximations of chance constraints under finite distributions, Math. Programming 170/1 (2018) 43–65.https://doi.org/10.1007/s10107-018-1295-zGoogle Scholar
  2. M. Avriel, W. E. Diewert, S. Schaible, I. Zang: Generalized Concavity, Classics in Applied Mathematics 63, Society for Industrial and Applied Mathematics, Philadelphia (2010).https://doi.org/10.1137/1.9780898719437Google Scholar
  3. J. Barrera, T. Homem de Mello, E. Moreno, B. K. Pagnoncelli: Chance-constrained problems and rare events: an importance sampling approach, Math. Programming 157/1 (2016) 153–189.https://doi.org/10.1007/s10107-015-0942-xGoogle Scholar
  4. A. Ben-Tal, A. Nemirovski: Robust solutions of linear programming problems contaminated with uncertain data, Math. Programming, Ser. A 88 (2000) 411–424.https://doi.org/10.1007/PL00011380Google Scholar
  5. J. S. Brauchart, E. B. Saff, I. H. Sloan, R. S. Womersley: QMC designs: optimal order quasi Monte Carlo integration schemes on the sphere, Math. Computation 83 (2014) 2821–2851.https://doi.org/10.1090/S0025-5718-2014-02839-1Google Scholar
  6. I. Bremer, R. Henrion, A. Möller: Probabilistic constraints via SQP solver: Application to a renewable energy management problem, Comp. Management Science 12 (2015) 435–459.https://doi.org/10.1007/s10287-015-0228-zGoogle Scholar
  7. G. C. Calafiore, M. C. Campi: The scenario approach to robust control design, IEEE Trans. Automat. Control 51 (2006) 742–753.https://doi.org/10.1109/TAC.2006.875041Google Scholar
  8. D. Dentcheva: Optimisation models with probabilistic constraints, in: Lectures on Stochastic Programming. Modeling and Theory, A. Shapiro, D. Dentcheva and A. Ruszczyński (eds.), MPS-SIAM Series on Optimization 9, SIAM and MPS, Philadelphia (2009) 87–154.https://doi.org/10.1137/1.9780898718751.ch4Google Scholar
  9. D. Dentcheva, G. Martinez: Augmented Lagrangian method for probabilistic optimization, Ann. Oper. Res. 200/1 (2012) 109–130.https://doi.org/10.1007/s10479-011-0884-5Google Scholar
  10. D. Dentcheva, G. Martinez: Regularization methods for optimization problems with probabilistic constraints, Math. Programming, Ser. A 138/1-2 (2013) 223–251.https://doi.org/10.1007/s10107-012-0539-6Google Scholar
  11. D. Dentcheva, A. Prékopa, A. Ruszczyński: Concavity and efficient points for discrete distributions in stochastic programming, Math. Programming 89 (2000) 55–77.https://doi.org/10.1007/PL00011393Google Scholar
  12. A. L. Diniz, R. Henrion: On probabilistic constraints with multivariate truncated gaussian and lognormal distributions, Energy Systems 8/1 (2017) 149–167.https://doi.org/10.1007/s12667-015-0180-6Google Scholar
  13. A. L. Dontchev, R. T. Rockafellar: Implicit Functions and Solutions Mappings: A View from Variational Analysis, 2nd ed., Springer Series in Operations Research and Financial Engineering, Springer, New-York (2014).https://doi.org/10.1007/978-1-4939-1037-3Google Scholar
  14. Y. M. Ermoliev, T. Y. Ermolieva, G. J. Macdonald, V. I. Norkin: Stochastic optimization of insurance portfolios for managing exposure to catastrophic risk, Ann. Oper. Res. 99 (2000) 207–225.https://doi.org/10.1023/A:1019244405392Google Scholar
  15. C. I. Fábián, E. Csizmás, R. Drenyovszki, T. Vajnai, L. Kovács, T. Szántai: A randomized method for handling a difficult function in a convex optimization problem, motivated by probabilistic programming, Ann. Oper. Res. (2019) 1–32.https://doi.org/10.1007/s10479-019-03143-zGoogle Scholar
  16. C. I. Fábián, E. Csizmás, R. Drenyovszki, W. van Ackooij, T. Vajnai, L. Kovács, T. Szántai: Probability maximization by inner approximation, Acta Polytechnica Hungarica 15/1 (2018) 105–125.https://doi.org/10.12700/APH.15.1.2018.1.7Google Scholar
  17. K. Fang, S. Kotz, K. W. Ng: Symmetric Multivariate and Related Distributions, Monographs on Statistics and Applied Probability 36, Springer, Berlin (1990).https://doi.org/10.1007/978-1-4899-2937-2Google Scholar
  18. M. H. Farshbaf-Shaker, R. Henrion, D. Hömberg: Properties of chance constraints in infinite dimensions with an application to PDE constrained optimization, Set Valued Var. Analysis 26/4 (2018) 821–841.https://doi.org/10.1007/s11228-017-0452-5Google Scholar
  19. A. Geletu, A. Hoffmann, M. Klöppel, P. Li: A tractable approximation of non-convex chance constrained optimization with non-Gaussian uncertainties, Eng. Optimization 47/4 (2015) 495–520.https://doi.org/10.1080/0305215X.2014.905550Google Scholar
  20. T. González Gradón, H. Heitsch, R. Henrion: A joint model of probabilistic/robust constraints for gas transport management in stationary networks, Comp. Management Science 14 (2017) 443–460.https://doi.org/10.1007/s10287-017-0284-7Google Scholar
  21. A. Hantoute, R. Henrion, P. Pérez-Aros: Subdifferential characterization of continuous probability functions under Gaussian distribution, Math. Programming 174 (2019) 167–194.https://doi.org/10.1007/s10107-018-1237-9Google Scholar
  22. R. Henrion: Introduction to Chance Constraint Programming, Tutorial Paper for the Stochastic Programming Community HomePage, http://www.wias-berlin.de/people/henrion/publikat.html (2004).Google Scholar
  23. R. Henrion, A. Möller: A gradient formula for linear chance constraints under Gaussian distribution, Math. Oper. Res. 37 (2012) 475–488.https://doi.org/10.1287/moor.1120.0544Google Scholar
  24. R. Henrion, C. Strugarek: Convexity of chance constraints with independent random variables, Comp. Optimization Appl. 41 (2008) 263–276.https://doi.org/10.1007/s10589-007-9105-1Google Scholar
  25. R. Henrion, C. Strugarek: Convexity of chance constraints with dependent random variables: the use of copulae, in: Stochastic Optimization Methods in Finance and Energy: New Financial Products and Energy Market Strategies, M. Bertocchi, G. Consigli and M. A. H. Dempster (eds.), International Series in Operations Research and Management Science, Springer, New York (2011) 427–439.https://doi.org/10.1007/978-1-4419-9586-5_17Google Scholar
  26. L. J. Hong, Y. Yang, L. Zhang: Sequential convex approximations to joint chance constrained programed: A Monte Carlo approach, Oper. Res. 59/3 (2011) 617–630.https://doi.org/10.1287/opre.1100.0910Google Scholar
  27. K. Jittorntrum: An implicit function Theorem, J. Optimization Theory Appl. 25/4 (1978) 575–577.https://doi.org/10.1007/BF00933522Google Scholar
  28. S. Kataoka: it A stochastic programming model, Econometrica 31 (1963) 181–196.https://doi.org/10.2307/1910956Google Scholar
  29. A. I. Kibzun, S. Uryas’ev: Differentiability of probability function, Stochastic Analysis Appl. 16/6 (1998) 1101–1128.https://doi.org/10.1080/07362999808809581Google Scholar
  30. A. Kogan, M. A. Lejeune: Threshold Boolean form for joint probabilistic constraints with random technology matrix, Math. Programming 147/1-2 (2014) 391–427.https://doi.org/10.1007/s10107-013-0728-yGoogle Scholar
  31. A. Kogan, M. A. Lejeune, J. Luedtke: Erratum to: Threshold Boolean form for joint probabilistic constraints with random technology matrix, Math. Programming 155/1 (2016) 617–620.https://doi.org/10.1007/s10107-015-0960-8Google Scholar
  32. S. Küçükyavuz: On mixing sets arising in chance-constrained programming, Math. Programming 132/1-2 (2012) 31–56.https://doi.org/10.1007/s10107-010-0385-3Google Scholar
  33. S. Kumagai: An implicit function theorem: comment, J. Optimization Theory Appl. 31/2 (1980) 285–288.https://doi.org/10.1007/BF00934117Google Scholar
  34. C. M. Lagoa, X. Li, M. Sznaier: Probabilistically constrained linear programs and riskadjusted controller design, SIAM J. Control Optimization 15 (2005) 938–951.https://doi.org/10.1137/S1052623403430099Google Scholar
  35. Z. M. Landsman, E. A. Valdez: Tail conditional expectations for elliptical distributions, North Amer. Act. J. 7/4 (2013) 55–71.https://doi.org/10.1080/10920277.2003.10596118Google Scholar
  36. M. A. Lejeune: Pattern-based modeling and solution of probabilistically constrained optimization problems, Oper. Res. 60/6 (2012) 1356–1372.https://doi.org/10.1287/opre.1120.1120Google Scholar
  37. M. A. Lejeune, F. Margot: Solving chance-constrained optimization problems with stochastic quadratic inequalities, Oper. Res. 64/4 (2016) 939–957.https://doi.org/10.1287/opre.2016.1493Google Scholar
  38. M. A. Lejeune, N. Noyan: Mathematical programming approaches for generating p-efficient points, Eur. J. Oper. Res. 207/2 (2010) 590–600.https://doi.org/10.1016/j.ejor.2010.05.025Google Scholar
  39. J. Luedtke: An integer programming and decomposition approach to general chance-constrained mathematical programs, in: Integer Programming and Combinatorial Optimization, F. Eisenbrand and F. B. Shepherd (eds.), Lecture Notes in Computer Science 6080, Springer, Berlin (2010) 271–284.https://doi.org/10.1007/978-3-642-13036-6_21Google Scholar
  40. J. Luedtke, S. Ahmed: A sample approximation approach for optimization with probabilistic constraints, SIAM J. Optimization 19 (2008) 674–699.https://doi.org/10.1137/070702928Google Scholar
  41. J. Luedtke, S. Ahmed, G. L. Nemhauser: An integer programming approach for linear programs with probabilistic constraints, Math. Programming 122/2 (2010) 247–272.https://doi.org/10.1007/s10107-008-0247-4Google Scholar
  42. K. Marti: Differentiation of probability functions : the transformation method, Comp. Math. Appl. 30 (1995) 361–382.https://doi.org/10.1016/0898-1221(95)00113-1Google Scholar
  43. M. Minoux, R. Zorgati: Convexity of Gaussian chance constraints and of related probability maximization problems, Comp. Statistics 31/1 (2016) 387–408.https://doi.org/10.1007/s00180-015-0580-zGoogle Scholar
  44. R. B. Nelsen: An Introduction to Copulas, 2nd ed., Springer Series in Statistics, Springer, New York (2006).Google Scholar
  45. A. Nemirovski, A. Shapiro: Convex approximations of chance constrained programs, SIAM J. Optimization 17/4 (2006) 969–996.https://doi.org/10.1137/050622328Google Scholar
  46. B. Pagnoncelli, S. Ahmed, A. Shapiro: Sample average approximation method for chance constrained programming: Theory and applications, J. Optimization Theory Appl. 142 (2009) 399–416.https://doi.org/10.1007/s10957-009-9523-6Google Scholar
  47. A. Prékopa: Stochastic Programming, Kluwer, Dordrecht (1995).https://doi.org/10.1007/978-94-017-3087-7Google Scholar
  48. A. Prékopa: On the concavity of multivariate probability distributions functions, Oper. Res. Letters 29 (2001) 1–4.https://doi.org/10.1016/S0167-6377(01)00070-0Google Scholar
  49. A. Prékopa: Probabilistic programming, in: Stochastic Programming, A. Ruszczyński and A. Shapiro (eds.), Handbooks in Operations Research and Management Science 10, Elsevier, Amsterdam (2003) 267–351.https://doi.org/10.1016/S0927-0507(03)10005-9Google Scholar
  50. F. A. Ramponi: Consistency of the scenario approach, SIAM J. Optimization 28/1 (2018) 135–162.https://doi.org/10.1137/16M109819XGoogle Scholar
  51. J. O. Royset, E. Polak: Extensions of stochastic optimization results to problems with system failure probability functions, J. Optimization Theory Appl. 133/1 (2007) 1–18.https://doi.org/10.1007/s10957-007-9178-0Google Scholar
  52. A. Sklar: Fonctions de répartition à dimensions et leurs marges, Publ. Inst. Stat. Paris 8 (1959) 229–231.Google Scholar
  53. E. Tamm: On g-concave functions and probability measures (Russian), Eesti NSV Teaduste Akademia Toimetised, Füüsika-Matemaatika 28 (1977) 17–24.Google Scholar
  54. S. Uryas’ev: Derivatives of probability functions and some applications, Ann. Oper. Res. 56 (1995) 287–311.https://doi.org/10.1007/BF02031712Google Scholar
  55. S. Uryas’ev: Derivatives of probability and integral functions: General theory and examples, in: Encyclopedia of Optimization, C. A. Floudas and P. M. Pardalos (ed.), 2nd ed., Springer, Berlin (2009) 658–663.https://doi.org/10.1007/978-0-387-74759-0_119Google Scholar
  56. W. van Ackooij: Eventual convexity of chance constrained feasible sets, Optimization 64/5 (2015) 1263–1284.https://doi.org/10.1080/02331934.2013.855211Google Scholar
  57. W. van Ackooij: Convexity statements for linear probability constraints with Gaussian technology matrices and copulae correlated rows, ResearchGate (2017) 1–19, doi 10.13140/RG.2.2.11723.69926.Google Scholar
  58. W. van Ackooij, V. Berge, W. de Oliveira, C. Sagastizábal: Probabilistic optimization via approximate p-efficient points and bundle methods, Computers & Oper. Research 77 (2017) 177–193.https://doi.org/10.1016/j.cor.2016.08.002Google Scholar
  59. W. van Ackooij, W. de Oliveira: Convexity and optimization with copulae structured probabilistic constraints, Optimization 65/7 (2016) 1349–1376.https://doi.org/10.1080/02331934.2016.1179302Google Scholar
  60. W. van Ackooij, W. de Oliveira: Nonsmooth and nonconvex optimization via approximate difference-of-convex decompositions, J. Optimization Theory Appl. 182/1 (2018) 49–80.https://doi.org/10.1007/s10957-019-01500-3Google Scholar
  61. W. van Ackooij, A. Frangioni, W. de Oliveira: Inexact stabilized Benders’ decomposition approaches: with application to chance-constrained problems with finite support, Comp. Optimization Appl. 65/3 (2016) 637–669.https://doi.org/10.1007/s10589-016-9851-zGoogle Scholar
  62. W. van Ackooij, R. Henrion: (Sub-) Gradient formulae for probability functions of random inequality systems under Gaussian distribution, SIAM J. Uncertainty Quantification 5/1 (2017) 63–87.https://doi.org/10.1137/16M1061308Google Scholar
  63. W. van Ackooij, R. Henrion, A. Möller, R. Zorgati: Chance constrained programming and its applications to energy management, in: Stochastic Optimization – Seeing the Optimal for the Uncertain, I. Dritsas (ed.), InTechOpen (2011).https://doi.org/10.5772/15438Google Scholar
  64. W. van Ackooij, J. Malick: Eventual convexity of probability constraints with elliptical distributions, Math. Programming 175/1 (2019) 1–27.https://doi.org/10.1007/s10107-018-1230-3Google Scholar
  65. W. van Ackooij, C. Sagastizábal: Constrained bundle methods for upper inexact oracles with application to joint chance constrained energy problems, SIAM J. Optimization 24/2 (2014) 733–765.https://doi.org/10.1137/120903099Google Scholar
  66. H.-H. Wu, S. Küçükyavuz: Chance-constrained combinatorial optimization with a probability oracle and its application to probabilistic partial set covering, SIAM J. Optimization (2019) 1–37.Google Scholar
  67. Z. M. Zadeh, E. Khorram: Convexity of chance constrained programming problems with respect to a new generalized concavity notion, Ann. Oper. Res. 196/1 (2012) 651–662.https://doi.org/10.1007/s10479-012-1105-6Google Scholar

Suggested citation

Y. Laguel, W. Van Ackooij, J. Malick, G. Matiussi Ramalho. “On the Convexity of Level-Sets of Probability Functions.” Journal of Convex Analysis 29 (2022), No. 2, 411–442. https://doi.org/10.68381/jca29026

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2022. Rights now held by Banach Press.