1
$\begingroup$

Suppose we want to find the $x_i$ such that $$\sum_{i=1}^p\frac{1}{1+x_i}$$ has an extreme value, such that the $x_i$ are all non-negative, and $\sum_{i=1}^n x_i=p$.

This should be doable with lagrange multipliers, but how? The inequality is tricky, so I considered replacing the $x_i$ with $x_i^2$. However, each entry of the gradient gives you $(1+x_i^2)^{-2}2x_i=\lambda 2x_i$, so I'm not quite sure how to proceed. It seems obvious that you get a min when all the $x_i$ are 1, but what about the maximum?

Edit: It was noted that I need to check the boundary points for the maximum. Is there a systematic technique to do this? I suspect that the max will be attained when all but one of the $x_i$ is zero, but how do you start when the boundary contains so many points?

$\endgroup$
  • $\begingroup$ Note that the lagrange equations have to be satisfied for all $x_i$. This usually implies that all $x_i$ are equal (did not check if this is the case here). If this is the case then the value of $x_i$ can then be found from $\sum x_i =p \implies x_i = p/n$. $\endgroup$ – Winther Oct 17 '15 at 23:58
  • 1
    $\begingroup$ I don't think gradient of $1/x$ should give you terms in $\log x$... $\endgroup$ – Chris Kerridge Oct 18 '15 at 0:02
  • $\begingroup$ Does all $x_i$ equal really give the max? $\endgroup$ – André Nicolas Oct 18 '15 at 0:21
  • $\begingroup$ Sorry, I was wrong on those two points. I meant that you should get a minimum, and I fixed the gradient calculation. It still seems you can only find one extreme solution. What about the other(s)? $\endgroup$ – Almost Shirley Oct 18 '15 at 0:21
  • $\begingroup$ The maximum is not attained in the interior of the surface $\sum x_i = p$ with $x_i\geq 0$ (since you only found one solution) so it must be attained on the boundary. You need to check the cases where one or more of $x_i$ are zero. $\endgroup$ – Winther Oct 18 '15 at 0:23
1
$\begingroup$

Let $$ L = \sum_{i=1}^n \frac{1}{1+x_i} - \lambda \left( \sum_{i=1}^n x_i -p \right). $$ Then $$ \frac{\partial L}{\partial x_j} = \frac{-1}{(1+x_j)^2}-\lambda, $$ and so we discover that if the gradient of $L$ is zero (required for an internal extremum), all of the $x_j$ are equal, and in particular, equal to $p/n$, by the constraint. In this case, the value of $L$ is $$ \frac{n}{1+p/n} = \frac{n^2}{n+p} = \frac{n(n+p)-np-p^2+p^2}{n+p} = n-p + \frac{p^2}{n+p} $$.

What if we don't have this case? Then the extremum occurs on the boundary, i.e. when one of the $x_i$ at least is zero. By symmetry we can assume $x_n=0$, and $L$ becomes $$ L\mid_{x_n=0} = 1 + \sum_{i=1}^{n-1} \frac{1}{1+x_i} - \lambda \left( \sum_{i=1}^{n-1} x_i - p \right). $$ Ah, but this is exactly the same problem as we solved before, but with $n$ replaced by $n-1$. Hence the extremum is at $x_i=p/(n-1)$, and so the value is $$ 1+ \frac{(n-1)^2}{n-1+p} = \frac{n-1+p-(n-1)+n(n-1)}{n-1+p} = n-p+\frac{p^2}{n-1+p}. $$ Similarly, if $k$ of the $x_i$ are zero, we find $$ k+\frac{(n-k)^2}{n-k+p} = k+n-k-p + \frac{p^2}{n-k+p} = n-p + \frac{p^2}{n-k+p}, $$ which obviously increases as $k$ increases. Hence the global maximum is when $k=n-1$, with value $n-1+\frac{1}{1+p}$, whereas the global minimum is when all the $x_i$ are $p/n$ (can check this is a minimum using the Hessian), with value $\frac{n}{1+p/n}$.

$\endgroup$
  • $\begingroup$ But in the problem statement, the sum to be optimized runs from $i=1$ to $i=p$, and not to $i=n$. Unless there is a typo on the OP's part, your answer will be wrong. If there is no typo, the minimum will be $\frac p2$ and the maximum will be $p$. $\endgroup$ – Batominovski Oct 18 '15 at 0:47
  • $\begingroup$ The OP has for some reason edited that part of the question, which now makes less sense. $\endgroup$ – Chappers Oct 18 '15 at 10:33

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.