= Solution
Let $\lambda^*$ be an optimal dual multiplier and define the maximum violation
$$
v(x)=\max\{0,(Ax-b)_1,\ldots,(Ax-b)_m\}.
$$
Dual stationarity and <strong duality> imply, for every $x$,
$$
c^Tx+(\lambda^*)^T(Ax-b)
=-b^T\lambda^*=p^*.
$$
Since every component of $Ax-b$ is at most $v(x)$ and $\lambda^*\geq0$,
$$
(\lambda^*)^T(Ax-b)\leq
\lVert\lambda^*\rVert_1v(x).
$$
It follows that the <exact maximum-violation penalty> obeys
$$
c^Tx+Mv(x)
\geq p^*+\bigl(M-\lVert\lambda^*\rVert_1\bigr)v(x).
$$
Choose any $M>\lVert\lambda^*\rVert_1$. A primal optimum has $v(x)=0$ and penalized value $p^*$, whereas every infeasible point has $v(x)>0$ and penalized value strictly greater than $p^*$. Thus the penalized problem and the original <linear program> have exactly the same minimizers.
Back to article page
