Nonconvex and Nonsmooth Approaches for Affine Chance-Constrained Stochastic Programs

Ying Cui, Junyi Liu, Jong Shi Pang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Chance-constrained programs (CCPs) constitute a difficult class of stochastic programs due to its possible nondifferentiability and nonconvexity even with simple linear random functionals. Existing approaches for solving the CCPs mainly deal with convex random functionals within the probability function. In the present paper, we consider two generalizations of the class of chance constraints commonly studied in the literature; one generalization involves probabilities of disjunctive nonconvex functional events and the other generalization involves mixed-signed affine combinations of the resulting probabilities; together, we coin the term affine chance constraint (ACC) system for these generalized chance constraints. Our proposed treatment of such an ACC system involves the fusion of several individually known ideas: (a) parameterized upper and lower approximations of the indicator function in the expectation formulation of probability; (b) external (i.e., fixed) versus internal (i.e., sequential) sampling-based approximation of the expectation operator; (c) constraint penalization as relaxations of feasibility; and (d) convexification of nonconvexity and nondifferentiability via surrogation. The integration of these techniques for solving the affine chance-constrained stochastic program (ACC-SP) is the main contribution of this paper. Indeed, combined together, these ideas lead to several algorithmic strategies with various degrees of practicality and computational efforts for the nonconvex ACC-SP. In an external sampling scheme, a given sample batch (presumably large) is applied to a penalty formulation of a fixed-accuracy approximation of the chance constraints of the problem via their expectation formulation. This results in a sample average approximation scheme, whose almost-sure convergence under a directional derivative condition to a Clarke stationary solution of the expectation constrained-SP as the sample sizes tend to infinity is established. In contrast, sequential sampling, along with surrogation leads to a sequential convex programming based algorithm whose asymptotic convergence for fixed- and diminishing-accuracy approximations of the indicator function can be established under prescribed increments of the sample sizes.

Original languageEnglish (US)
Pages (from-to)1149-1211
Number of pages63
JournalSet-Valued and Variational Analysis
Volume30
Issue number3
DOIs
StatePublished - Sep 2022

Bibliographical note

Funding Information:
This work was based on research supported by the U.S. Air Force Office of Sponsored Research under grant FA9550-18-1-0382. Acknowledgements

Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Nature B.V.

Keywords

  • Chance constraints
  • Continuous approximations
  • Exact penalization
  • Nonconvex
  • Nonsmooth
  • Sampling

Fingerprint

Dive into the research topics of 'Nonconvex and Nonsmooth Approaches for Affine Chance-Constrained Stochastic Programs'. Together they form a unique fingerprint.

Cite this