Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 339 / 1

A feasible point lies in the probability simplex, so $r^{T}x={\sum }_i{x}_i{r}_i$ is a convex combination of the coordinates of $r$. Hence $r^{T}x\le r_{\max }:={\max }_i{r}_i$. Taking a coordinate vector $e_j$ with $r_j=r_{\max }$ attains equality. ThereforeMore generally, all optimal solutions are exactly the probability vectors supported on the maximizing indices: equality requires $x_i(r_{\max }-r_i)=0$ for every $i$. Thus ties give an entire optimal face, while a unique maximizing index gives a unique optimizer.

For fixed $x$, put $z=r-r_0$. The polyhedral uncertainty set is equivalent to $-1\le Pz\le 1$, so the inner problem is the linear programThe variable $z$ is unrestricted in sign. The point $z=0$ is strictly feasible. If the optimum is finite, it is attained, so the infimum is a minimum. The use of an infimum also covers possible unbounded cases permitted by the printed assumptions; strict feasibility alone does not guarantee a finite objective.

Associate nonnegative Lagrange multipliers $\alpha$ with $-Pz-1\le 0$ and $\beta$ with $Pz-1\le 0$. The Lagrangian dual problem is obtained fromIts infimum over unrestricted $z$ is finite exactly when $P^T(\alpha -\beta )=x$. Thus the dual isThe precise finiteness condition is $x\in \mathrm{range}{P}^T$. If $x=P^{T}q$, then $x^{T}z=q^{T}Pz\ge -\Vert q{\Vert }_1$ on the feasible set. The primal is feasible and bounded below, and splitting $q$ into positive and negative parts makes the dual feasible. Linear programming duality therefore gives attained equal finite optima. Equivalently, the strictly feasible point $z=0$ satisfies the Slater condition, with the required finiteness hypothesis. This is strong duality in the usual finite sense.

If $x\notin \mathrm{range}{P}^T=(\ker P{)}^{\perp }$, there is $d\in \ker P$ with $x^{T}d<0$. Every $z=td$, $t\ge 0$, is feasible and the objective tends to $-\infty$. The dual is then infeasible. Equality of extended values still holds if its supremum over the empty feasible set is defined as $-\infty$, but there are no finite optimizers. The paper does not assume full column rank of $P$, so this qualification is necessary. The same calculation gives the support function of an inverse image of an infinity-norm ball, ${\inf }_r{r}^{T}x=r_0^{T}x-{\min }_{P^{T}q=x}\Vert q{\Vert }_1$ for finite decisions.

For every decision with finite worst-case value, the previous dual represents that value as a maximum over $\alpha ,\beta$. Maximizing it jointly with $x$ yields the robust linear optimization over the probability simplex formulation:Indeed every feasible triple gives a dual lower bound on that decision's worst-case revenue, while dual attainment supplies a triple reaching it. This argument only combines two maximizations after dualization; it does not interchange the original max and min.

If the probability simplex intersects $\mathrm{range}{P}^T$, this linear program is feasible and bounded above by ${\max }_i(r_0{)}_i$, and hence attains an optimum. Its maximizing $x$ is a robust optimizer. If the intersection is empty, every decision has worst-case value $-\infty$ and the linear program is infeasible, consistently with the extended-value convention. Full column rank of $P$ ensures every simplex decision has a finite inner optimum, but is not needed for the qualified equivalence.