I am trying to understand the relationship between the constrained and unconstrained versions of a convex optimization problem. The unconstrained problem is as follows: $$\min_{X}||X-Y||_2^2 + \lambda \mbox{TV}(X)$$ I am trying to show that it is equivalent to the following constrained problem $$\min_X \mbox{TV}(X) \mbox{ s.t. } ||X-Y||_2 < \beta$$ How can I show that the two optimization problems are equivalent? My idea is to express each as a Lagrangian and show that the Lagrangians are the same. The Lagrangian for the first problem would be $$L_1(X, \lambda) = ||X-Y||_2^2 + \lambda \mbox{TV}(X)$$ The Lagrangian for the second problem would be $$L_2(X, \lambda) = \mbox{TV}(X)+\lambda(||X-Y||_2^2 - \beta)$$ Is there a way to rewrite $L_1$ such that it corresponds to $L_2$ for a different choice of $\lambda$? Or vice versa? Thanks!

  • $\begingroup$ This has nothing to do with constraint programming, by the way... $\endgroup$ – Michael Grant Mar 21 '14 at 1:53
  • 1
    $\begingroup$ Two problems here. First of all, $L_1$ is not the Lagrangian of the first problem. $\lambda$ is fixed, so really, there is no Lagrangian; or rather, it's simply the objective function, a function of $X$ alone. Second, don't use $\lambda$ in $L_2$, because it deceives you into thinking that it is the same $\lambda$ as the first, when of course it is not: it is the Lagrange multiplier for the inequality constraint. $\endgroup$ – Michael Grant Mar 21 '14 at 1:58
  • $\begingroup$ And finally: what exactly do you believe the definition of "equivalence" is here? I mean, I know Boyd et. al. talk about it in handwaving terms but I am not sure their definition is precise enough by itself to automatically suggest a proof here. $\endgroup$ – Michael Grant Mar 21 '14 at 2:01
  • $\begingroup$ Thanks for the response, @Michael. I'm new to optimization, so I'm still trying to understand the basics. By equivalence, I mean that the minimizer of the first problem and the minimizer of the second problem are both the same. Does this basically come down to finding a closed form solution for both the problems and showing that they are eqiuvalent? What dictates whether you can write a closed form solution? How can you show "equivalence" (in my sense) if there is no way to write a closed form solution? Thanks! $\endgroup$ – Vivek Subramanian Mar 21 '14 at 13:52
  • $\begingroup$ Yeah, that definition of equivalence is simply not going to work---because it will almost never be true. You do not know what $\beta$ and $\lambda$ are, so you can't possibly say that the minimizers will be the same. What I believe you can say, and prove with at least some formality, is that for some particular value of $\lambda\in[0,\mathop{\textrm{TV}}(Y)]$, that there exists a value of $\beta\in[0,\|Y\|_2]$ where the minimizers coincide, and vice versa. $\endgroup$ – Michael Grant Mar 21 '14 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.