Sum of convex functions

Question

Let $f: R \rightarrow R$ be a convex function. Define the function $g$ to be the sum of $f(x)$ taking on different values, i.e. $g(1,2)=f(1)+f(2)$. Does $g$ possess any interesting/special properties other than the fact that it is also convex? Suggestions or references are greatly appreciated.

Answer 1

There might be many interesting properties, depending on what you are looking for. Here are some examples:

1. The problem $\min_{x_1, \dots, x_n} g(x_1, \dots, x_n)$ is separable. Can be minimized w.r.t $x$ and $y$ separately.
2. The Hessian matrix of $g$, if $f$ are all twice differentiable, is diagonal. It might help if you are minimizing $g(x) + h(x)$, where the Hessian of $h$ has low rank, and you are using Newton's method. Another example where it might help is when you are minimizing $g(x)$ subject to $A x + b$, and $A$ has low rank.
3. Using separability, it is also easy, in many cases, to derive a dual. For example, look at minimizing $g(x)$ subject to $\|x\|_2 \leq 1$.

If you tell us what exactly you are looking for, we might be able to find more `interesting' properties.