Learning optimal solutions to chance-constrained optimization models from limited data

Music City Center 

We consider the challenge of provisioning resources to meet high reliability or service level requirements, which are typical in applications such as power distribution, emergency response, and regulatory risk management. With chance-constrained optimization serving as a natural starting point for modeling this class of problems, our main contribution is to characterize how the optimal costs and decisions scale for a generic joint chance-constrained model as the target probability of satisfying the reliability constraints approaches its maximal level. Besides providing insights into the behaviour of optimal costs and decisions based on large-deviations theory, the scaling result carries several algorithmic implications, beginning with the following observation on distributionally robust optimization (DRO) modeling of chance constraints: While widely used DRO approaches based on KL-divergences, Wasserstein distances, and moments distort the scaling properties of optimal decisions and lead to exponentially higher costs, incorporating marginal distributions or employing suitably chosen f -divergence balls preserves the correct scaling and ensures that decisions remain conservative by at most a constant or logarithmic factor. Further, given N data samples, we demonstrate how the scaling can serve as a basis for estimating approximately Pareto-optimal decisions whose constraint violation probabilities can even be smaller than the Ω(1/N)−estimation barrier that is fundamental in the absence of parametric assumptions.

Distributionally Robust Optimization

Chance constrained optimization

Extreme value extrapolation

Pareto efficiency

Rare events

Large deviations