# Lagrange optimization of reciprocals

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?

• 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$. – Winther Oct 17 '15 at 23:58
• I don't think gradient of $1/x$ should give you terms in $\log x$... – Chris Kerridge Oct 18 '15 at 0:02
• Does all $x_i$ equal really give the max? – André Nicolas Oct 18 '15 at 0:21
• 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)? – Almost Shirley Oct 18 '15 at 0:21
• 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. – Winther Oct 18 '15 at 0:23

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}$.
• 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$. – Batominovski Oct 18 '15 at 0:47