(441a) A Sigmoidal Approximation for Chance-Constrained Nonlinear Programs

Authors: 
Cao, Y., University of Wisconsin-Madison
Zavala, V. M., University of Wisconsin-Madison
Chance constraints (CCs) are powerful decision-making paradigm that enable decision makers to directly control risk. A CC (also known as a probabilistic constraint) imposes a requirement on the probability that a constraint is satisfied. Mathematically, this a CC can be expressed as P(g(x,W)≤0)≥α, where x is the decision variable and W is a random parameter vector. Unfortunately, nonlinear programs (NLPs) with CCs cannot be handled by standard optimization solvers and specialized reformulations and/or approximations are needed.

The most straightforward and general reformulation of a CC introduces binary variables to count the number of realizations under which the constraint g(x,w)≤0 is satisfied/violated, giving rise to a large-scale MINLP [1]. This reformulation exploits the fact that that the CC can be expressed as the expectation of the indicator function.

A popular conservative approximation for a CC requires that the constraint is satisfied over all possible realizations w of the random variable W (i.e., g(x,w)≤0 is satisfied with probability one) [2]. This scenario-based approximation can be easily handled using structured NLP solvers but can give very conservative solutions.

A CC can also be approximated in a conservative manner by using a conditional value-at-risk (CVaR) constraint [3]. This approach has been shown to be equivalent to an outer-approximation of the indicator function. The CVaR formulation can also be handled by structured NLP solvers but also yields very conservative solutions. The authors in [4] propose a difference of convex functions (DC) approximation for the indicator function and they show that the approximation can be made asymptotically exact. Unfortunately, this formulation requires specialized solution algorithms that are not guaranteed to work in a general nonconvex NLP setting.

In this talk, we propose a new approximation for CCs based on a risk metric that we call the sigmoidal value at risk (SigVaR). This metric is constructed by using a smooth outer-approximation of the indicator function. We prove that this approximation is conservative but that the level of conservatism can be made arbitrarily small for limiting parameter values. The SigVaR approximation brings computational benefits over exact mixed-integer and difference of convex functions reformulations because, as with CVaR and the scenario-based approximation, it can be handled using structured NLP solvers. We establish formal connections between SigVaR and CVaR that allow us to identify suitable parameter values for the approximation. We present small- and large-scale numerical studies including a wind turbine and a flare system optimization study [5,6] to demonstrate that SigVaR dramatically reduces conservatism of existing approaches.

[1] J. Luedtke, S. Ahmed, and G. L. Nemhauser, An integer programming approach for linear programs with probabilistic constraints, Mathematical Programming, 122 (2010), pp. 247-272.

[2] G. Calafiore and M. C. Campi, Uncertain convex programs: randomized solutions and confidence levels, Mathematical Programming, 102 (2005), pp. 25-46.

[3] A. Nemirovski and A. Shapiro, Scenario approximations of chance constraints, in Probabilistic and randomized methods for design under uncertainty, Springer, 2006, pp. 3-47.

[4] L. J. Hong, Y. Yang, and L. Zhang, Sequential convex approximations to joint chance constrained programs: Amontecarloapproach, Operations Research, 59 (2011), pp. 617-630.

[5] Y. Cao, F. D'Amato, and V. M. Zavala, Stochastic optimization formulations for wind turbine power maximization and extreme load mitigation, Under Review, 2017.

[6] J. Tovar-Facio, Y. Cao, J.M. Ponce-Ortega, and V. M. Zavala. Scalable Solution Strategies for Chance-Constrained Nonlinear Programs. Under Review, 2018.