0

I know that the norm of $x\in R^n$, $(\sum\limits_{i=1}^n|x_i|^2)^{0.5}$ is a convex function. Also, not any composition of two convex functions is convex.

So my question is:
Lets say we have a real convex function $f_i=f(x_i)$, $i=1,...,n$. Is the $(\sum\limits_{i=1}^n|f_i|^2)^{0.5}$ convex?

Yair Forchevsky
  • 41
  • Can you elaborate on which norm you want to talk about? When we put a norm on the space of convex functions, it could be the sup norm, integral norm or any other norm. – Srinivas K Feb 11 '15 at 09:14
  • @Did : Sorry. What exactly is meant by " Is the norm of f(X) convex ? " – Srinivas K Feb 11 '15 at 09:24

3 Answers3

4

No, for example $ f(x) = x^2 - 1$.

Look at the graph of $| f(x) |$:

enter image description here

Edit: here's a counterexample for the updated question: \begin{equation*} h(x) = \sqrt{(x_1 - 1)^2 + (x_2 - 1)^2}. \end{equation*} enter image description here

littleO
  • 51,938
  • Thanks for the answer. I am interested in 2-norm. Sorry for not being clear. more specifically: if $f_i = f(x_i)$, $i=1,..,n$ is a convex function. Then the norm would be: $ (\sum\limits_{i=1}^n |f_i|^2)^{0.5}$. – Yair Forchevsky Feb 11 '15 at 11:18
  • This provides a counterexample in the case where $n = 1$, and if a conjecture like this fails when $n = 1$ then it seems unlikely to hold true for larger values of $n$. You can use a similar idea to find a counterexample when $n = 2$ or for larger values of $n$. – littleO Feb 11 '15 at 11:31
  • Thanks. I'm not sure. Following the argument of Mukhopadhyay below I can write: $ \sum\limits_{i=1}^n (f(\alpha x_i+(1-\alpha)x_i)^2 \le \sum\limits_{i=1}^n (\alpha f(x_i)+(1-\alpha)f(x_i))^2$ which holds since each term in the sum on the right hand side is larger than that on the left due to the convexity of $f(x)$. – Yair Forchevsky Feb 11 '15 at 12:01
  • Hmm, I think that way of looking at it might be a bit overly complicated. We just need to find a simple example where the function is clearly not convex. But first I have a question for you: in your question, do you mean that there is a convex function $f:\mathbb R \to \mathbb R$ such that $f_i(x) = f(x_i)$ for $i = 1,\ldots, n$? That's how it's phrased right now. So in that case, you're asking if the function $h(x) = (\sum_{i=1}^n f(x_i)^2)^{1/2}$ is convex. Is that what you intended? – littleO Feb 11 '15 at 12:07
  • Actually yes, sorry for the confusion and thanks for taking the time to answer. – Yair Forchevsky Feb 11 '15 at 13:26
  • I just updated my answer to show a counterexample in the case $n = 2$. – littleO Feb 12 '15 at 01:25
0

No, not necessarily. Something that could occur is that part of your convex function lies under the $x$-axis, which is then mirrored in the $x$-axis by the norm. Take $f(x) = x^2-10$ for example.

Marc
  • 6,861
0

This is to ask if $g,f$ are convex functions then whether $g\circ f$ is also convex. Let $D=Dom(f)\cap Dom(g)$. Then, for $x,y\in D,\ \alpha\in [0,1]$, $$g(\alpha f( x)+(1-\alpha)f(y))\le \alpha g(f(x))+(1-\alpha)g(f(y))$$ But a sufficient condition for $$g(f(\alpha x+(1-\alpha)y))\le g(\alpha f( x)+(1-\alpha)f(y))$$ is that $g$ is increasing. Otherwise, as in the case of norm, it may not be true always as pointed out by other answers.

EDIT As the original question is modified a little bit, I am giving another answer.

Now, you have a function $g:\mathbb{R}^n\to \mathbb{R}^n$, with $g_{i}(x)=f(x_i)$. The function that you are interested in is $h:\mathbb{R}^n\to \mathbb{R}^+$defined as $h(x)=\sqrt{\sum_{i}f^2(x_i)}$. Then, $h$ would be convex if the Hessian $\nabla^2 h$ is positive definite $\forall x\in \mathbb{R}^n$. Now, $\{\nabla h(x)\}_i=\frac{f(x_i)f'(x_i)}{h(x)}$, so $$\nabla^2h(x)_{ii}=\frac{\left(f'(x_i)^2h(x)+f(x_i)f''(x_i)h(x)-\frac{(f(x_i)f'(x_i))^2}{h(x)}\right)}{h^2(x)},\ \nabla^2h(x)_{ij}=0,\ i\ne j$$The numerator of $\nabla^2 h(x)$ can be written as (after taking $h(x)$ to the denominator)$$\sum_{j\ne i}f'(x_i)^2f(x_j)^2+\sum_{j}f(x_i)f''(x_i)f(x_j)^2$$So, if $f$ is a positive real valued convex function, like $x^2$, then the Hessian at any point is a diagonal matrix with non-negative diagonals making the matrix positive semi-definite and hence the function $h$ convex.

Samrat Mukhopadhyay
  • 16,277
  • Thanks for the answer. Mind that I edited the question: I mean a 2-norm not absolute value. I know this argument for a differentiable function, but this is more general, nice. So would you say that the 2-norm of a convex function is convex? – Yair Forchevsky Feb 11 '15 at 11:33
  • Thanks for the answer. Isn't it possible to make the following argument based on what you suggested originally: $\sum\limits_{i=1}^n \sqrt{f(\alpha x_i+(1-\alpha)y_i)^2}\le \sum\limits_{i=1}^n \sqrt{\alpha f(x_i)+(1-\alpha)f(y_i))^2} \le \alpha \sqrt{ \sum\limits_{i=1}^n f(x_i)} + (1-\alpha) \sqrt{\sum\limits_{i=1}^n f(y_i)} $. The first inequality is due to the convexity of $f(x)$ and the second is the triangle inequality. – Yair Forchevsky Feb 11 '15 at 13:58
  • I will think about it @YairForchevsky. – Samrat Mukhopadhyay Feb 11 '15 at 14:55
  • Actually I realized that the first inequality that I wrote holds only for positive (or more precisely non-negative) $f(x)$ so it agrees with the result you got using the Hessian. So I guess this concludes the issue for me. Thanks again. – Yair Forchevsky Feb 11 '15 at 19:51
  • You are Welcome. – Samrat Mukhopadhyay Feb 11 '15 at 19:58