= Robust linear optimization over the probability simplex
Worst-case linear revenue over a <polyhedral uncertainty set> is optimized by the linear program
$$
\max_{x,\alpha,\beta}\ r_0^Tx-\mathbf1^T(\alpha+\beta),\qquad x\in\Delta_n,\quad\alpha,\beta\ge0,\quad P^T(\alpha-\beta)=x.
$$
Here $\Delta_n$ is the <probability simplex>. Finite decisions are exactly its intersection with $\operatorname{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.
Back to article page
