3

Suppose we have function $f:\mathbb{R}^{|d_x+d_y+d_z|}\rightarrow\mathbb{R}$, $g:\mathbb{R}^{|d_x+d_y|}\rightarrow\mathbb{R}$ and $h:\mathbb{R}^{|d_y+d_z|}\rightarrow\mathbb{R}$, satisfying

$$f(x,y,z) = g(x,y)+ h(y,z),$$ where $x, y, z$ are vectors in $\mathbb{R}^{d_x}$, $\mathbb{R}^{d_y}$ and $\mathbb{R}^{d_z}$, respectively.

If $g$ and $h$ are strictly convex, is $f$ also strictly convex?

I feel this is not necessarily true because the strict convexity of $g$ and $h$ from $y$ may cancel each other out, but I am not able to find a good counter-example. On the other hand, using the definition of strict convexity, it does seem that the above is a true statement. I appreciate your help.

fwd
  • 3,290
Tan
  • 621

2 Answers2

2

Consider two points $P=(x,y,z)$ and $P'=(x',y',z')$, with $P \ne P'$, and a point strictly between them $P''=tP+(1-t)P'=(x'',y'',z'')$ with $0 < t < 1$.

Now either $(x,y) \ne (x',y')$ or $(y,z) \ne (y',z')$ (or both). You have $$g(x'',y'') \le tg(x,y) + (1-t)g(x',y')$$ and $$h(y'',z'') \le th(y,z) + (1-t)h(y',z')$$ both by convexity, and at least one of them is strict. Add up the inequalities, you get $$f(x'',y'',z'') < tf(x,y,z) + (1-t)f(x',y',z')$$ which gives you strict convexity.

Jukka Kohonen
  • 2,729
  • 1
    The result is correct, but not your proof. Note that you can have (for example) $x=x'$ and $y=y'$, in which case equality holds for $g$. – Martin R Sep 02 '21 at 14:20
  • You are right. I was just editing that, but since Misha has already the correct answer, my answer is superfluous and I could as well delete it now. – Jukka Kohonen Sep 02 '21 at 14:22
  • 1
    I don't think MSE is so short on storage space that we can't accommodate two similar answers to a question written at about the same time. – Misha Lavrov Sep 02 '21 at 14:23
  • Ok, I'll leave it there -- but I'll gladly acknowledge that Misha has the priority of a correct answer (by 1 minute) ! – Jukka Kohonen Sep 02 '21 at 14:25
2

It's a standard fact that adding two functions that really are strictly convex would produce a third strictly convex function. However, that's not what's happening in your case: $g(x,y)$ is a strictly convex function of $x$ and $y$, but it is not a strictly convex function of $(x,y,z)$. So we're adding two functions that are "merely convex", and can't use the simple argument.

Instead, let's pull out the definition. Take two points $(x_1, y_1, z_1)$ and $(x_2,y_2,z_2)$ and take $0 < \lambda < 1$. Then we always have $$\lambda g(x_1,y_1) + (1-\lambda) g(x_2,y_2) \ge g(\lambda x_1 + (1-\lambda)x_2, \lambda y_1 + (1-\lambda)y_2)$$ and $$\lambda h(y_1,z_1) + (1-\lambda) h(y_2,z_2) \ge h(\lambda y_1 + (1-\lambda)y_2, \lambda z_1 + (1-\lambda)z_2)$$ because $g$ and $h$ are convex functions.

The first inequality is strict unless $(x_1, y_1) = (x_2, y_2)$. The second inequality is strict unless $(y_1, z_1) = (y_2, z_2)$. Therefore, assuming $(x_1,y_1,z_1) \ne (x_2,y_2,z_2)$, at least one of the inequalities is strict. Adding them together produces a strict inequality, which is the definition of strict convexity of $f$.

Misha Lavrov
  • 142,276