Robust Optimization — Worst-Case Mathematical Programming
Robust Optimization (Minimax Programming) · Also known as: minimax optimization, worst-case optimization, Gürbüz Optimizasyon (Robust Optimization)
Robust optimization is a mathematical programming framework, formalised by Ben-Tal and Nemirovski in the late 1990s and made broadly tractable by Bertsimas and Sim (2004), that finds decisions guaranteed to perform acceptably under every scenario within a predefined uncertainty set — rather than assuming parameter values are known exactly. Instead of optimising for a single expected outcome, it minimises the worst-case objective across all plausible realisations of uncertain data.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Robust optimisation is appropriate when parameter uncertainty is bounded but its distribution is unknown or unreliable, when worst-case guarantees are required (safety-critical or regulatory contexts), and when a single implementable decision is needed rather than a policy distribution as in stochastic programming. It works with continuous decision variables. There is no minimum sample-size requirement — the uncertainty set is defined analytically, not estimated from data. It is not suitable when uncertainty is unbounded, when a probability distribution for the uncertain parameters is available and accurate (use stochastic optimisation instead), or when fewer than approximately 1,000 scenario evaluations would be feasible for scenario-based validation.
Strengths & limitations
- Provides deterministic worst-case guarantees without requiring a probability distribution for uncertain parameters.
- Reformulations for convex uncertainty sets are often as tractable as the nominal problem — no additional computational explosion.
- The conservatism level is directly controllable via the size and shape of the uncertainty set, making the robustness-performance tradeoff explicit and transparent.
- Applicable across diverse domains — supply chain, finance, engineering design, energy systems — wherever bounded parameter uncertainty exists.
- The solution is necessarily more conservative than the nominal optimum; the price of robustness can be significant when the uncertainty set is large.
- Defining a realistic uncertainty set requires domain knowledge; an poorly chosen set may be either too conservative or fail to cover true perturbations.
- For non-convex problems or general mixed-integer programs, robust reformulations can be NP-hard and require specialised decomposition algorithms.
- Robust optimisation does not incorporate probability information; when a reliable distribution is available, stochastic programming may yield higher expected performance.
Frequently asked
How is robust optimisation different from stochastic programming?
Robust optimisation seeks a single decision that is feasible and near-optimal for every scenario in a bounded uncertainty set, without assuming any probability distribution over those scenarios. Stochastic programming uses a known (or estimated) probability distribution to optimise expected performance, typically producing a policy or recourse actions rather than one fixed solution. Choose robust optimisation when worst-case guarantees matter and no reliable distribution is available; choose stochastic programming when a good distribution is known and average performance is the primary criterion.
What is the price of robustness?
The price of robustness is the increase in objective value (for a minimisation problem) compared to the nominal optimal solution obtained without accounting for uncertainty. Bertsimas and Sim (2004) showed that for their budget-uncertainty formulation this price grows only as the square root of the number of uncertain parameters, making it modest in practice. Examining this gap after solving is essential: if it is very large, the uncertainty set is probably too conservative.
Which uncertainty set shape should I choose?
Box sets are the simplest and most conservative — each parameter varies independently. Ellipsoidal sets (Ben-Tal & Nemirovski) model correlated perturbations bounded in Euclidean norm and lead to second-order cone programs. Polyhedral / budget-constrained sets (Bertsimas & Sim) control the number of parameters that can deviate simultaneously, preserving linearity and reducing conservatism. Choose based on domain knowledge about how perturbations co-occur and which solver class is available.
Can robust optimisation handle integer decision variables?
Yes, but robust integer and mixed-integer programming is substantially harder. Robust counterparts of mixed-integer linear programs are often NP-hard in the worst case. Benders decomposition and column-and-constraint generation algorithms are standard approaches, but problem size and uncertainty-set complexity must be kept manageable.
Sources
- Ben-Tal, A., El Ghaoui, L. & Nemirovski, A. (2009). Robust Optimization. Princeton University Press. ISBN: 9780691143682
- Bertsimas, D. & Sim, M. (2004). The Price of Robustness. Operations Research, 52(1), 35-53. DOI: 10.1287/opre.1030.0065 ↗
How to cite this page
ScholarGate. (2026, June 1). Robust Optimization (Minimax Programming). ScholarGate. https://scholargate.app/en/optimization/robust-optimization
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Convex OptimizationOptimization↔ compare
- Evolutionary StrategyOptimization↔ compare
- Linear ProgrammingOptimization↔ compare
- Stochastic OptimizationOptimization↔ compare
- Surrogate-Based OptimizationOptimization↔ compare