Is a function of the form $f(x) = \|x\|_1\|x\|_2$ convex in x? I have tried plotting it in wolfram alpha and it appears convex, althought I ahve not been able to show it yet
is product of norms convex?
2 Answers
No, it isn't. Consider (for functions on $\mathbb R$) $ x(t) = \cases{1/n^3 & for $0 \le t \le n^4$\cr 0 & otherwise\cr}, \ y(t) = \cases{n^3 & for $-1/n^4 < t < 0$\cr 0 & otherwise\cr} $ We have $\|x\|_1 = n$, $\|y\|_1 = 1/n$, $\|x\|_2 = 1/n$, $\|y\|_2 = n$, so $f(x) = f(y) = 1$. However, $\|(x+y)/2\|_1 > n/2$ and $\|(x+y)/2\|_2 > n/2$, so $f((x+y)/2) > n^2/4 > 1$ if $n > 2$.
EDIT: it seems that $f$ is convex on ${\mathbb R}^3$ but not on ${\mathbb R}^4$. Counterexample for ${\mathbb R}^4$: $x = (1,0,0,0)$, $y = (0,1/5,1/5,1/5)$, $f((x+y)/2) = .4233202099 < (f(x)+f(y))/2 = .6039230485$.
EDIT: Oops, wrong way. Try $x = (1,0,0,0)$, $y = (.9,.07,.07,.07)$, $f((x+y)/2) = 1.004288519 > (f(x)+f(y))/2 = 1.004012120$.
-
0However, it is true that $f$ is quite nonconvex along the straight-line path $(1,0,0,0) + \alpha(-\frac32,1,1,1)$ for \alpha<0.049. – 2013-01-05
Hint: we have $(\lVert x\rVert_1+\lVert y\rVert_1)((\lVert x\rVert_2+\lVert y\rVert_2)\geqslant 0$. Multiply this by $\alpha(1-\alpha)\geqslant 0$. It's the difference between $\alpha f(x)+(1-\alpha)f(y)\mbox{ and }\alpha \lVert x\rVert_1+(1-\alpha)\lVert y\rVert_1))(\alpha \lVert x\rVert_2+(1-\alpha)\lVert y\rVert_2).$
-
0I have seen the specific condition that you mentioned before (reversed for concave functions). But as you pointed out, it need hot hold in general. – 2012-12-13