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,...)

  • 2
    $\begingroup$ 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$. $\endgroup$ – 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 :)


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.