Are these two optimization problems equivalent?

Question

I have two problems as follow.

$min_x: ||x-y||_2^2 + \lambda_1 ||x|| \quad \ \ (1)$

and

$min_x: ||x-y||_2^2 + \lambda_2 ||x||^2 \quad (2)$

Here $||\cdot||$ could be any norm and $\lambda_1\geq0$ and $\lambda_2 \geq 0$ and $\lambda_1$ and $\lambda_2$ are not fixed.

I think these two problems are equivalent. Here is my thinking. First these tow problems are equivalent to finding projections on norm balls as follow.

$min_{||x||\leq \bar{\lambda_1}}: ||x-y||_2^2 \quad \ \ (3)$

and

$min_{||x||^2\leq \bar{\lambda_2}}: ||x-y||_2^2 \quad \ \ (4)$

The only different between (3) and (4) is the radius of the norm ball. Because $\lambda_1$ and $\lambda_2$ are not fixed, so the radius can change. Therefore they are the same problem, although we don't know the corresponding relationships between $\lambda_1$ and $\lambda_2$ and $\bar{\lambda_1}$ and $\bar{\lambda_2}$.

Answer 1

It's hard to offer a mathematically rigorous definition of equivalence here, but the following handwaving definition is, in my view, quite robust:

Two mathematical models are equivalent if the solution to one immediately leads to a solution to the other, and vice-versa.

Consider (3) and (4): it is evident that they produce precisely the same solutions whenever $\bar{\lambda}_2 = \bar{\lambda}_1^2$. So you can solve (3) and immediately you have the solution to (4), and vice versa. Thus (3) and (4) are equivalent given that relationship between the $\lambda$ values.

On the other hand, if you solve (1) for a particular value of $\lambda_1$, you know that you've solved (2) for some value of $\lambda_2$---but you don't know which one. To the best of my knowledge there's no straightforward mapping between $\lambda_1$ and $\lambda_2$ in this case, and even if there were, you'd lose that straightforward mapping as soon as the model becomes even slightly more complex (e.g., adding constraints).

So you can't really say (1) and (2) are equivalent. Sure, they do trace out the same tradeoff curves between $\|x-y\|$ and $\|x\|$---so if you're only interested in the tradeoff curve, you can choose whichever of the two models you find easier to solve. (Indeed, (3) and (4) trace out the same tradeoff curves as well.) But that's not what the accepted definition of equivalence requires.