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 '19 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$ – user17900 Jul 15 '19 at 21:50
  • $\begingroup$ I guess a sufficient condition would be $f''(\bar x/n)<0$. $\endgroup$ – Herr K. Jul 15 '19 at 23:03
  • $\begingroup$ Thanks for the idea - but why would this be sufficient? $\endgroup$ – user17900 Jul 16 '19 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$ – user17900 Jul 17 '19 at 16:31
2
$\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

|improve this answer|||||
$\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$ – user17900 Jul 16 '19 at 12:21

Your Answer

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