# How can we show that two different optimization problems have the same minimizer?

It is evident that the two following optimization problems have the same minimizer: $$\min_{Ax=b} \| x\|_2$$ That is, $$z=\arg\min_{Ax=b} \| x\|_2$$ $$\min_{Ax=b} \| x\|_2^2$$ That is, $$y=\arg\min_{Ax=b} \| x\|_2^2$$

However, what would be the way to show that $$y=z$$ where $$x,y,z \in \mathbb{R}^n$$? (Contradiction, straight proof,...)

• You can use the fact that $x \mapsto x^2$ is strictly increasing over the domain $[0, \infty)$. So, since $\|x\|_2 \ge 0$, we have $\|x\|_2 < \|y\|_2 \implies \|x\|^2_2 < \|y\|^2_2$. – Theo Bendit Oct 8 '18 at 1:40

I think a correct statement is: $$\text{the two problems has the same solutions set}.$$ Here is a direct argument. Let $$z$$ be a solution of the first problem. Our goal is to show that $$z$$ is a solution of the second problem. Indeed, let $$x$$ be such that $$Ax =b$$. Then, $$\lVert z\rVert_{2} \leq \lVert x \rVert_{2}$$ since $$z$$ is the solution of the first one and $$x$$ belongs to the feasible set. Squaring both sides, we get $$\lVert z\rVert^2_{2} \leq \lVert x\rVert_{2}^{2}$$, which shows that $$z$$ solves the second one. The converse is similar, just take the square root :)