Robust Optimization: Worst-Case over an Uncertainty Set

In stochastic programming, we minimize the expected cost under a known probability distribution over the uncertainty. Robust optimization takes a different stance: we make no probabilistic assumptions and instead protect against the worst case over a specified uncertainty set $U$.

Given a decision $x$, an uncertain parameter $u \in U$, and a cost function $f(x, u)$, the robust optimization problem is

$$\min_x \; \max_{u \in U} \; f(x, u).$$

The inner $\max$ computes the worst-case cost of decision $x$ across all $u \in U$. The outer $\min$ selects the decision whose worst-case cost is smallest. Like the here-and-now solution of a two-stage stochastic program, $x$ must be chosen before $u$ is revealed -- but here we hedge against the worst $u$ rather than the average $u$.

When $U = \{u_1, u_2, \ldots, u_K\}$ is a finite list of scenarios and we have candidate decisions $x^{(1)}, x^{(2)}, \ldots,$ we can find the robust optimum directly from a cost table. For example, with two candidates and three scenarios,

$$\begin{array}{c|ccc} & u_1 & u_2 & u_3 \\ \hline x^{(1)} & 8 & 12 & 6 \\ x^{(2)} & 10 & 9 & 11 \end{array}$$

the worst case for $x^{(1)}$ is $\max\{8, 12, 6\} = 12,$ and the worst case for $x^{(2)}$ is $\max\{10, 9, 11\} = 11.$ The robust optimum is $x^{(2)},$ with worst-case cost $11.$