Robust Optimization

Robust optimization addresses settings where the probability distribution of uncertain parameters is unknown or unreliable, by assuming the parameters can take any value within an uncertainty set U and seeking a solution that remains feasible under the worst case. The first formulation, due to Soyster (1973), uses a box uncertainty set and produces highly conservative solutions. Ben-Tal and Nemirovski (1998, 1999, 2000) introduced ellipsoidal uncertainty sets, which balance conservatism and performance and reduce to second-order cone programs (SOCP). Bertsimas and Sim (2003, 2004) proposed budgeted uncertainty, in which at most Γ parameters per constraint simultaneously attain their worst values; the resulting model is an LP of the same size as the nominal LP and is the most widely deployed variant in practice. Adjustable robust optimization (Ben-Tal Goryashko Guslitzer Nemirovski 2004) lets second-stage decisions adapt to the realised uncertainty, commonly via affine decision rules. Distributionally robust optimization (DRO) optimizes the worst-case expectation over a family of distributions, bridging stochastic and robust paradigms. Compared with stochastic programming, robust optimization needs no distribution information, but tends to be more conservative. References: Ben-Tal El Ghaoui Nemirovski (2009), Bertsimas Brown Caramanis (2011).