Show that $\|x\|_1 = 1/2 \inf_{y > 0}(\sum_{i=1}^{m}\frac{x_i^2}{y_i} + 1^Ty)$

Question

Show that $\|x\|_1 = 1/2 \inf_{y > 0}(\sum_{i=1}^{m}\frac{x_i^2}{y_i} + 1^Ty)$ for $x \in R^{m}$.

I think an equivalent problem is: minimize $f(y) = 1/2 (\sum_{i=1}^{m}\frac{x_i^2}{y_i} + 1^Ty)$.

$1/y$ is a convex function on $y > 0$, $1^Ty$ is a convex function so, $1/y + 1^Ty$ is a convex function. I remember something like that the $\inf$ of a convex function over a convex set is convex.

$df(y)/dy_i = 1/2(-\frac{x_i^2}{y_i^2} + 1) = 0, y_i^2 = x_i^2, y_i = |x_i|$

The function value at $y_i$ becomes $m/2 + 1^Ty = m/2 + 1^T|x|$ which is not equal to the $\|x\|_1 = 1^T|x|$.

Answer 1

Your derivation is almost correct until you claim that the function value becomes $m/2 + 1^T|x|$. When $y_i = |x_i|$,

$$\frac{1}{2}\left(\sum_{i=1}^{m}\frac{x_i^2}{y_i} + 1^Ty\right) = \frac{1}{2}\left(\sum_{i=1}^{m}\frac{x_i^2}{|x_i|} + 1^T|x| \right)=\frac{1}{2}\left(\sum_{i=1}^{m}|x_i|+||x||_1\right)=||x||_1.$$

Answer 2

We have for $y>0$ \begin{align} \sum_{i=1}^{m}\frac{x_i^2}{y_i} + 1^Ty &= \sum_{i=1}^{m}(\frac{x_i^2}{y_i}+y_i) \\ &= \sum_{i=1}^{m}(\frac{x_i^2}{y_i}+y_i-2|x_i|) + 2\sum_{i=1}^{m}|x_i|\\ &= \sum_{i=1}^{m}(\frac{|x_i|}{\sqrt{y_i}}-\sqrt{y_i})^2 + 2\sum_{i=1}^{m}|x_i| \ge 2\sum_{i=1}^{m}|x_i| = 2||x||_1\\ \end{align}

Hence, $\|x\|_1 = 1/2 \inf_{y > 0}(\sum_{i=1}^{m}\frac{x_i^2}{y_i} + 1^Ty)$ for $x \in R^{m}$