= Support function of an inverse image of an infinity-norm ball
{title2=$\sigma_C(x)=\min_{P^Tq=x}\|q\|_1,\quad C=\{z:\|Pz\|_\infty\le1\}$}
If $x\notin\operatorname{range}P^T=(\ker P)^\perp$, the <support function> is infinite along a kernel line. Otherwise <linear programming duality> gives the displayed minimum, attained because the corresponding linear programs are feasible with finite values. Splitting $q=\alpha-\beta$ into nonnegative parts yields the equivalent minimum of $\mathbf1^T(\alpha+\beta)$. Thus worst-case revenue over a <polyhedral uncertainty set> is $r_0^Tx-\sigma_C(x)$, with value $-\infty$ off the row space.
Back to article page
