Robust Optimization
Robust optimization guards against uncertain data by optimizing for the worst case within a defined uncertainty set, requiring no probability distribution.
Worst-case guarantees
Where stochastic programming needs a probability distribution over uncertain data, robust optimization needs only a set of possible data values, the uncertainty set. It seeks a decision that remains feasible and performs well for every data value in that set, optimizing against the worst case. This yields hard guarantees rather than expectations, which is what safety-critical and adversarial settings demand.
The robust counterpart
Take a constraint a^T x <= b where the coefficient vector a is uncertain, known only to lie in a set U. The robust version requires the constraint to hold for all a in U, which is equivalent to the single constraint max over a in U of (a^T x) <= b. Reformulating this inner maximization into explicit constraints produces the robust counterpart, a deterministic problem that can be solved directly.
Tractability depends on the set
The remarkable fact is that for well-chosen uncertainty sets the robust counterpart stays in a familiar, tractable class. A box (interval) uncertainty set keeps a linear program linear. An ellipsoidal uncertainty set turns a linear constraint into a second-order cone constraint, so the robust counterpart is an SOCP. A polyhedral set keeps it a linear program. This is why robust optimization is practical and not merely conservative.
- Box set: robust LP stays an LP, most conservative
- Ellipsoidal set: robust LP becomes an SOCP
- Budgeted (Bertsimas-Sim) set: control conservatism with a budget parameter
- Polyhedral set: robust counterpart via LP duality
The price of robustness
Protecting against every outcome in a large set costs performance in the typical case, a trade-off called the price of robustness. Budgeted uncertainty sets let a modeler dial conservatism by limiting how many coefficients may deviate at once, tuning the balance between safety and average performance. Robust optimization is the tool of choice when the uncertainty is bounded but its distribution is unknown or when constraint violations are unacceptable.