Robustness certificates in data-driven non-convex optimization with additively-uncertain constraints

Alexander Gallo, Massimiliano Zoggia, Alessandro Falsone, Maria Prandini, Simone Garatti

TL;DR

Certifying the robustness of non-convex optimization problems usually requires solving NP-hard problems repeatedly. This paper introduces a "computational shortcut" for problems with additive uncertainty, providing rigorous robustness guarantees for any feasible solution—even sub-optimal ones—with almost zero extra overhead.

What Problem Does This Paper Address?

In data-driven decision-making, we often use the scenario approach: we collect $N$ samples (scenarios) of uncertainty and ensure our decision satisfies constraints for all of them. The goal is to guarantee that the decision will also work for future, unseen scenarios with high probability.

For convex problems, this theory is well-established. However, many real-world tasks (like scheduling power plants) are non-convex and involve discrete variables. For these problems, standard scenario theory faces two major hurdles:

  1. A priori guarantees (knowing how much data you need before you start) are often too conservative or non-existent.
  2. A posteriori guarantees (checking the risk after you have a solution) require identifying "support scenarios"—the specific data points that define the feasibility boundary. In non-convex settings, finding these usually requires solving the original hard problem hundreds or thousands of times, which is computationally prohibitive.

Methods

The authors exploit a specific but common structure: additively-uncertain constraints. These are constraints of the form $g(x) \le b(\delta_i)$, where the decision $x$ and the uncertainty $\delta$ are separated.

The key technical contribution is proving that the risk of a non-convex problem with this structure is upper-bounded by a much simpler convex proxy problem.

  • The Proxy: They construct a simple linear program that only cares about the "worst-case" values of the uncertainty across the dataset.
  • The Certificate: Because the proxy is convex and simple, its "complexity" (the number of support scenarios) is easy to find—it's just the number of unique scenarios that achieve the minimum value of $b(\delta)$ for each constraint component.
  • Sub-optimality: Unlike standard theory that often requires the global optimum, these certificates hold for any feasible solution. This is vital for non-convex optimization where solvers often settle for local optima or "good enough" feasible points.

Datasets

The researchers evaluated their approach on a Unit Commitment (UC) problem—the task of deciding which power generators to turn on/off to meet demand at minimum cost.

  • Source: Real-world hourly aggregate load demand data from the Spanish transmission system operator (Red Eléctrica).
  • Scope: Weekday demand profiles from January 1, 2014, to December 31, 2024 (2,870 days).
  • Usage: The data was split to provide training scenarios and a separate set for Monte-Carlo validation of the actual risk.

Key Insights and Ideas

  • The "Envelope" Principle: In additive uncertainty, the feasibility region is entirely determined by the "inner envelope" of the noise samples. You don't need to know the global optimum of the non-convex cost function to know if a point is robust; you just need to know where that envelope lies.
  • Computational "Free Lunch": Calculating the robustness certificate using their method takes milliseconds, whereas the standard "greedy" algorithm for general non-convex problems takes hours.
  • Incremental Sizing: They adapted an incremental algorithm that grows the dataset size only as much as needed. Because their check is so fast, they can determine the required amount of data without solving the heavy non-convex problem at every step.

Key Results

The authors tested a UC problem with 480 variables (384 of which were binary).

  • Speedup: To compute a posterior robustness bound, the standard method took an average of 4 hours and 33 minutes. The proposed method took just 0.5 milliseconds.
  • Tightness: While the new bounds are technically "conservative" (since they are an upper bound), the experiments showed they were very close to the actual empirical risk. The gap between the "exact" non-convex complexity and the "proxy" complexity was minimal.
  • Data Savings: Using the incremental approach, they achieved a target risk level ($\epsilon = 0.1$) using significantly fewer scenarios (worst case of 376) compared to the 533 scenarios required by standard one-shot a priori formulas.

Limitations and Future Work

  • Structural Constraint: The method relies entirely on the additive nature of the uncertainty ($g(x) \le b(\delta)$). If the uncertainty is multiplicative or otherwise coupled with the decision variables (e.g., $g(x, \delta) \le 0$), this specific shortcut does not apply.
  • Conservativeness Gap: While small in the power grid example, the gap between the proxy risk and the true risk could potentially be larger in other applications.
  • Future Directions: The authors suggest exploring if similar "structural exploitation" can be applied to more complex constraint types or used to improve "wait-and-judge" scenario strategies.

Summary updated

Abstract

We consider decision-making problems that are formulated as non-convex optimization programs where uncertainty enters the constraints through an additive term, independent of the decision variables, and robustness is imposed using a finite data-set, according to the scenario robust optimization paradigm. By exploiting the structure of the constraints, we show that both a priori and a posteriori distribution-free probabilistic robustness certificates for a possibly sub-optimal solution to the resulting data-driven optimization problem can be obtained with minimal computational effort. Building on these results, we also discuss a one-shot and an incremental procedure to determine the size of the data-set so as to guarantee a user-chosen robustness level. Notably, both the a posteriori robustness assessment and incremental data-set sizing do not require to solve the non-convex scenario program. A comparative analysis performed on the unit commitment problem using real data reveals a limited increase in conservativeness with a significant computational saving with respect to the application of scenario theory results for general, non necessarily structured, non-convex problems.
BibTeX
@misc{gallo2026robustness,
  author = {Alexander Gallo and Massimiliano Zoggia and Alessandro Falsone and Maria Prandini and Simone Garatti},
  title = {{Robustness certificates in data-driven non-convex optimization with additively-uncertain constraints}},
  year = {2026},
  eprint = {2602.21090},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.21090},
}
Figure