Overfitting in Adaptive Robust Optimization
Karl Zhu, Dimitris Bertsimas · 2025
Read Overfitting in Adaptive Robust Optimization by Karl Zhu, Dimitris Bertsimas (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-16451.txt.
Introduction
Robust plans that adapt as uncertainty unfolds beat static plans inside the guessed range, but they can break badly just outside it. Karl Zhu and Dimitris Bertsimas liken this brittleness to overfitting in machine learning: the adaptive parts lean too hard on the assumed range. Their fix sizes the safety range per constraint, with tougher guarantees for the constraints that hurt most when breached.
Read as regularization, the tighter guarantees shrink risky adaptive moves while looser ones keep useful freedom. The view gives a principled way to design uncertainty sets that balance toughness with flexibility.
Catalog record
| CREATOR | Karl Zhu, Dimitris Bertsimas |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 16 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-16451
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Overfitting in Adaptive Robust Optimization Karl Zhu, Dimitris Bertsimas Abstract Adaptive robust optimization (ARO) extends static robust optimization by allowing decisions to depend on the realized uncertainty — weakly dominating static solutions within the modeled uncertainty set. However, ARO makes previous constraints that were independent of uncertainty now dependent, making it vulnerable to additional infeasibilities when realizations fall outside the uncertainty set. This phenomenon of adaptive policies being brittle is analogous to overfitting in machine learning. To mitigate against this, we propose assigning constraint-specific uncertainty set sizes, with harder constraints given stronger probabilistic guarantees. Interpreted through the overfitting lens, this acts as regularization: tighter guarantees shrink adaptive coefficients to ensure stability, while looser ones preserve useful flexibility. This view motivates a principled approach to designing uncertainty sets that balances robustness and adaptivity. \workshoptitle Overfitting in Adaptive Robust Optimization 1 Introduction Robust optimization (RO) is one of the main frameworks (along with stochastic programming) for decision-making under uncertainty. RO produces a robust solution by requiring feasibility across all realizations within a specified uncertainty set \mathcal{U} . In this paper, we consider a robust linear optimization problem with m robust constraints and uncertainty on the right-hand side (RHS): \displaystyle\max_{\boldsymbol{x}\in\mathbb{R}^{n}}\quad \displaystyle\boldsymbol{c}^{\top}\boldsymbol{x} s.t. \displaystyle\boldsymbol{a}_{i}^{\top}\boldsymbol{x}\leq b_{i}+\boldsymbol{d}_{i}^{\top}\boldsymbol{u},\quad\forall\boldsymbol{u}\in\mathcal{U},\quad\forall i\in[m], \displaystyle\boldsymbol{x}\geq\boldsymbol{0}, where for parameters we have \boldsymbol{c}\in\mathbb{R}^{n} , and for each constraint i , we have \boldsymbol{a}_{i}\in\mathbb{R}^{n},b_{i}\in\mathbb{R},\boldsymbol{d}_{i}\in\mathbb{R}^{p} . Finally, we have the perturbation parameter \boldsymbol{u}\in\mathbb{R}^{p} which is uncertain but assumed to lie within \mathcal{U} . Here, \boldsymbol{x} is fixed before u is realized, yielding a static robust solution. Adaptive robust optimization (ARO) extends this framework by allowing some decisions to adjust after observing \boldsymbol{u} ben-tal_adjustable_2004 . A common tractable restriction is to use affine decision rules \boldsymbol{x}(\boldsymbol{u})=\boldsymbol{z}+V\boldsymbol{u} (1) with decision variables \boldsymbol{z}\in\mathbb{R}^{n} and V\in\mathbb{R}^{n\times p} . Static solutions correspond to {V}=\boldsymbol{0} , so adaptive policies always weakly dominate static ones within the set. The size and geometry of \mathcal{U} are chosen to balance feasibility and optimality. Common choices include the box ( \ell_{\infty} norm) soyster_technical_1973 , ellipsoid ( \ell_{2} norm) ben-tal_robust_1999 , and budget sets (intersection of \ell_{\infty} and \ell_{1} norms) bertsimas_price_2004 . A well-chosen uncertainty set should not contain all possible realizations of \boldsymbol{u} , as this would be overly conservative. Therefore, when evaluating solutions in simulation, one should not draw samples directly from the uncertainty set, but rather from an underlying distribution. A key, under-discussed drawback of ARO is that constraints that were originally independent of uncertainty become dependent. While static robust solutions often remain feasible outside the modeled set, adaptive policies may fail catastrophically—for example, violating variable non-negativity constraints. In this sense, adaptive policies are brittle : they achieve superior performance within \mathcal{U} but generalize poorly beyond it. This brittleness is directly analogous to overfitting in machine learning, where models with higher flexibility fit training data well but perform poorly out-of-sample. This perspective motivates a rethinking of how uncertainty sets are specified in ARO. Not all constraints are equally critical: hard constraints demand stronger guarantees, while softer constraints may tolerate limited violations. Interpreted through the overfitting lens, this leads to a regularization view : tighter guarantees shrink adaptive coefficients to improve stability, while looser guarantees preserve flexibility. Although the equivalence of robustness and regularization has been studied extensively xu_robustness_nodate , bertsimas_characterization_2018 , to our knowledge, there have been no similar discussions of this insight for ARO. In this note we illustrate brittleness using a renewable generation toy example, propose constraint-dependent uncertainty set sizes as a principled remedy for this brittleness, and show how robust counterparts (RC) impose regularization on adaptive coefficients. 2 Brittleness of Adaptive Policies We illustrate brittleness with a toy model of production planning under renewables: \displaystyle\max_{x,s}\quad \displaystyle x_{1}+x_{2}+y_{1}+y_{2}-100s_{1}-100s_{2} s.t. \displaystyle x_{1}+y_{1}-s_{1}\leq 2+u_{1},\quad\forall(u_{1},u_{2})\in\mathcal{U}, \displaystyle x_{2}+y_{2}-s_{2}\leq 2+u_{2},\quad\forall(u_{1},u_{2})\in\mathcal{U}, \displaystyle x_{1},x_{2},y_{1},y_{2},s_{1},s_{2}\geq 0. Here a forecast of 2 units of renewable power is available in each period. Decisions x_{1},y_{1} allocate this supply in period 1, and x_{2},y_{2} in period 2. Shortfalls are covered by grid imports s_{1},s_{2} , which are costly and non-renewable. Uncertainty in renewable availability is represented by a budget uncertainty set \mathcal{U}=\{(u_{1},u_{2}):\|\boldsymbol{u}\|_{\infty}\leq\rho,\ \|\boldsymbol{u}\|_{1}\leq\Gamma\}. An optimal solution to the nominal problem (where \mathcal{U}=\{\boldsymbol{0}\} ) is x_{i}=y_{i}=1,\ s_{i}=0 for i=1,2 with an objective value of 4, but any shortfall in renewables forces costly grid usage. An optimal solution to the static robust problem with (\rho,\Gamma)=(1,1) is x_{i}=1,y_{i}=s_{i}=0, for i=1,2 , with an objective value of 2. Notice that although the l_{1} ball that defines \mathcal{U} couples the uncertainties across constraints sets in \mathcal{U} , the static robust problem in general cannot exploit this coupling marandi_when_2018 , giving an overly conservative solution that is equivalent to the uncertainty set being a box \mathcal{U}=\{(u_{1},u_{2}):\|\boldsymbol{u}\|_{\infty}\leq\rho\}. In contrast, ARO is able to exploit this coupling bertsimas_benefit_2024 . Suppose we introduce a restricted affine decision rules that made the flows adapt to the current period of uncertainty: x_{i}(u_{i})=z^{x}_{i}+V^{x}_{i,i}u_{i},\quad y_{i}(u_{i})=z^{y}_{i}+V^{y}_{i,i}u_{i},\quad i=1,2. An optimal adaptive policy with (\rho,\Gamma)=(1,1) is x_{i}(u_{i})=1,\ y_{i}(u_{i})=1+u_{i} , for i=1,2 with an objective value of 3 – significantly outperforming the static policy within \mathcal{U} . However, the adaptive policy is brittle: the non-negativity constraints, originally independent of u , now depend on u and may be violated. For instance, if u_{1}<-1 , then y_{1}(u_{1})<0 , which is physically infeasible. Shortages can be met with imports, but negative flows cannot be implemented. A natural remedy is to assign larger uncertainty radii to hard constraints (e.g., non-negativity) and smaller ones to softer constraints (e.g., grid imports). For example, with (\rho,\Gamma)=(2,2) on the non-negativity constraints only, an optimal adaptive solution is x_{i}=y_{i}=1+\tfrac{1}{2}u_{i} , for i=1,2 and maintains an objective value of 3 and remains feasible for all u\geq-2 . In our example, only a non-negative RHS of renewable supply makes sense, so u_{1},u_{2} naturally both have a lower bound of -2 . So the enlarged set recovers the guaranteed feasibility previously enjoyed by the static policy while retaining the benefits from ARO and uncertainty coupling. 3 Probabilistic and Deterministic Guarantees From the toy example we saw that a uniform uncertainty set \mathcal{U} is not appropriate in ARO, since many constraints that were previously independent of uncertainty become dependent once adaptivity is introduced. This motivates the use of constraint-specific uncertainty sets \mathcal{U}_{i} for each constraint i\in[m] , sized according to its criticality. We distinguish two types: • Hard constraints (e.g. flow non-negativity): must be satisfied in all realizations. These require deterministic guarantees, with uncertainty sets that fully cover the support of \boldsymbol{u} . • Softer constraints (e.g., renewable allocations with non-renewable grid imports): can tolerate limited violations if backup resources exist. For these, probabilistic guarantees are appropriate, where ellipsoidal or budget sets provide explicit confidence levels while preserving adaptive flexibility. We now provide quantitative prescriptions. First, we recall probabilistic guarantees under Gaussian and distribution-free assumptions from the RO literature bertsimas_probabilistic_2021 , suited for softer constraints. Then, we present deterministic robust counterparts for bounded and semi-bounded supports, which are appropriate for hard constraints that must hold almost surely. Probabilistic guarantees. For each constraint i\in[m] , we may require \mathbb{P}\!\left[\boldsymbol{a}_{i}^{\top}\boldsymbol{x}(\boldsymbol{u})\;\leq\;b_{i}+\boldsymbol{d}_{i}^{\top}\boldsymbol{u}\right]\ \geq\ 1-\epsilon. (2) Different uncertainty sets \mathcal{U}_{i} provide different sufficient conditions for ( 2 ). • Gaussian case. If \boldsymbol{u}\sim\mathcal{N}(\boldsymbol{\mu},\Sigma) and \boldsymbol{x}(\boldsymbol{u})=\boldsymbol{z}+V\boldsymbol{u} , then ( 2 ) holds iff \boldsymbol{a}_{i}^{\top}\boldsymbol{z}+(V^{\top}\boldsymbol{a}_{i}-\boldsymbol{d}_{i})^{\top}\boldsymbol{\mu}+\rho_{1-\epsilon}\,\bigl\|\Sigma^{1/2}(V^{\top}\boldsymbol{a}_{i}-\boldsymbol{d}_{i})\bigr\|_{2}\;\leq\;b_{i}, where \rho_{1-\epsilon} is the (1-\epsilon) -quantile of the standard normal. Equivalently, this is the RC