5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Can you tell us anything more about $f$? $\endgroup$ – Rodrigo de Azevedo Jun 15 at 15:15
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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! $\endgroup$ – cirpis Jun 16 at 0:02
  • 1
    $\begingroup$ 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$. $\endgroup$ – Michael Jun 16 at 0:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.