Optimisation: Minimise series

Question

Let $a_i\geqslant 0$ for $i=1,\ldots,n$.

Show how to minimize $$\sum_{i=1}^n\frac 1 {a_i+x_i}$$ subject to $$\sum_{i=1}^n x_i = b$$ where $x_i\geqslant 0$ for $i=1,\ldots,n$ and $b>0$.

I'm stuck on how to do this problem.

Answer 1

If we ignore the constraint that $x_i\ge0$ we can use standard Lagrangian methods but otherwise we must use Karush-Kuhn-Tucker. The objective function is convex and the constrain set is convex with a non-empty interior so we can use Kuhn-Tucker methods.

$$\mathcal{L}(x,\lambda)=\sum_{i=1}^{n}\dfrac{1}{a_i+x_i}+(\mu-\lambda_i) \cdot x_i$$

with $\lambda_i\ge 0$ and $\lambda_i\cdot x_i=0$ (complementary slackness condition). The first-order condition:

$$ \dfrac{-1}{(a_i+x_i)^2}=\lambda_i-\mu.$$ Thus if $x_i>0$ then $\lambda_i=0$ we must have $x_i=\dfrac{\sqrt{\mu}}{\mu}-a_i$ and $\mu>0$. Moreover, if $x_i>0$ for all $i$ we have $b=n\,\dfrac{\sqrt{\mu}}{\mu}-\sum\limits_{i=1}^{n} a_i$ and $x_i=\dfrac{b+\sum\limits_{j\neq i}a_j-(n-1)a_i}{n}$.

The above is the solution one gets by using standard Lagrangian methods but it clearly is not a feasible solution if $a_i$ is too high. The following procedure finds the optimal solution:

1. Without loss of generality order the $a_i$: $a_1\le a_2\le a_3 \le ... \le a_n$.
2. If $\frac{b+\sum\limits_{j\neq i}a_j-(n-1)a_n}{n}\ge 0$ then the above solution is the correct one, stop.
3. Otherwise set $x_n=0$ and tentatively consider $x_i=\frac{b+\sum\limits_{j<n,j\neq i}a_j-(n-2)a_i}{n-1}$ for $i<n$.
4. If $x_{n-1}\ge0$ then this is the solution, stop.
5. Otherwise set $x_{n-1}=0$ and proceed in the same manner as in the previous steps.

Answer 2

As Chris K intuited, the best approach is to try to make $a_i+x_i$ constant, or, more precisely, to make $\min\{a_i+x_i\mid i=1,\dots,n\}$ as large as possible. Can you prove this without taking any derivatives?

Details

First, we should recognize that there must be a minimum: the set of all positive $x_1,\dots,x_n$ satisfying the constraint $\sum x_i=b$ is closed and bounded, hence compact, and the function $f(x_1,\dots,x_n)=\sum \frac 1 {a_i+x_i}$ is continuous, so by the extreme value theorem $f$ has a minimum.

Suppose that $x_i \ge 0$, $x_k>0$, and $a_i+x_i<a_k+x_k$. Let $\delta$ be real. Then $$\frac 1 {a_i+x_i+\delta}+\frac 1 {a_k+x_k-\delta}=\frac {a_i+x_i+a_k+x_k}{(a_i+x_i)(a_k+x_k)+\delta((a_k+x_k)-(a_i+x_i))-\delta^2}.$$

So as long as $0<\delta<\min \{x_k,(a_k+x_k)-(a_i+x_i)\}$, increasing $x_i$ by $\delta$ while decreasing $x_k$ by $\delta$ will reduce $f$, so $x_1,\dots,x_n$ don't minimize $f$. That is, any two terms in the minimizer are either equal or cannot be rebalanced to be closer to each other.

Sergio Parreiras's algorithm can then be seen as finding values of $x_i$s meeting this criterion.

Answer 3

Using the method of Lagrange multipliers:

To ensure $x_i\ge 0$, we can use the substitution $x_i=u_i^2$.

Let $L(\lambda,u_1,\ldots)=\sum \frac 1 {a_i+u_i^2}+\lambda \left(\sum u_i^2-b\right)$.

Then $${\partial \over \partial u_i} L(\lambda,x_1,\ldots)= \frac{-2u_i}{(a_i+u_i^2)^2}+2\lambda u_i,$$ which is $0$ when $$u_i=0 \text{ or } \lambda = \frac 1 {(a_i+u_i^2)^2}.$$

Restoring the original variables, we see that for each $i$, either $x_i=0$ or $\dfrac 1 {(a_i+x_i)^2}=\lambda$.

Perhaps you can finish this.