# Maximize an unweighted sum given a weighted sum

My problem boils down to the following:

Given real numbers $$c_i \geq 0$$

$$\begin{array}{ll} \text{maximize} & f(x_1)+f(x_2)+\cdots+f(x_n)\\ \text{subject to} & c_1x_1+c_2x_2+\cdots +c_nx_n = C\\ & x_i \geq 0\end{array}$$

It is furthermore known that and $$f$$ is concave, strictly increasing and bounded.

I know that if we instead maximize $$c_1f(x_1)+c_2f(x_2)+\ldots+c_2f(x_n)$$, then we can apply Jensen's inequality and bound our sum from above by a constant and then apply the equality criterion

$$\frac{c_1f(x_1)+c_2f(x_2)+\ldots+c_2f(x_n)}{c_1+c_2+\ldots+c_n}\leq f\left(\frac{c_1x_1+c_2x_2+\ldots +c_nx_n}{c_1+c_2+\ldots+c_n}\right) = f\left(\frac{C}{c_1+c_2+\ldots+c_n}\right)$$

with equality iff

$$x_1 = x_2 = \ldots = x_n = \frac{C}{c_1+c_2+\ldots+c_n}$$

Is there a way to salvage this solution for the unweighted case given weighted constraints?

• Can you tell us anything more about $f$? – Rodrigo de Azevedo Jun 15 at 15:15

I think you are asking if you can get an "easy" solution that holds independent of the particular structure of $$f$$, that is, a solution that depends only on $$C,c_1,...,c_n$$.
Not in general. To see why, you can just do an example: Fix $$C>0$$. Fix $$\epsilon>0$$ and assume $$c_i\geq \epsilon$$ for all $$i$$. Then any $$(x_1, ..., x_n)$$ that satisfies the constraints must have $$x_i\leq C/\epsilon$$ for all $$i \in \{1, ..., n\}$$. Fix $$\alpha \in (0,1)$$ and define $$f(x) =\left\{ \begin{array}{ll} x^{\alpha} &\mbox{ if 0\leq x \leq C/\epsilon} \\ (C/\epsilon)^{\alpha} & \mbox{ if x>C/\epsilon} \end{array} \right.$$
By a simple Lagrange multiplier argument you can show that the solution to maximizing $$\sum_{i=1}^n f(x_i)$$ subject to $$\sum_{i=1}^n c_i x_i\leq C$$ and $$x_i\geq 0$$ for all $$i$$ is: $$x^*_i = \frac{Cc_i^{-1/(1-\alpha)}}{\sum_{j=1}^n c_j^{-\alpha/(1-\alpha)}} \quad \forall i \in \{1, ..., n\}$$ This solution requires knowledge of $$\alpha$$.
On the other hand, the problem can easily be worked out by a Lagrange multiplier argument: Maximize $$\sum_{i=1}^n f(x_i) -\lambda \left(\sum_{i=1}^n c_i x_i - C\right)$$ over $$x_i\geq 0$$ for all $$i \in \{1, ..., n\}$$. Then choose $$\lambda$$ to make the constraint $$\sum_{i=1}^n c_ix_i = C$$ hold.
• Right, I see what you are saying - the answer really depends on the precise structure of $f$ and there doesn't seem to be an easy way around it. See my issue is that I don't have that good a knowledge of $f$ other than the fact that its concave, increasing and bounded, and I really cant get much more specificity than that. (This is why Lagrange multipliers didn't work for me). However, your example does seem enlightening - I will try solving it by looking for a certain type of weighted sum! I.e. solutions of the form $x_i = \frac{C g(c_i)}{\sum_{j=1}^n g(c_j)c_j}$. Thanks! – cirpis Jun 16 at 0:02
• PS: The 2-part structure of f was only to satisfy the “bounded” requirement. The same solution holds if we just define $f(x)=x^{\alpha}$ for all $x\geq 0$. – Michael Jun 16 at 0:02