= Solution
Let $u'$ be any constrained minimizer for $\sigma>0$ and let $\lambda^*$ be a dual optimum. Set the common optimal value to $p^*$. <Weak duality> and feasibility imply
$$
p^*=d(\lambda^*)\leq L(u',\lambda^*)
=\operatorname{TV}(u')+\lambda^*(r(u')-\sigma)\leq\operatorname{TV}(u')=p^*.
$$
All inequalities are therefore equalities. In particular, $u'$ minimizes $L(\cdot,\lambda^*)$, whose $-\lambda^*\sigma$ term is constant. Hence
$$
\boxed{u'\in\operatorname*{argmin}_u\{\operatorname{TV}(u)+\lambda^*\|u-g\|_2^2\},\qquad\lambda^*\geq0.}
$$
This proves the claim for every constrained minimizer, rather than just for the particular one used to establish a saddle point. The multiplier may be zero, and the penalized minimizer then need not be unique.
Conversely, for $\lambda>0$ the quadratic makes the penalized objective coercive and strictly convex, so it has a unique minimizer $u_\lambda$. Choose $\boxed{\sigma=\|u_\lambda-g\|_2^2}$. If a feasible $u$ had $\operatorname{TV}(u)<\operatorname{TV}(u_\lambda)$, then
$$
\operatorname{TV}(u)+\lambda r(u)
\leq\operatorname{TV}(u)+\lambda\sigma
<\operatorname{TV}(u_\lambda)+\lambda r(u_\lambda),
$$
contradicting penalized optimality. Thus $u_\lambda$ solves the constrained problem at that budget. This is <constrained-penalized equivalence for total variation denoising>. It is a correspondence of minimizers and suitable parameters, not a claim that every budget has a unique multiplier or a unique constrained minimizer.
Back to article page
