Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 339 / 1 / c / Solution

Let ${\lambda }^{\ast }$ be an optimal dual multiplier and define the maximum violationDual stationarity and strong duality imply, for every $x$,Since every component of $Ax-b$ is at most $v(x)$ and ${\lambda }^{\ast }\ge 0$,It follows that the exact maximum-violation penalty obeysChoose any $M>\Vert {\lambda }^{\ast }{\Vert }_1$. A primal optimum has $v(x)=0$ and penalized value $p^{\ast }$, whereas every infeasible point has $v(x)>0$ and penalized value strictly greater than $p^{\ast }$. Thus the penalized problem and the original linear program have exactly the same minimizers.