(62f) A Stochastic Approximation Method for Approximating the Efficient Frontier of Chance-Constrained Nonlinear Programs

Chance-constrained optimization requires constraints with uncertain parameters to be satisfied with a minimum probability. It has applications in diverse areas such as chemical process systems, power systems, and finance [1-3]. Apart from a few known tractable cases, solving chance-constrained nonlinear programs (NLPs) to optimality is in general hard since the feasible region is not guaranteed to be convex and evaluating feasibility of the probabilistic constraint involves multi-dimensional integration. Motivated by a diverse array of applications, many numerical approaches for chance-constrained NLPs attempt to determine good-quality feasible solutions in reasonable computation times.

We propose a stochastic approximation method for approximating the efficient frontier of chance-constrained NLPs [4]. Our approach is based on a bi-objective viewpoint of chance-constrained programs that seeks solutions on the efficient frontier of optimal objective value versus risk of constraints violation. To this end, we construct a reformulated problem whose objective is to minimize the probability of constraints violation subject to deterministic convex constraints (which includes a bound on the objective function value). We adapt existing smoothing-based approaches for chance-constrained problems to derive a convergent sequence of smooth approximations of our reformulated problem and apply a projected stochastic subgradient algorithm to solve it. In contrast with exterior sampling-based approaches (such as sample average approximation) that approximate the original chance-constrained program with one having finite support, our proposal converges to stationary solutions of a smooth approximation of the original problem, thereby avoiding poor local solutions that may be an artefact of a fixed sample. Our results only require mild assumptions on the problem data and do not assume Gaussianity of the distribution of the uncertain parameters or make structural assumptions on the functions involved in the chance constraints. Our proposal also includes a tailored implementation of the smoothing-based approach that chooses key algorithmic parameters based on problem data. Computational results on four test problems from the literature indicate that our proposed approach can efficiently determine very good approximations of the efficient frontier, even for large-scale problems with joint chance constraints.

1. Shapiro, Alexander, Darinka Dentcheva, and Andrzej Ruszczynski. Lectures on stochastic programming: modeling and theory. Society for Industrial and Applied Mathematics, 2014.

2. Bienstock, Daniel, Michael Chertkov, and Sean Harnett. Chance-constrained optimal power flow: Risk-aware network control under uncertainty. SIAM Review, 56.3 (2014): 461-495.

3. Grossmann, Ignacio E., Robert M. Apap, Bruno A. Calfa, Pablo Garcia-Herreros, and Qi Zhang. Recent advances in mathematical programming techniques for the optimization of process systems under uncertainty. Computers & Chemical Engineering 91 (2016): 3-14.

4. Kannan, Rohit, and James R. Luedtke. A stochastic approximation method for approximating the efficient frontier of chance-constrained nonlinear programs. Mathematical Programming Computation (2021): 1-47.