Data-Driven Robust Optimization

Dimitris Bertsimas; Vishal Gupta; Nathan Kallus

Source-linked AI summary

Data-Driven Robust Optimization

Dimitris Bertsimas, Vishal Gupta, Nathan Kallus

arXiv:1401.0212v2Dec 31, 2013math.OC

TL;DR

Robust optimization needs uncertainty sets that avoid excessive conservatism and computational intractability as data become increasingly available. The paper proposes a hypothesis-test-based schema for constructing data-driven sets, whose models retain robustness guarantees while being less conservative than conventional approaches.

Problem
Poorly chosen uncertainty sets can make robust models overly conservative or computationally intractable, making the choice of a good set crucial.
Method
The paper proposes a general schema for designing robust-optimization uncertainty sets from data using statistical hypothesis tests.
Results
Data-driven sets imply a probabilistic guarantee, are typically smaller than corresponding data-poor variants, and yield models that are less conservative than conventional robust approaches while retaining the same robustness guarantees.
Takeaways & Limitations
The approach provides a flexible, broadly applicable way to use available data in robust optimization while preserving robustness guarantees.
Takeaways & Limitations
Gaussian tests that lack robustness will likely yield poor performance.

Abstract

from arXiv · show

The last decade witnessed an explosion in the availability of data for operations research applications. Motivated by this growing availability, we propose a novel schema for utilizing data to design uncertainty sets for robust optimization using statistical hypothesis tests. The approach is flexible and widely applicable, and robust optimization problems built from our new sets are computationally tractable, both theoretically and practically. Furthermore, optimal solutions to these problems enjoy a strong, finite-sample probabilistic guarantee. \edit{We describe concrete procedures for choosing an appropriate set for a given application and applying our approach to multiple uncertain constraints. Computational evidence in portfolio management and queuing confirm that our data-driven sets significantly outperform traditional robust optimization techniques whenever data is available.

1. Introduction

The paper develops a data-driven schema for constructing uncertainty sets for robust optimization from statistical hypothesis tests. It establishes probabilistic guarantees and tractable formulations while addressing set selection, multiple uncertain constraints, and practical performance.

Schema and guarantees: Data-driven uncertainty sets combine samples with structural assumptions about the unknown distribution P∗ and can be substantially smaller than traditional counterparts while retaining probabilistic guarantees.The data are assumed i.i.d. from P∗, and the resulting robust models can be less conservative.
Schema and guarantees: The schema uses confidence regions from statistical hypothesis tests to quantify uncertainty and encompasses sets with different geometric shapes, computational properties, and modeling power.The proposed sets can represent skewness, heavy-tails, and correlations.
Unifying perspective: The hypothesis-testing perspective unifies several existing data-driven methods and motivates statistical refinements, including bootstrap-based improvements to numerical performance.The framework is also presented as a way to compare and contrast different approaches and extend the schema to other methods.
Set construction: The authors construct multiple convex uncertainty sets with explicit descriptions, each applicable under different a priori assumptions about P∗.The considered pairings are selected for practical relevance and tractable resulting sets, but the list is non-exhaustive.
Computational tractability: Robust optimization over the proposed sets is generally tractable, with polynomial-time reformulations for a large class of functions and potential computational benefits from sparse constraints or cutting-plane methods.The paper states that off-the-shelf software can solve the reformulations and that cutting-plane methods may outperform reformulation-based approaches.
Extensions and practice: For multiple uncertain constraints, jointly optimizing individual set parameters yields tractable models whose solutions satisfy all constraints simultaneously at any desired level ϵ.The paper also provides practitioner guidelines for selecting sets and calibrating parameters using model-selection techniques.

2. Background

The paper reviews tractability results for robust nonlinear constraints and hypothesis-testing tools used to construct data-driven uncertainty sets. These tools provide confidence regions with finite-sample coverage, while bootstrap-based tests are only asymptotically valid.

The tractability analysis represents support-function epigraphs with convex inequalities that can be separated in polynomial time.This representation extends tractability beyond bi-affine functions to many other concave functions.
Robust constraints are tractable for each proposed set when f(u,x) is bi-affine.
Some formulations require exponential-cone constraints, which may be numerically challenging despite theoretical tractability.Cutting-plane or bundle methods are offered as alternatives when appropriate.
Hypothesis tests reject a null hypothesis when their statistic exceeds a threshold calibrated so incorrect rejection occurs with probability at most α.The two-sided Student’s t-test uses sample mean, sample standard deviation, and a Student t quantile; under Gaussianity, its rejection error is at most α.
Bootstrap thresholds are useful in practice for novel tests, but bootstrap-based hypothesis tests are strictly speaking valid only asymptotically for large N.The paper notes practical accuracy even for N as small as 100.
A confidence region contains null hypotheses not rejected by the test, and contains P∗ with probability at least 1 −α when the test assumptions hold.This converts hypothesis testing into a data-based set of distributions consistent with the test.

3. Designing Data-Driven Uncertainty Sets

The paper designs uncertainty sets by combining hypothesis-test confidence regions with convex upper bounds on worst-case risk measures. The resulting sets provide probabilistic guarantees, support multiple uncertain constraints, and can be substantially smaller than support-based alternatives as sample size grows.

The method exploits the dependence of f on u, allowing sets much smaller than the 1 −ϵ support while retaining a probabilistic guarantee.Such smaller sets are preferred because they are less conservative.
The schema constructs a convex, positively homogeneous upper bound and identifies a closed convex uncertainty set whose support function equals that bound.This set is then used in robust optimization.
With probability at least 1 −α over sampling, the constructed set implies a probabilistic guarantee at level ϵ for P∗.
For multiple uncertain constraints, the paper optimizes individual ϵj values subject to ∑j ϵj ≤ ϵ rather than fixing every ϵj to ϵ/m.Theorem 3 preserves the sampling guarantee when the family of sets is constructed simultaneously.
For finite-support distributions, Pearson’s χ2 and G-test constructions are respectively second-order-cone and exponential-cone representable.The exponential cone can nevertheless be numerically challenging.
As N increases, the data-driven sets shrink considerably and converge almost surely to U_CVaR P∗, whereas Campi–Garatti sets converge to supp(P∗).For small N, the proposed sets are equivalent to the convex hull of supp(P∗).

5. Independent Marginal Distributions

The paper constructs multivariate uncertainty sets by combining univariate goodness-of-fit tests for independent marginal distributions. These sets exploit distributional structure while retaining finite-sample probabilistic guarantees and tractable optimization procedures.

5. Independent Marginal Distributions: Independent marginal samples are combined into a valid multivariate hypothesis test and confidence region.The test rejects when any marginal KS test fails, with an adjusted level α′ = 1 − d√1 −α.
5. Independent Marginal Distributions: The KS-based confidence region uses empirical cdfs and contains distributions whose cdfs remain within the test’s acceptance band.For N = 100, the 80% KS confidence region is illustrated as a grey band around the empirical cdf.
5. Independent Marginal Distributions: The innermost worst-case optimization can be solved explicitly because the KS region’s extrema occur on its left or right boundaries.The active boundary depends on the sign of v_i, enabling convex optimization in λ and efficient line search.
5. Independent Marginal Distributions: With probability at least 1 − α, the constructed family {U I ϵ} implies a probabilistic guarantee for P∗ at level ϵ.The guarantee is established under independent components and the stated support conditions.
5. Independent Marginal Distributions: KS-based sets are computationally preferable to analogous EDF-test sets because they retain a simple violated-cut procedure.Other EDF alternatives remain polynomial-time separable but lack an equally simple algorithm for generating violated cuts; simulations found KS generally performs as well as or better.

6. Uncertainty Sets Built from Marginal Samples

Using samples from marginal distributions, the paper builds uncertainty sets from quantile information without assuming marginal independence. The resulting sets retain probabilistic guarantees under stated sample and quantile conditions, though their guarantee family depends on ϵ.

6. Uncertainty Sets Built from Marginal Samples: The marginal-sample construction observes separate samples from each marginal and does not assume those marginals are independent.The exposition assumes exactly N samples per marginal, while differing sample counts require additional notation.
6. Uncertainty Sets Built from Marginal Samples: The set U M ϵ is formed by bounding each component between empirical order statistics associated with the ϵ/d quantile.The construction uses a univariate quantile test and combines marginal tests by a union bound.
6. Uncertainty Sets Built from Marginal Samples: If N − s + 1 < s, then with probability at least 1 − α, U M ϵ implies a probabilistic guarantee for P∗ at level ϵ.The theorem also provides an additional optimization consequence for the constructed set.
6. Uncertainty Sets Built from Marginal Samples: The family {U M ϵ : 0 < ϵ < 1} may not simultaneously guarantee P∗ because its confidence region depends on ϵ.This is an explicit scope limitation of the family-level guarantee.
6. Uncertainty Sets Built from Marginal Samples: The resulting robust counterpart is a simple box represented by linear inequalities and separable in closed form.The box structure follows directly from the marginal bounds.

7. Uncertainty Sets for Potentially Non-independent Components

For potentially dependent components, the paper uses a goodness-of-fit test based on linear-convex functions to construct uncertainty sets from joint samples. The resulting sets have probabilistic guarantees and polynomial-time separation.

7. Uncertainty Sets for Potentially Non-independent Components: The construction observes samples from the joint distribution and applies a multivariate goodness-of-fit test based on linear-convex functions.The test uses statistics over affine functions with appropriate thresholds calibrated by bootstrap.
7. Uncertainty Sets for Potentially Non-independent Components: The uncertainty set U LCX ϵ is the confidence-region counterpart of this test and simultaneously implies a probabilistic guarantee for P∗.The theorem covers the family over 0 < ϵ < 1.
7. Uncertainty Sets for Potentially Non-independent Components: Separation over the linear-convex set is polynomial-time computable using auxiliary linear optimization problems.The routine identifies worst-case affine parameters across possible sign cases and generates a violated cut when needed.
7. Uncertainty Sets for Potentially Non-independent Components: The representation of δ∗(v| U LCX) is inconvenient, although separation remains polynomial-time and can be implemented with ellipsoid or dual-simplex methods.The dual-simplex approach is described as practically efficient for large-scale problems.

8. Hypothesis Testing: A Unifying Perspective

The paper presents hypothesis testing as a unifying perspective for data-driven uncertainty sets, linking containment guarantees to confidence regions and enabling improved calibration. Bootstrap thresholds can substantially shrink ambiguity and reduce potential over-conservatism while preserving probabilistic guarantees.

8. Hypothesis Testing: A Unifying Perspective: Families of measures containing P∗ with probability at least 1 − α correspond one-to-one with confidence regions of hypothesis tests.This correspondence provides a common statistical interpretation for several data-driven methods.
8. Hypothesis Testing: A Unifying Perspective: The hypothesis-testing perspective unifies comparisons across methods and brings practical statistical experience into uncertainty-set design.The paper uses this perspective to leverage bootstrap calibration and compare resulting approaches.
8.1. Uncertainty Set Motivated by Cristianini and Shawe-Taylor, 2003: Bootstrap thresholds for PCS are typically much smaller than concentration-based thresholds and remain approximately valid at level 1 − α.The paper reports that the reduction can be a full order of magnitude or more.
8.1. Uncertainty Set Motivated by Cristianini and Shawe-Taylor, 2003: Smaller bootstrapped thresholds shrink PCS, reducing ambiguity in P∗ and the potential over-conservatism of methods built from it.This includes the original machine-learning application and the paper’s own uncertainty-set construction.
8.1. Uncertainty Set Motivated by Cristianini and Shawe-Taylor, 2003: The resulting U CS ϵ family simultaneously implies a probabilistic guarantee for P∗, and its robust constraint is exactly equivalent to the corresponding ambiguous chance constraint.The equivalence uses the smaller bootstrapped thresholds.
8.2. Uncertainty Set Motivated by Delage and Ye, 2010: The paper’s comparison shows that U M does not learn marginal independence, whereas U LCX captures symmetry, skewness, and support more effectively in the example.In that example, U LCX is the smallest set by volume, while moment-based sets do not capture second-coordinate skewness.
8.2. Uncertainty Set Motivated by Delage and Ye, 2010: Gaussian tests lacking robustness may yield poor performance when their underlying distributional assumptions are inappropriate.The paper explicitly identifies robustness to such departures as relevant to performance.

9. Optimizing over Multiple Constraints

The paper develops methods for optimizing uncertainty-set parameters across multiple constraints, combining semi-infinite optimization with iterative heuristics. The proposed procedure has non-increasing optimization values and finite convergence.

The approach combines semi-infinite optimization techniques with the data-driven uncertainty-set schema for multiple constraints.
The constraints δ*(v|U_ϵ) ≤ t are bi-convex in (v,t) and ϵ for 0 < ϵ < 1.
For fixed ϵ_j values, the heuristic solves the robust problem, optimizes the ϵ_j values for the resulting solution, and repeats.The iterations stop when a stopping criterion is met or no further improvement occurs.
A refinement solves a linear optimization problem to obtain the next iterates for ϵ_j using information from the overall optimization and other constraints.
The procedure ensures that the optimization value is non-increasing between iterations and is finitely convergent.

10. Choosing the “Right” Set and Tuning α, ϵ

The paper treats uncertainty-set selection and parameter tuning as application-dependent model-selection problems. It proposes hold-out and cross-validation procedures while identifying limitations affecting their guarantees and data usage.

Choosing an appropriate uncertainty set is non-trivial and depends on the application.
A hold-out procedure constructs candidate sets on training data, evaluates their robust solutions on independent hold-out data, and selects the best.
With probability at least 1 − α, the set selected using independent data correctly implies a probabilistic guarantee at level ϵ.
The hold-out procedure uses only half the data to calibrate the uncertainty set, which may be impractical when N is moderately large.
K-fold cross-validation may identify a good set, but the paper cannot prove that its selected set satisfies the appropriate guarantee.The numerical experiments use 5-fold cross-validation.
For α and ϵ without natural values, the paper recommends jointly selecting them from grids using hold-out data or cross-validation.

11. Applications

Applications in portfolio management and queueing show that the data-driven sets improve robust optimization performance and can exploit distributional structure. The experiments also examine set selection, multiple constraints, and finite-sample guarantees.

Applications: In portfolio management and queueing, the data-driven sets outperform traditional uncertainty sets, while their robust models perform as well as or better than other data-driven approaches.
Applications: Different sets learn features such as correlation structure and skewness, so the best set can depend on both the application and N.
Applications: Optimizing the ϵ_j values for multiple constraints can significantly improve performance.
Portfolio Management: In portfolio experiments, cross-validation identifies sets whose out-of-sample estimates are reasonably close to true performance, whereas in-sample objective values are loose bounds.
Portfolio Management: Set size alone cannot predict portfolio performance: one smaller set performs much worse out-of-sample, motivating cross-validation or similar selection methods.
Portfolio Management: The portfolio experiments show that distribution-sensitive sets learn asymmetry and hold slightly less of higher-indexed toxic assets, unlike moment-based sets.
Queueing Analysis: In queueing, the bounds improve with more data; the proposed bounds are significantly better with less data and exhibit less variability.
Queueing Analysis: The queueing analysis can simultaneously bound the entire waiting-time CDF for any n, whether transient or steady-state.

12. Conclusions

The paper adapts robust optimization to a data-centered paradigm by designing uncertainty sets from hypothesis tests. These sets retain probabilistic guarantees while typically being smaller and less conservative than conventional alternatives.

The paper proposes a schema for designing robust-optimization uncertainty sets from data using hypothesis tests.
The paper treats adapting traditional robust optimization techniques to the emerging data-centered paradigm as a first step.
The schema's sets imply probabilistic guarantees and are typically much smaller than corresponding data-poor variants.
Models built from these sets are less conservative than conventional robust approaches while retaining the same robustness guarantees.
When R is unknown, the authors describe an estimation procedure and prove a modified version of Theorem 11 with different constants.The simpler case where R is known is treated directly.

Appendices

The appendices establish probabilistic guarantees for data-driven uncertainty sets and derive tractable formulations for their support functions and worst-case risk measures. They also extend the construction across several distributional and structural settings.

Probabilistic guarantees: Robust feasibility implies a finite-sample probabilistic guarantee that the uncertain constraint is violated with probability at most ϵ.The proof separates the uncertainty set from the violating region and then applies continuity of probability.
Probabilistic guarantees: The uncertainty-set construction yields simultaneous probabilistic guarantees over a family of admissible ϵ values.The result follows by combining Theorem 2 with a union bound.
Tractable formulations: Worst-case expectations and support functions are reduced to linear, conic, or semidefinite optimization problems through duality.The appendix derives analytical inner maximizations, second-order cone representations, and semidefinite formulations for several uncertainty sets.
Tractable formulations: For monotonic functions, the relevant inner optimization can be solved at endpoint values of θ_i, producing the stated support-function expression.Following the proof backward also identifies an optimizer in the uncertainty set and validates the associated procedure.
Risk formulations: The appendix develops worst-case Value at Risk formulations for multiple uncertainty-set families, including KS- and moment-based constructions.These formulations use duality, variable elimination, and rescaling to obtain finite optimization descriptions.

EC.3. Optimizing ϵj’s for Multiple Constraints

The section presents an alternating heuristic for allocating violation probabilities across multiple uncertain constraints using shadow prices. It also reports queueing and set-size results illustrating the procedure’s practical behavior.

Computational evidence: N = 1,000 makes the non-bootstrapped set nearly as large as the full support, whereas bootstrapping with N = 100 produces a smaller set than the non-bootstrapped method with 50 times more points.The non-bootstrapped set shrinks slowly toward its infinite limit.
EC.3. Optimizing ϵ_j’s for Multiple Constraints: The heuristic updates each ϵ_j by solving a local linear optimization problem weighted by the constraint’s shadow price and sensitivity.The coefficient approximates the improvement from a small change in ϵ_j, while a norm constraint limits the step size.
EC.3. Optimizing ϵ_j’s for Multiple Constraints: The procedure preserves feasibility of the previous iterate and terminates when the objective value no longer makes significant progress.Lower bounds on the new ϵ_j values retain feasibility, making the original objective non-increasing.
Queueing results: The queueing analysis uses a KS test on busy-period customer counts to choose a truncation level that bounds the probability of exceeding it.The selected index supports truncating the queue recursion with probability at least 1 − α.
Queueing results: The queue empties every n̂(k) customers with at least the probability established by the KS-based bound.The bound is used to control the busy-period length in the queueing application.

EC.6. Constructing UI ϵ from Other EDF Tests

This section extends the uncertainty-set construction from the KS test to other empirical distribution function tests. The resulting sets retain probabilistic guarantees, while the KS test generally produces smaller sets and the alternatives can be numerically harder to optimize.

Test extensions: The construction applies to K, CvM, W, and AD empirical distribution function tests through test-specific matrices, vectors, and cones.The theorem assumes g(u) is monotonic and right-continuous and uses the confidence region associated with the selected test.
Optimization structure: For monotonic g(u), an optimal solution assigns zero mass to the left or right auxiliary component according to whether g is non-decreasing or non-increasing.Specifically, q^L = 0 for non-decreasing g and q^R = 0 for non-increasing g.
Test comparison: The KS test yields smaller uncertainty sets than the K test because Γ_K ≥ Γ_KS for all N and α.The appendix therefore recommends preferring KS to K when choosing between those tests.
Guarantees: With probability at least 1 − α over the sample, the resulting family of uncertainty sets implies a probabilistic guarantee.The guarantee extends the earlier construction to the alternative EDF tests.
Computational considerations: Optimization remains polynomial-time for CvM, W, and AD tests but is more challenging numerically than the construction’s standard formulation.The alternative formulations use conic optimization with interior-point solvers.