3
$\begingroup$

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be a twice differentiable and strictly increasing function. Suppose that we are searching for the numbers $x_1$, ..., $x_n$ that maximise

$$\sum_{i=0}^{n}{f(x_i)}$$

subject to the constraints that $\sum_{i=0}^{n}{x_i}=\bar{x}$ and $x_i \geq 0$ for all $i$.

If $f$ is strictly concave everywhere, it is optimal to set $x_i = x_j$ for every $i$ and $j$ (so that $x_i^* = \bar{x}/n$ for all $i$). If $f$ is strictly convex everwhere, it is optimal to set $x_i=\bar{x}$ and $x_j=0$ for some arbitrary $i$ and all $j\neq i$. However, I am interested in the 'mixed' case where $f$ has at least one convex portion but is ultimately concave.

Specifically, suppose that $f$ is strictly concave for all $x \geq \hat{x}$. Does this imply that $x_i^* = x_j^*$ provided that $\bar{x}$ is 'large enough'? If so, what precisely is the assumption that we need to make about $\bar{x}$? If not, are there some additional assumptions we can make to ensure that $x_i^* = x_j^*$?

Many thanks in advance!

Edit 1: It has been pointed out that $f′(x_i^*)=f′(x_j^*)$ whenever $x_i^*>0$ and $x_j^*>0$. This might be a useful step towards an answer.

Edit 2: It has occurred to me that we will probably need to assume something like $f'(x) \rightarrow 0$ as $x \rightarrow \infty$ in order to ensure that $x_i^* = x_j^*$.

$\endgroup$
  • $\begingroup$ Can you assume that $f$ is quasiconcave? $\endgroup$ – Herr K. Jul 15 at 19:03
  • 1
    $\begingroup$ I think so. My understanding is that any monotone function is quasi-concave. Since $f$ is monotonically increasing, this would imply that it is quasi-concave. $\endgroup$ – afreelunch Jul 15 at 21:50
  • $\begingroup$ I guess a sufficient condition would be $f''(\bar x/n)<0$. $\endgroup$ – Herr K. Jul 15 at 23:03
  • $\begingroup$ Thanks for the idea - but why would this be sufficient? $\endgroup$ – afreelunch Jul 16 at 16:17
  • 1
    $\begingroup$ So to clarify: while $f$ is quasi-concave, the objective function $\sum_{i=0}^{n}{f(x_i)}$ need not be quasi-concave -- at least, unless we place some restriction on $\bar{x}$ (and perhaps make additional assumptions). $\endgroup$ – afreelunch Jul 17 at 16:31
3
$\begingroup$

If $f$ is strictly convex everywhere, it is optimal to set $x_i =\overline x$ and $x_j =0$ for some arbitrary $i$ and all $j\ne i$.

I assume from this that the $x_i$ are constrained to be non-negative?


Using the Lagrange multiplier technique with Lagrangian $L=\sum_i f(x_i)-\lambda (\sum_i x_i-\overline x)$, we can conclude that the stationary points occur when $\frac{\mathrm{d} f}{\mathrm{d}x}\big{|}_{x_i}=\lambda$. Furthermore, if some of the $x_i$ are assigned to be zero then we can use the same Lagrange multiplier technique on all of the remaining unassigned $x_i$.

Hence we can deduce that $\sum f(x_i)$ is maximised when, at all of the $x_i$ which do not satisfy $x_i=0$, $f(x)$ has the same derivative.


As an example, consider the case when $f(x)=(x-1)^3$ and $n=2$. If there is a maximum with $x_1$ and $x_2$ both non-zero, then it must be the case that $\frac{\mathrm{d}f}{\mathrm{d}x}=3(x-1)^2$ is the same at $x_1$ and $x_2$.

For $x_1$ and $x_2$ to be distinct we would have to have $x_1=1+\sqrt a, \ x_2=1-\sqrt a$ for some constant $a$. Therefore, it $\overline x \ne 2$, then at the maximum either $x_1=x_2$ or $x_1=0$ and $x_2=\overline x$. On the other hand, if $\overline x=2$ then, for any $0\le a \le 1$, there is a maximum with $x_1=1+\sqrt a, \ x_2=1-\sqrt a$ and $\sum_i f(x_i)=0$.


Finally, there is one point that I would like to make about eventually concave functions. The function graphed below contains a section which is strictly convex but very close to being a horizontal line followed by a section which is strictly concave but is very close to being a straight line. Even for rather large $\overline x$, the maxima will satisfy $x_i=\overline x$ and $x_j=0$ for $j \ne i$.

enter image description here

$\endgroup$
  • $\begingroup$ Thanks for the answer. 1) Yes, I did want to constrain the $x_i$ to be non-negative - apologies for forgetting to state this! 2) I completely agree that the derivatives must be the same in the interior, i.e. $f'(x_i)=f'(x_j)$ whenever it is optimal to set $x_i>0$ and $x_j>0$. 3) I am a bit confused about your example $f(x)=(x−1)^3$ -- this function is first concave then convex, whereas I am looking at the reverse case! 4) More generally, can you think of a sufficient condition to ensure that $x_i=x_j$ at the optimum? $\endgroup$ – afreelunch Jul 16 at 12:21

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.