Box, Ellipsoidal, and Budgeted Uncertainty Sets

In robust optimization we protect against the worst case over an uncertainty set $\mathcal{U}$. The shape of $\mathcal{U}$ controls both how much protection we get and how tractable the resulting problem is. Three standard choices are the box, ellipsoidal, and budgeted uncertainty sets.

The box uncertainty set treats each component of the uncertain vector independently, allowing each one to vary within its own interval:

$$\mathcal{U}_{\text{box}} = \{u \in \mathbb{R}^n \,:\, |u_i - \bar{u}_i| \le \hat{u}_i \text{ for all } i = 1, \ldots, n\},$$

where $\bar{u}$ is the nominal value and $\hat{u}_i \ge 0$ is the half-width along coordinate $i$.

For a linear objective $f(u) = c^\top u$, the worst case over the box is

$$\max_{u \in \mathcal{U}_{\text{box}}} c^\top u \;=\; c^\top \bar{u} \;+\; \sum_{i=1}^n |c_i|\, \hat{u}_i.$$

The maximum is achieved at the corner where $u_i = \bar{u}_i + \hat{u}_i$ when $c_i \ge 0$ and $u_i = \bar{u}_i - \hat{u}_i$ when $c_i < 0$ — every component swings to its worst extreme at once.

For example, with $c = (2,\, -3,\, 1)^\top$, $\bar{u} = (1,\, 1,\, 1)^\top$, and $\hat{u} = (0.5,\, 1,\, 2)^\top$:

$$c^\top \bar{u} + \sum_i |c_i|\hat{u}_i = (2 - 3 + 1) + (2)(0.5) + (3)(1) + (1)(2) = 0 + 1 + 3 + 2 = 6.$$