Convergent Bounds for Stochastic Programs with Expected Value Constraints

Abstract

This article elaborates a bounding approximation scheme for convexmultistage stochastic programs (MSP) that constrain the conditional expectation ofsome decision-dependent random variables. Expected value constraints of this typeare useful for modelling a decision maker’s risk preferences, but they may also ariseas artefacts of stage-aggregation. It is shown that the gap between certain upper andlower bounds on the optimal objective value can be made smaller than any prescribedtolerance. Moreover, the solutions of some tractable approximate MSP give rise to apolicy which is feasible in the (untractable) original MSP, and this policy’s cost differsfrom the optimal cost at most by the difference between the bounds. The consideredproblem class comprises models with integrated chance constraints and conditionalvalue-at-risk constraints. No relatively complete recourse is assumed.