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$
7
  • $\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
    Commented Oct 17, 2015 at 23:58
  • 1
    $\begingroup$ I don't think gradient of $1/x$ should give you terms in $\log x$... $\endgroup$ Commented Oct 18, 2015 at 0:02
  • $\begingroup$ Does all $x_i$ equal really give the max? $\endgroup$ Commented Oct 18, 2015 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$ Commented Oct 18, 2015 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
    Commented Oct 18, 2015 at 0:23

1 Answer 1

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$
2
  • $\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$ Commented Oct 18, 2015 at 0:47
  • $\begingroup$ The OP has for some reason edited that part of the question, which now makes less sense. $\endgroup$
    – Chappers
    Commented Oct 18, 2015 at 10:33

You must log in to answer this question.

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