 Solution

Let $u^{\prime }$ be any constrained minimizer for $\sigma >0$ and let ${\lambda }^{\ast }$ be a dual optimum. Set the common optimal value to $p^{\ast }$. Weak duality and feasibility implyAll inequalities are therefore equalities. In particular, $u^{\prime }$ minimizes $L(\cdot ,{\lambda }^{\ast })$, whose $-{\lambda }^{\ast }\sigma$ term is constant. HenceThis 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 =\Vert u_{\lambda }-g{\Vert }_2^2}$. If a feasible $u$ had $\mathrm{TV}(u)<\mathrm{TV}(u_{\lambda })$, thencontradicting 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.