Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 38 / 1 / b / Solution

Let the finite primal supremum be $v$. First it is attained. The setis a finitely generated cone, hence closed by the argument in the root Solution. For a sequence of primal feasible points whose values approach $v$, the pairs $(b,c^{T}x)$ belong to $K$. Their limit $(b,v)$ therefore belongs to $K$. It gives a feasible point $x_{\ast }$ with $c^T{x}_{\ast }\ge v$, so necessarily $c^T{x}_{\ast }=v$.

Let $I$ index the tight primal inequalities at $x_{\ast }$ and let $Z$ index its zero coordinates. Consider the closed convex cone generated by $A_i^T$ for $i\in I$ and $-e_j$ for $j\in Z$. If $c$ were outside this cone, separation from a closed convex cone would give a direction $d$ withFor sufficiently small positive $\delta$, $x_{\ast }+\delta d$ remains a feasible point: the active constraints have the required signs, and every inactive constraint retains its positive slack. Its larger objective contradicts optimality. Therefore there are $y_i\ge 0$, supported on $I$, and ${\mu }_j\ge 0$, supported on $Z$, such thatThis makes $y$ a dual feasible point. Moreover, the support restrictions giveTogether with weak duality, this proves strong duality and dual attainment: