Maximizing a convex function The following problem is exercise I.6 from Bellman's Dynamic Programming.
Consider the problem of maximizing the function
$$
F(x_{1} , \ldots , x_{N}) = \sum_{i = 1}^{n} \varphi(x_{i}),
$$
subject to the constraints $x_{i} \geq 0$ and $\displaystyle\sum_{i = 1}^{N} x_{i} = c$. Show that if $\varphi$ is convex, then the maximum is $\varphi(c)$.
I don't think this problem is correct as written. Consider the example with $n = 2$, $c = 1$ and $\varphi : \mathbf{R} \to \mathbf{R} : x \mapsto x^{2} + 1$. Then, $\varphi(c) = 2$, but $x = (1,0)$ is feasible and achieves an objective value of $F(1,0) = \varphi(1) + \varphi(0) = 2 + 1 = 3$, so the maximum is not $\varphi(c)$.
What do you think the author meant to ask? One modification I found is the following.
Consider the problem of minimizing the function
$$
F(x_{1} , \ldots , x_{N}) = \sum_{i = 1}^{n} \varphi(x_{i}),
$$
subject to the constraints $x_{i} \geq 0$ and $\displaystyle\sum_{i = 1}^{N} x_{i} = c$. Show that if $\varphi$ is convex, then the maximum is $n \varphi\left(\frac{c}{n}\right)$.
Can anyone think of something better? My problem loses the simplicity of the answer, $\varphi(c)$, and also the character of maximizing a convex function.
 A: Summarized: Correct answer is $\phi(c) + (n-1)\phi(0)$ in general, so he probably assumed $\phi(0)=0$ which is a trivial shift of the problem.
Why? Because convexity implies immediately that taking a bit off the largest $x$ and adding it to any of the others decreases the target function. This is because the gradient of $\phi$ is steeper at the larger value. Hence $(c,0,0,\cdots,0)$ is trivially optimal.
The followings are my first naïve early hours approach.

I think it's easiest to solve the problem and then work out what the answer was. The following is unnecessarily complicated, but totally brainless which is sometimes an advantage. Let's look for stationary points inside the range with Lagrange multipliers:
$G(x_i;\lambda) = \sum\phi(x_i) - \lambda (\sum x_i - c)$
This gives $\phi'(x_i) = \lambda$ for all $x_i$. Hence if $\phi''$ has a definite sign, there is at most one solution to this equation (since $\phi'$ is monotonic) and therefore $x_1=x_2=\cdots=x^\star$. But from the constraint, $nx^\star = c$ and therefore the only stationary point is
$$\boxed{n \phi(\frac{c}{n})}$$
as you suggest.
Now what about the maximum on the boundary? Setting one variable at a time to zero, we find that the possible stationary points here are just versions of the above restricted to a smaller number of variables. Hence the possible stationary points are
$$n \phi\left(\frac{c}{n}\right), (n-1) \phi\left(\frac{c}{n-1}\right)+\phi(0), (n-2) \phi\left(\frac{c}{n-2}\right)+2\phi(0), \cdots, \phi(c)+(n-1)\phi(0)$$
depending on how many variables are non-zero.
The only remaining question is which of these is largest. Note that
$$m \phi(c/m) +(n-m)\phi(0) = n\phi(0) + m(\phi(c/m) -\phi(0))$$
But so long as $\phi''(0) > 0$, $$\phi(x) -\phi(0) > m (\phi(x/m)-\phi(0))$$ and hence the maximum is in fact
$$\boxed{\phi(c)+(n-1)\phi(0)}$$
You can see this by using standard results on convex functions. Intuitively, it's better to put all your eggs in one basket, since your rate of return goes up with your investment.
Hence he was likely assuming $\phi(0)=0$.
Edit: Noticed and fixed massive error.
