= L1 exact penalty
{title2=$f(x)+\rho\|c(x)\|_1$}
An L1 penalty can enforce a constraint exactly at a finite weight, rather than only in an infinite-weight limit. For a convex equality-constrained problem with an optimal multiplier $y_*$ and <optimization Lagrangian> $f-y^Tc$, the lower bound $f(x)-y_*^Tc(x)\geq f(x_*)$ gives
$$
f(x)+\rho\|c(x)\|_1\geq f(x_*)+(\rho-\|y_*\|_\infty)\|c(x)\|_1.
$$
Thus $\rho>\|y_*\|_\infty$ makes every penalty minimizer feasible and optimal. Local versions require appropriate regularity and second-order assumptions. The nonsquared norm is essential to this finite-threshold property; a <quadratic penalty method> usually approaches feasibility only as its weight diverges.
Back to article page
