Minimizing Sum of Reciprocals

Question

Find the minimum value, in terms of $k$ of $\frac{1}{x_1}+…+\frac{1}{x_n}$ if $x_1^2+x_2^2+…+x_n^2=n$ and $x_1+x_2+…+x_n=k$, where $\sqrt{n} < k \leq n$.

I tried the am-hm, but how to relate with the sum of squares?

Answer 1

Given that $\sum\limits_{j=1}^nx_j^2=n$ and $\sum\limits_{j=1}^nx_j=k$ we want to minimize $\sum\limits_{j=1}^n\dfrac1{x_j}$.

That is, we need to find $x_j$ so that for all $\delta x_j$ where $\sum\limits_{j=1}^nx_j\,\delta x_j=0$ and $\sum\limits_{j=1}^n\delta x_j=0$, we also have $\sum\limits_{j=1}^n\dfrac{\delta x_j}{x_j^2}=0$.

Orthogonality implies that there exist $a$ and $b$ so that for all $j$, $ax_j+b=x_j^{-2}$. Thus, $$ ax_j^3+bx_j^2-1=0\tag{1} $$ This implies there are only $3$ distinct values for $x_j$, say $v_1$, $v_2$, and $v_3$.

The equations $\sum\limits_{j=1}^nx_j^2=n$ and $\sum\limits_{j=1}^nx_j=k$ imply that $$ \begin{bmatrix} v_1^2&v_2^2&v_3^2\\ v_1&v_2&v_3\\ 1&1&1 \end{bmatrix} \begin{bmatrix} m_1\\m_2\\m_3 \end{bmatrix} = \begin{bmatrix} n\\k\\n \end{bmatrix}\tag{2} $$ where $m_1$, $m_2$, and $m_3$ are the counts of each value.

Since the coefficient of $x_j$ in $(1)$ is $0$ (and the constant term is not $0$), Vieta's Formulas say that $$ \frac1{v_1}+\frac1{v_2}+\frac1{v_3}=0\tag{3} $$ This means that, for an interior critical point, one of the $v_j$ must be negative. Thus, the critical point must be on an edge. Let's consider the edge where $m_3=0$. In that case, we have $$ \begin{bmatrix} v_1^2&v_2^2\\ v_1&v_2\\ 1&1 \end{bmatrix} \begin{bmatrix} m_1\\m_2 \end{bmatrix} = \begin{bmatrix} n\\k\\n \end{bmatrix}\tag{4} $$ Let $m_1=m$, then the bottom equation implies $m_2=n-m$.

Let $v_1=v$, then the middle equation implies $v_2=\frac{k-mv}{n-m}$.

The top equation implies $$ \begin{align} &mv^2+(n-m)\left(\frac{k-mv}{n-m}\right)^2=n\\ &\implies mnv^2-2kmv+(mn+k^2-n^2)=0\tag{5} \end{align} $$ We can solve $(5)$ for $v$: $$ v=\frac{km\pm\sqrt{m(n-m)(n^2-k^2)}}{mn}\tag{6} $$ Using $(6)$, we get $$ \begin{align} &\frac mv+\frac{(n-m)^2}{k-mv}\\ &=\frac{nm^2}{km\pm\sqrt{m(n-m)(n^2-k^2)}}+\frac{n(n-m)^2}{k(n-m)\mp\sqrt{m(n-m)(n^2-k^2)}}\tag{7} \end{align} $$ Note that $(7)$ gives the same result if we use the upper choice of $\pm$ and $\mp$ as when we use the lower choice and substitute $m\mapsto n-m$. Thus, we can choose the $+$ in each $\pm$ and the $-$ in each $\mp$.

Taking the derivative of $(7)$ yields $$ \frac{n^4(n^2-k^2)\sqrt{m(n-m)(n^2-k^2)}}{2\left(km+\sqrt{m(n-m)(n^2-k^2)}\right)^2\left(k(n-m)-\sqrt{m(n-m)(n^2-k^2)}\right)^2}\tag{8} $$ Since $(8)$ is always positive, $(7)$ must be increasing. Thus, there is no internal critical point, so the critical point must be an edge. Because of a division by $0$, the "solution" for $m=0$, which is $x_j=\frac kn$, fails to satisfy $(4)$. Thus, we choose the closest we can, which is $m=1$. This gives the minimum to be $$ \frac{n(n-1)}{k-\sqrt{\frac{n^2-k^2}{n-1}}}+\frac{n}{k+\sqrt{(n-1)(n^2-k^2)}}\tag{9} $$ attained with $x_1=\dfrac kn+\sqrt{(n-1)\left(1-\frac{k^2}{n^2}\right)}$ and $x_j=\dfrac kn-\sqrt{\frac1{n-1}\left(1-\frac{k^2}{n^2}\right)}$ for $2\le j\le n$.

Answer 2

Checking the case $n = 2$

First condition: $$ g(x,y) = x + y = k \iff y = - x + k $$

Second condition: $$ h(x,y) = x^2 + y^2 = 2 \iff y = \pm \sqrt{2 - x^2} $$

This gives \begin{align} 2 &= x^2 + (-x + k)^2=2 x^2 -2kx + k^2 \iff \\ 1 &= x^2 - kx + k^2/2 = (x - k/2)^2 + k^2/4 \iff \\ x &= \frac{k\pm\sqrt{4-k^2}}{2} \quad \wedge \\ y &= \frac{-k\mp\sqrt{4-k^2}}{2} + k = \frac{k\mp\sqrt{4-k^2}}{2} \end{align} We got 2 points or 1 point ($k=2$) which satisfy the conditions, which agrees with an intersection of a line ($g=k$) and a circle ($h=2$). Their coordinates were expressed in terms of $k$. Inserting those points into $f$ we get: \begin{align} f(x,y) &= \frac{1}{x} + \frac{1}{y} \\ &= \frac{2}{k\pm\sqrt{4-k^2}} + \frac{2}{k\mp\sqrt{4-k^2}} \\ &= \frac{4k}{k^2 - (4 - k^2)} \\ &= \frac{2k}{k^2 - 2} \\ &= F(k) \end{align} This function is constant regarding $x$ and $y$, which includes the minimum.

(in progress)

The Lagrange function is $$ L(x,\lambda, \mu) = f(x) + \lambda \left( g(x) - k \right) + \mu \left( h(x) - n \right) $$ Gradient components are \begin{align} \frac{\partial L}{\partial x_j} &= -\frac{1}{x_j^2} + \lambda + 2 \mu x_j \quad (j\in\{1,\ldots,n\}) \\ \frac{\partial L}{\partial\lambda} &= g(x) - k \\ \frac{\partial L}{\partial\mu} &= h(x) - n \end{align} At critical points $x^*$ the above components vanish. So $$ f(x^*) = \sum_i \frac{1}{x^*_i} = \sum_i \lambda x^*_i + 2 \mu (x^*_i)^2 = \lambda k + 2 \mu n $$ The question is how to calculate $\lambda$ and $\mu$. We have $n+2$ equations with $n+2$ unknowns, so there is a chance for a unique solution $(x, \lambda, \mu)$, but so far I found no way to extract it.

Answer 3

The question does not constrain $x_i, i=1,\ldots,n$ under any subset of $\mathbb{R}^n$. Thus, I will solve it for $\mathbf{x} \in \mathbb{R}^n$.

Let $f_n(\mathbf{x}) = \frac{1}{x_1}+…+\frac{1}{x_n}$ be the cost function. Consider $n > 1$ because $n=1$ is meaningless (there is no $k$).

Case $n=2$:

The straight line $x_1 + x_2 = k$ intercepts the circle $x_1^2+x_2^2 = 2$ at most two points, says

$$(x_1,x_2) = \left(\frac{k}{2} \pm \frac{\sqrt{4-k^2}}{2}, \frac{k}{2} \mp \frac{\sqrt{4-k^2}}{2}\right).$$Hence, the minimal value is given by

$$ f_2(x_1^{\star},x_2^{\star}) = \frac{2k}{k^2-2}.$$

Case $n\geq 3$:

Notice that if $k=n$, the hyperplane $x_1 + x_2 + \cdots + x_n = n$ is tangent to the hypersphere $x_1^2 + x_2^2 + \cdots + x_n^2 = n$ at the point $x_1 = \cdots =x_n= 1$, which is the only solution to the problem in that case.

If $\sqrt{n} < k < n$, the hyperplane $x_1 + x_2 + \cdots + x_n = k$ intercepts the hypersphere at infinitely many points.

Now, let $x_i = \epsilon, $ for some $i \in \{1,\ldots , n\}$ and $ \epsilon < 0$. For $|\epsilon|$ small enough, there always exists $x_1, \ldots, x_{i-1},x_{i+1}, \ldots x_{n}$ finite satisfying both constraints $$\sum \limits_{j\neq i}x_j^2 =n-\epsilon^2 $$ $$ \sum \limits_{j\neq i}x_j =k-\epsilon. $$

If $\epsilon \rightarrow 0$, then $f_n(\mathbf{x}) \rightarrow -\infty$. Thus, no global minimum is reached in that case.

Conclusions:

(1) The problem has at most two global minimum only for $n=2$;

(2) The problem has a single global minimum if and only if $k = n \geq 2$. In this case, we have a hyperplane tangent to the hypersphere and $f_n(\mathbf{x}^{\star}) = n$.