Minimum of sum of reciprocals of positive real numbers with inequality costraint

Question

I am facing a problem where you have to find the minimum of the function \begin{equation} f(a_1,...,a_n) = \sum_{i=1}^n \frac{1}{a_i} \end{equation} constrained to \begin{equation} \sum_{i=1}^n a_i = 2m \end{equation} and \begin{equation} a_1 \leq m \leq a_n \end{equation} where $a_1$ and $a_n$ are respectively the smallest and the largest element and $a_i>0\ \forall i$. Can we find the minimum of $f(a_1,...,a_n)$ without resorting to non-linear optimization methods?

ADDITIONAL THOUGHTS:

I already faced a similar problem without the constraints on $a_1$ and $a_n$ that can be solved through Cauchy-Schwarz inequality. If we apply C-S trying to exclude one of the elements, say $a_j$, we find \begin{equation} \sum_{i=1}^n \frac{1}{a_i} \geq \frac{(n-1)^2}{2m- a_j} + \frac{1}{a_j}\ . \end{equation} which according to Monte Carlo simulations takes the minimum when $a_j=m$. In fact, the result should be \begin{equation} f(a_1,...,a_n) \geq \frac{(n-1)^2}{m} + \frac{1}{m} \end{equation} meaning that the minimum of $f(a_1,...,a_n)$ is reached when one of the elements is exactly $m$.

Answer 1

Wow, the solution just blew my mind! You are absolutely correct about monte-carlo. First consider the Am-Gm-Hm inequality, we have

$$\frac{n}{\sum_{i=1}^{n}\frac{1}{a_i}}\le \frac{\sum_{i=1}^{n}a_i}{n} \Rightarrow \sum_{i=1}^{n}\frac{1}{a_i} \ge \frac{n^2}{\sum_{i=1}^{n}a_i} = \frac{n^2}{2m}$$

With equality iff $\forall i,j: a_i=a_j=\frac{2m}{n}$ and you get the same result if you write Lagrangian and KKT conditions. But this is correct if the problem is unconstrained, while we have $a_1\le m\le a_n$, therefore we must treat $m$ like an optimization variable. The inequality constraints $a_1\le m \le a_n$ can be written as $-m\le -a_1,\cdots, m\le a_n$ which can be written as $I_i(m-a_1)\le 0$ where $I_i=\pm1$ is some indicator function that governs the sign of inequalities. Therefore in our case the Lagrangian is

$$\mathcal{L} (a_1,\cdots,a_n,m,\nu,\lambda_1\cdots,\lambda_n) = \sum_{i=1}^{n}\frac{1}{a_i} + \nu \left( \sum_{i=1}^{n}a_i -2m \right) + \sum_{i=1}^{n} I_i\lambda_i(m-a_i)$$

and the KKT conditions become

$$\begin{align} &\frac{\partial \mathcal{L}}{\partial a_i} =0 \Rightarrow \frac{-1}{a_i^2}+\nu-I_i\lambda_i=0 \\ & \frac{\partial \mathcal{L}}{\partial m} = -2\nu + \sum_{i=1}^{n} I_i\lambda_i = 0\\ &\forall i: \lambda_i(m-a_i)=0 \\ &\nu \left( \sum_{i=1}^{n}a_i -2m \right)=0 \end{align}$$

We know that $\nu \neq 0$ since $\nu \left( \sum_{i=1}^{n}a_i -2m \right)=0$ and $\sum_{i=1}^{n}a_i = 2m $, this means at least one of $\lambda_i$ is non-zero through equation $\frac{\partial \mathcal{L}}{\partial m} = -2\nu + \sum_{i=1}^{n} I_i\lambda_i = 0$. Assume $\lambda_j\neq 0$ which in combination with $\lambda_i(m-a_j)=0 $ results in $a_j=m$. This means $\sum_{i=1,i\neq j}^{n}a_i=m$ and since $\forall i: a_i \ge 0$, this means $m\ge 0$ and no other $a_i$ is equal to $m$, or there is exactly two $a_i$'s which are equal to $m$. In the latter case, let's call them $a_j=m,a_k=m$.

The first case results in $a_j=m$ and the unconstrained problem (which we solved at the beginning using AM-HM inequality) $\sum_{i=1,i\neq j}^{n}\frac{1}{a_i}$ subject to $\sum_{i=1,i\neq j}^{n}a_i=m$ and $a_j=m$ which has minimum $\frac{(n-1)^2}{m}+\frac{1}{m}$, or the second case where $a_j=a_k=m$ and rest of $a_i=0$ which has minimum $\frac{2}{m}$ but since $\forall i: a_i > 0$ only the first case is acceptable.

I forgot to mention, the problem is obviously convex, so KKT conditions are necessary and sufficient to find global optimum.

It is obvious because all the constraints are linear and the objective is sum of functions of the form $f(x_i)=\frac{1}{x_i}$. Consider each $f(x_i)$ individually, the hessian is $f''(x_i) = \frac{1}{x_i^3}$ which in the non-negative orthant, is convex. Now the main objective is positive sum of individual convex functions $\sum_{i=1}^{N}f(x_i)$ which is convex itself since positive summation (and more general case, expectation) conserves convexity. Unfortunately there is no easier way, you should always check convexity through Hessian, definition or composition rules.

Answer 2

You're almost there -- your Monte Carlo simulations do in fact indicate the optimal solution. Here's a full proof:

If $n=1$, the conditions can't be satisfied. If $n=2$, the conditions are always satisfied, and so the optimum is $2/m$ when $a_1=a_2=m$. Otherwise, $a_1\leq m$ since $$a_1\leq \frac{a_1+\cdots+a_n}n=\frac{2m}n\leq m,$$ and so the only nontrivial condition is $a_n\geq m$.

Applying Cauchy-Schwarz gives $$\left(\sum_{i=1}^{n-1}\frac1{a_i}\right)\left(\sum_{i=1}^{n-1}a_i\right)\geq (n-1)^2,$$ and so $$\sum_{i=1}^n\frac1{a_i}\geq \frac{(n-1)^2}{2m-a_n}+\frac1{a_n}.$$ Equality is reached if and only if $a_1=\cdots=a_{n-1}=\frac{2m-a_n}{n-1}$. So, the minimum is reached by $$\min_{m\leq x\leq 2m}\left(\frac{(n-1)^2}{2m-x}+\frac1x\right).$$ Let this function be $f(x)$. We may compute that, for $m\leq x\leq 2m$, $$f'(x)=\frac{(n-1)^2}{(2m-x)^2}-\frac1{x^2}\geq \frac{(n-1)^2}{m^2}-\frac1{m^2}=\frac{n(n-2)}{m^2}>0,$$ and so $f(x)$ is minimized when $x=m$.

Answer 3

There can only be one value $\ge m$ else the sum would exceed $2m$. For similar reasons $a_n<2m$. So ignore $a_n$ and apply Lagrange Multipliers to the remaining terms.

All $a_i=(2m-a_n)/(n-1)$.

Plugging $a_n$ back in and using $m\le a_n<2m\implies \frac{1}{2m}<\frac{1}{a_n}<\frac{1}{m}$

$S_2=\sum{\frac{1}{a_i}}>\frac{(n-1)^2}{(2m-a_n)}+\frac{1}{a_n}>\frac{(n-1)^2}{(2m-a_n)}+\frac{1}{2m}$