Robust Solutions of Optimization Problems Affected by Uncertain Probabilities

Aharon Ben-Tal, Dick den Hertog, Anja M.b. De Waegenaere, Bertrand Melenberg, Gijs RennenSSRN Electronic Journal 2011 · DOI

TL;DR

This paper introduces a statistically grounded framework for Robust Optimization (RO) when the uncertain parameters are probabilities. By using $\phi$-divergences (like Kullback-Leibler or chi-squared) to define uncertainty regions, the authors provide a data-driven approach that remains computationally tractable, often reducing to standard linear or conic quadratic programming.

What Problem Does This Paper Address?

In many real-world optimization problems—such as portfolio selection or inventory management—decisions depend on expectations of random variables. These expectations are calculated using probability distributions typically estimated from historical data. However, these estimates are never perfect. Small errors in the assumed probabilities can lead to solutions that perform poorly or violate constraints in practice.

Traditional Robust Optimization addresses parameter uncertainty by defining "uncertainty regions" and requiring the solution to be feasible for all parameters within that region. However, standard shapes like boxes or ellipsoids often lack a clear statistical meaning when applied to probability vectors. The challenge is to find uncertainty regions that are statistically significant, consistent with data, and yet simple enough to keep the resulting optimization problem solvable (tractable).

Methods

The authors propose using $\phi$-divergences to construct uncertainty regions. These are functional measures of "distance" between two probability distributions. Common examples include the Kullback-Leibler divergence, Hellinger distance, and chi-squared distance.

The key innovation is showing that if the uncertainty region is defined as a set of probability vectors within a certain $\phi$-divergence "distance" from an empirical estimate, the Robust Counterpart Problem (RCP) remains tractable. Specifically, they derive a general reformulation (Theorem 4.1) that transforms a robust linear constraint into a convex constraint involving the conjugate function of $\phi$.

They demonstrate that for most standard $\phi$-divergences, this reformulation leads to well-known, efficient optimization classes:

  • Linear Programming (LP) for variation distance.
  • Conic Quadratic Programming (CQP) for chi-squared, Hellinger, and Cressie-Read divergences.
  • Problems admitting self-concordant barriers (solvable via interior-point methods) for Kullback-Leibler and Burg entropy.

Datasets

The paper does not use a large-scale external dataset but evaluates the approach through a simulated multi-item newsvendor problem.

  • Setup: 12 items, each with 3 demand scenarios (low, medium, high).
  • Parameters: Revenue function values (prices, costs, salvage values) and sample-based probability estimates were predefined.
  • Evaluation: The authors sampled 10,000 "true" probability vectors to compare the performance of robust solutions versus non-robust ones across different sample sizes ($N = 10$ to $1000$).

Key Insights and Ideas

  • Statistical Meaning: $\phi$-divergence regions are not just arbitrary shapes; they correspond to asymptotic confidence regions for goodness-of-fit statistics. This allows decision-makers to set the "robustness" level based on a desired statistical confidence (e.g., 95%).
  • Information Processing: A powerful property of $\phi$-divergences is that they allow the incorporation of additional information (like a statistical model) to shrink the uncertainty region without reducing the confidence level.
  • Tractability of Complexity: While divergence measures might look mathematically daunting, the paper proves they often "collapse" into standard, easy-to-solve optimization problems.
  • Conjugate Functions: The use of Fenchel duality and conjugate functions is the mathematical bridge that makes these robust counterparts tractable.

Key Results

The paper provides a comprehensive "cheat sheet" mapping various $\phi$-divergences to their corresponding optimization classes and conjugate functions.

Table 2: Some $\phi$-divergence examples, with their conjugates and adjoints. The last column indicates the tractability of the robust counterpart.

In the newsvendor simulation, robust solutions significantly outperformed non-robust ones when data was scarce (small $N$). For the "maximize minimal profit" objective, the robust solution not only reduced risk but actually achieved a higher mean profit in simulations compared to the non-robust approach. The dispersion of outcomes was much tighter for robust solutions, effectively avoiding the substantial losses that plagued the non-robust baseline.

Limitations and Future Work

  • Asymptotic Reliance: The construction of confidence sets relies on asymptotic theory ($N \to \infty$). While "corrected" statistics are suggested for small samples, the approximations may still be loose in very data-poor regimes.
  • Non-linear Probabilities: The current framework primarily handles cases where the unknown probabilities appear linearly in the objective or constraints. Extending this to non-linear appearances (common in some complex risk measures) remains an open challenge.
  • Broader Statistics: Many goodness-of-fit statistics used in classical statistics do not fall into the $\phi$-divergence class; determining the tractability of robust counterparts for these other measures is a suggested direction for future research.

Summary updated

BibTeX
@misc{bental2011robust,
  author = {Aharon Ben-Tal and Dick den Hertog and Anja M.B. De Waegenaere and Bertrand Melenberg and Gijs Rennen},
  title = {{Robust Solutions of Optimization Problems Affected by Uncertain Probabilities}},
  year = {2011},
  doi = {10.2139/ssrn.1853428},
  howpublished = {SSRN Electronic Journal},
}
Figure