= Exact maximum-violation penalty
Consider minimizing $f(x)$ over a specified domain with inequalities $g_i(x)\le0$. Assume a primal minimizer exists and <strong duality> holds with an optimal nonnegative multiplier $\lambda^*$. Let $v(x)=\max(0,g_1(x),\ldots,g_m(x))$. For every $M>\|\lambda^*\|_1$, the <exact maximum-violation penalty>
$$
P_M(x)=f(x)+Mv(x)
$$
has the same minimum, and every penalized minimizer is feasible and primal optimal.
Indeed the optimal <Lagrange dual function> bound gives $f(x)+\sum_i\lambda_i^*g_i(x)\ge p^*$. Since $\sum_i\lambda_i^*g_i(x)\le\|\lambda^*\|_1v(x)$,
$$
P_M(x)\ge p^*+(M-\|\lambda^*\|_1)v(x).
$$
A primal optimizer has $v=0$ and reaches $p^*$. Any infeasible point has strictly larger penalized value, proving the claim. The strict multiplier margin and zero-gap hypotheses explain why existence of an arbitrary optimal dual vector alone is insufficient.
Back to article page
