5
$\begingroup$

I would like to prove that $\left \| x \right \|_1 \le \sqrt{n} \left \| x \right \|_2$ for all $x \in \mathbb{R}^n$ using Lagrangian multipliers.

Thank you all for your help!

$\endgroup$
0
6
$\begingroup$

Hint: Minimize $(\left \| x \right \|_2)^2$ under the constraint $\left \| x \right \|_1=C$ where $C$ is a constant.

Note that the optimal $x$ may either be at a point of non-differentiability of $\|x\|_1$ or where the contour of $(\|x\|_2)^2$ is tangent to $\|x\|_1=C$. The local optimum in the latter case can be found using Lagrange multipliers. In the former case show that if some $x_i=0$ then $(\|x\|_2)^2$ is not minimal (by deleting the zero components of $x$ and thereby reducing to the Lagrange Multiplier case).

$\endgroup$
0

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.