Introduction
Real-world systems, ranging from autonomous vehicles to financial portfolios, must operate reliably under significant uncertainty. Chance-Constrained Programs (CCP) address this by ensuring constraints are met with a specified high probability. However, the true underlying distribution of uncertainty is often unknown, leading to the development of Distributionally Robust Optimization (DRO). DRO seeks solutions that remain valid across an "ambiguity set" of potential distributions.
While Wasserstein-based DRO has gained popularity, it faces two significant hurdles: limited tractability for complex, nonlinear constraints and the high computational cost of tuning the uncertainty set's radius. This work introduces MMD-DRCCP, a framework that utilizes Maximum Mean Discrepancy (MMD) to define ambiguity sets, enabling the handling of general nonlinear constraints and efficient hyperparameter tuning.
Problem Formulation
The core challenge is solving optimization problems where constraints $f(x, \xi) \le 0$ must hold with probability $1-\alpha$, where $\xi$ is an uncertain parameter. Traditional methods often struggle when $f$ is nonlinear or non-convex. MMD-DRCCP addresses this by defining a robust counterpart that considers all distributions within an MMD-based ball centered at the empirical distribution of observed data.
Methodology: The MMD-DRCCP Framework
The authors pivot to Maximum Mean Discrepancy (MMD), a kernel-based metric measuring distances between distributions in a Reproducing Kernel Hilbert Space (RKHS).
Kernel Reformulation and CVaR Approximation
By leveraging the "Robust Representer Theorem," the authors transform the infinite-dimensional DRO problem into a finite-dimensional optimization task compatible with standard solvers. To maintain tractability, they employ a Conditional Value-at-Risk (CVaR) approximation, which provides a convex upper bound on the chance constraint while preserving the original function's convexity relative to decision variables.
The MMD Bootstrap
A key innovation is the MMD Bootstrap method. Unlike Wasserstein methods that require expensive cross-validation to set the uncertainty radius $\epsilon$, MMD's closed-form estimator allows for a fast resampling approach. This method determines a "sharp" radius that ensures safety without being overly conservative, as illustrated by the distribution of MMD estimates.
Finite-Sample Guarantees
The framework provides a safety guarantee of $O(1/\sqrt{N})$, where $N$ is the number of samples. Crucially, this rate is independent of the dimensionality of the uncertainty, making the method highly effective for complex, high-dimensional systems.
Experimental Evaluation
The algorithm was evaluated on two benchmarks:
- Portfolio Optimization: In a 3-asset problem with nonlinear constraints, MMD-DRCCP maintained safety across various sample sizes, while non-robust baselines failed. The bootstrap method allowed for higher profits compared to standard mathematical bounds.
- Tube-based Model Predictive Control (MPC): The method successfully guided a system through a non-convex safety zone defined by an SVM classifier—a task beyond the reach of existing affine-constrained Wasserstein methods.
Conclusion
MMD-DRCCP offers a "one-size-fits-all" approach to robust optimization with nonlinear constraints. By breaking the curse of dimensionality and providing an efficient bootstrap mechanism for tuning, it represents a significant step forward in practical, safe optimization under uncertainty. Future work will address computational scaling for larger datasets and exploring optimality gaps.
Summary updated