Formal argument for maximization of a sum of convex functions

650 Views Asked by At

For some strictly convex functions $f_1(x_1),f_2(x_2),...,f_n(x_n)$, it seems intuitive that for a given sum of $x_1+x_2+...+x_n=X$, where $x_1$, $x_2$,..., $x_n\geq0$

$$\exists k\in\{1,2,\dots,n\},\, f_k(X)=\max\left\{\sum_{i=1}^n{f_i(x_i)}\,:\sum_{i=1}^nx_i=X \text{ and } \forall i,\, x_i\geq 0\,\right\}$$

Since these functions are convex, the sum of these functions is greatest when the sum of arguments is equal to the argument of just one function. This seems intuitive, but I can't think of how to argue this in formal maths. Any suggestions?

1

There are 1 best solutions below

0
On

You can use the following theorem: if the maximum of a convex function on a convex set is attained, then it is attained at an extreme point.

In your case, the convex set is a simplex, which is a compact set. The function $F(x) = \sum_{i=1}^n f_i(x_i)$ is convex, and thus continuous. Therefore, the maximum is attained by Weirstrass. The constraints define a convex polytope, whose extreme points are its vertices, which are $(X, 0, \dots, 0),~(0, X, 0, \dots, 0), \dots, (0, \dots, 0, X)$. The result you wish follows from the fact that the maximum is attained at one of those vertices.