Distributionally robust polynomial chance-constraints under mixture ambiguity sets

Jean B. Lasserre, Tillmann WeißerMath. Program 2021 · DOI

Introduction

In the fields of optimization and control, managing uncertainty is a fundamental challenge. Traditional approaches typically fall into two categories: Robust Optimization, which assumes a worst-case scenario and often leads to overly conservative or "empty" feasible sets, and Chance-Constraints, which assume a specific probability distribution (e.g., Gaussian) to ensure constraints are met with a high probability. While the latter is less conservative, it is highly sensitive to distributional assumptions; if the true noise distribution deviates from the model, the system's safety is compromised.

Distributionally Robust Optimization (DRO) offers a middle ground. Instead of assuming a single fixed distribution, DRO considers an "ambiguity set"—a family of possible distributions. This paper advances DRO by focusing on mixture ambiguity sets, where the noise is modeled as a mixture of distributions (such as combinations of Gaussians with varying means and variances). The authors provide a mathematical framework to identify "safe" feasible regions under these complex uncertainty models, even when constraints are non-linear polynomials.

Methodology: The Moment-SOS Hierarchy

The core of the proposed method is the Moment-Sums-of-Squares (Moment-SOS) hierarchy. This technique translates complex, infinite-dimensional probability problems into a sequence of finite-dimensional Semidefinite Programs (SDPs) that can be solved numerically.

Inner Approximations and Safety

A primary goal for engineering applications is ensuring that any decision made is truly safe. The authors define a sequence of polynomials $w_d(x)$ such that the set where $w_d(x) < \varepsilon$ is guaranteed to be a subset of the true feasible set. This "inner approximation" ensures that the algorithm never overestimates the safety of a decision.

Dual LP Formulation and Stokes’ Theorem

The problem is initially framed as an infinite-dimensional Linear Program (LP). By solving its dual, the authors derive the coefficients for the approximating polynomials. A significant technical hurdle in polynomial approximation is the "Gibbs phenomenon," where polynomials struggle to approximate sharp transitions or boundaries. To mitigate this, the authors utilize Stokes’ Theorem to incorporate the analytical structure of the underlying distributions (e.g., Exponential or Gaussian) directly into the optimization process. This acceleration technique significantly improves the convergence rate of the approximations.

Numerical Evaluation

Since the paper focuses on theoretical optimization, the authors validated their framework using synthetic numerical experiments designed to test the limits of the hierarchy:

  1. Mixtures of Univariate Gaussians: The method was tested against noise where the mean and variance were only known to reside within a specific interval.
  2. Non-convex Feasible Sets: The framework was applied to complex, non-convex geometries, such as star-shaped or disconnected feasible regions, which are typically difficult for standard linear or ellipsoidal methods to capture.

Key Insights and Results

Volume Convergence

The authors provide a theoretical proof that as the degree of the polynomial $d$ increases, the gap between the inner approximation and the true feasible set shrinks to zero in terms of volume ($\lambda(X^*_\varepsilon \setminus X^d_\varepsilon) \to 0$). This ensures that the method is not only safe but also increasingly precise.

Efficiency and Performance

In a 2D non-convex test case, the SOS approach at degree $d=12$ captured approximately 74% of the feasible set in 482 seconds. In contrast, a high-fidelity Monte Carlo simulation required 8,600 seconds—nearly 18 times longer—to achieve comparable results, and notably, the Monte Carlo method provided no formal mathematical guarantee of safety.

Handling Joint Constraints

The research demonstrates that "joint" chance-constraints, where multiple conditions must be satisfied simultaneously, do not significantly increase the complexity of the framework compared to single constraints. This makes the approach viable for multi-objective optimization problems.

Conclusion and Future Directions

While the Moment-SOS hierarchy provides a rigorous and efficient way to handle mixture ambiguity sets, it faces the "curse of dimensionality." The size of the resulting SDPs grows rapidly with the number of variables and the polynomial degree, currently limiting the method to small-to-medium-sized problems (typically $n < 10$).

Future research will focus on exploiting sparsity patterns within the optimization problems. By identifying independent or weakly coupled variables, it may be possible to scale this distributionally robust framework to larger, more complex systems such as power grids or high-dimensional robotic controllers.

Summary updated

BibTeX
@article{lasserre2021distributionally,
  author = {Jean B. Lasserre and Tillmann Weißer},
  title = {{Distributionally robust polynomial chance-constraints under mixture ambiguity sets}},
  journal = {Math. Program.},
  year = {2021},
  doi = {10.1007/s10107-019-01434-8},
}
Figure