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
  • 1
    $\begingroup$ Can you tell us anything more about $f$? $\endgroup$ Jun 15, 2019 at 15:15

1 Answer 1

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
  • 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, 2019 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, 2019 at 0:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .