Efficient Scenario Generation for Heavy-Tailed Chance Constrained Optimization

José Blanchet, Fan Zhang, Bert ZwartStochastic 2020

Abstract

We consider a generic class of chance-constrained optimization problems with heavy-tailed (i.e., power-law type) risk factors. In this setting, we use the scenario approach to obtain a constant approximation to the optimal solution with a computational complexity that is uniform in the risk tolerance parameter. We additionally illustrate the efficiency of our algorithm in the context of solvency in insurance networks.

Introduction

In fields such as finance, insurance, and telecommunications, decision-makers frequently face chance-constrained optimization (CCP) problems. The objective is to minimize costs or maximize returns while ensuring that the probability of a system failure—such as a portfolio loss or a systemic default in an insurance network—remains below a small threshold, $\delta$.

The standard approach to solving CCP is the "scenario approach," which involves sampling $N$ potential future states and ensuring the decision is robust against all of them. However, for high-reliability requirements (e.g., $\delta = 10^{-5}$), the required sample size $N$ typically scales as $1/\delta$. This leads to an explosion in computational complexity, making the problem intractable. This paper addresses this challenge specifically for heavy-tailed risk factors, where "black swan" events are more frequent than predicted by standard Gaussian models.

Methodology: Efficient Scenario Generation (Eff-Sc)

The authors introduce Efficient Scenario Generation (Eff-Sc), a method that leverages the predictable geometry of heavy-tailed distributions as the risk level $\delta$ approaches zero. Instead of sampling from the entire distribution, the algorithm focuses on a subset of scenarios that are most likely to cause violations.

The method relies on two primary geometric constructions:

  1. The Outer Approximation Set ($O_\delta$): A region in the decision space guaranteed to contain the true feasible region.
  2. The Uniform Conditional Event ($C_\delta$): A "super set" in the risk-factor space that encompasses all possible violation events for any decision within $O_\delta$.

By sampling risk factors conditioned on falling into $C_\delta$, the algorithm achieves uniform complexity, meaning the required number of samples $N$ becomes independent of $\delta$. The paper details two construction techniques:

  • The Scaling Method: Utilizes the scale-free property (multivariate regular variation) of heavy-tailed distributions to track the feasible region's movement as $\delta$ decreases.
  • The Linear Approximation Method: A simplified version for jointly convex constraint functions, using piecewise linear boundaries to bound the risk.

Experimental Evaluation

The Eff-Sc method was evaluated using two primary simulation models based on real-world challenges:

  • Portfolio Optimization: A 10-asset model with Value-at-Risk (VaR) constraints and Pareto-distributed losses.
  • Minimal Salvage Fund: An insurance network model (Eisenberg-Noe) aimed at determining the minimum emergency fund required to prevent systemic default across 10 to 20 entities.

Key Results

The experiments demonstrated significant improvements over the standard scenario approach:

  • Sample Efficiency: In the salvage fund experiment with $\delta = 10^{-3}$, the standard approach required over 200,000 samples, while Eff-Sc required only 2,000 samples.
  • Computational Speed: While the CPU time for standard methods increased exponentially as $\delta$ decreased, the Eff-Sc method's complexity remained nearly constant.
  • Solution Quality: In portfolio tests, Eff-Sc consistently yielded better objective values (e.g., higher mean returns) than the standard approach while maintaining the required safety margins.

Discussion and Conclusion

The core insight of this work is that for heavy-tailed distributions, the "danger zone" becomes predictable as risk tolerance $\delta$ approaches zero. This allows for a synergy between rare-event simulation and optimization, where sampling is targeted rather than exhaustive.

While the current framework assumes multivariate regular variation and specific function structures, it provides a powerful template for high-reliability optimization in heavy-tailed environments. Future research may extend these "uniform complexity" results to light-tailed distributions using alternative rare-event techniques such as exponential tilting.

Summary updated

Abstract

We consider a generic class of chance-constrained optimization problems with heavy-tailed (i.e., power-law type) risk factors. As the most popular generic method for solving chance constrained optimization, the scenario approach generates sampled optimization problem as a precise approximation with provable reliability, but the computational complexity becomes intractable when the risk tolerance parameter is small. To reduce the complexity, we sample the risk factors from a conditional distribution given that the risk factors are in an analytically tractable event that encompasses all the plausible events of constraints violation. Our approximation is proven to have optimal value within a constant factor to the optimal value of the original chance constraint problem with high probability, uniformly in the risk tolerance parameter. To the best of our knowledge, our result is the first uniform performance guarantee of this type. We additionally demonstrate the efficiency of our algorithm in the context of solvency in portfolio optimization and insurance networks. Funding: The research of B. Zwart is supported by the NWO (Dutch Research Council) [Grant 639.033.413]. The research of J. Blanchet is supported by the Air Force Office of Scientific Research [Award FA9550-20-1-0397], the National Science Foundation [Grants 1820942, 1838576, 1915967, and 2118199], Defense Advanced Research Projects Agency [Award N660011824028], and China Merchants Bank.
BibTeX
@inproceedings{blanchet2020efficient,
  author = {José Blanchet and Fan Zhang and Bert Zwart},
  title = {{Efficient Scenario Generation for Heavy-Tailed Chance Constrained Optimization}},
  booktitle = {Stochastic},
  year = {2020},
}
Figure