Robust optimization

Robust optimization chooses a decision while accounting for every parameter in a prescribed uncertainty set. A worst-case maximization takes the form ${\sup }_x{\inf }_{r\in \mathcal{U}}F(x,r)$ with the decision chosen before the uncertain parameter. With affine dependence on the uncertainty, the support function and linear programming duality often replace the inner optimization by explicit constraints.

Worst-case linear revenue over a polyhedral uncertainty set is optimized by the linear programHere ${\Delta }_n$ is the probability simplex. Finite decisions are exactly its intersection with $\mathrm{range}{P}^T$. If this intersection is empty, all decisions have worst-case value $-\infty$ and the displayed linear program is infeasible; its supremum over the empty feasible set is also $-\infty$. Full column rank of $P$ suffices to make all simplex decisions finite.

A polyhedral uncertainty set is specified by finitely many linear inequalities. The displayed centered example is the inverse image of a box under a linear map. It is nonempty because it contains $r_0$, and contains every line $r_0+td$ with $d\in \ker P$. Consequently it need not be bounded when $P$ is rank deficient. Its supremum norm constraint is equivalent to $-1\le P(r-r_0)\le 1$.