2
$\begingroup$

How can we prove that the following function (harmonic mean) is concave?

$$f (x_1, x_2, \dots, x_n) := \frac{n}{\displaystyle\sum_{i=1}^n \frac{1}{x_i}}$$

Because this is not a function of one variable, I am not sure how to do so.

$\endgroup$
2
  • $\begingroup$ You can for example prove that the set of points below the graph of $f$ (that is $\{x\in\mathbb{R}^{n+1}~:~ x_{n+1}\leq f(x_1,\ldots,x_n) \}$ is a convex set. $\endgroup$ – Michal Adamaszek Oct 28 '19 at 9:49
  • $\begingroup$ In the case $n=2$ the proof is pretty simple: we have $$ \text{AM}(x_1,x_2)-\text{HM}(x_1,x_2) = \frac{(x_1-x_2)^2}{2(x_1+x_2)} $$ and the RHS is the product of two positive and convex functions ($z^2$ and $\frac{1}{2w}$) of the independent variables $z=(x_1-x_2)$ and $w=(x_1+x_2)$. On the other hand the extension to $n>2$ does not seem to be straightforward... $\endgroup$ – Jack D'Aurizio Oct 28 '19 at 19:18
1
$\begingroup$

$\text{HM}(x_1,\ldots,x_n)$ is quite blatantly a continuous function on $\mathbb{R}_+^n$, so its concavity follows from its midpoint-concavity, i.e. from the inequality

$$ \frac{1}{\sum_{k=1}^{n}\frac{1}{x_k+y_k}} \geq \frac{1}{\sum_{k=1}^{n}\frac{1}{x_k}}+\frac{1}{\sum_{k=1}^{n}\frac{1}{y_k}} $$ which is the super-additivity of the harmonic mean: see §14 here. Up to a change of variables, this is equivalent to the following inequality for positive variables $$ \sum X_k \sum Y_k \geq \sum (X_k+Y_k) \sum \frac{X_k Y_k}{(X_k + Y_k)} \tag{A}$$ which can be proved by applying Lagrange multipliers to the determination of $$ \max_{\substack{\sum X_k = A \\ \sum Y_k = B}}\sum \frac{X_k Y_k}{X_k + Y_k}.$$ Since $\frac{\partial}{\partial X_k}\left( \frac{X_k Y_k}{X_k + Y_k}\right) = \left(\frac{Y_k}{X_k+Y_k}\right)^2 $ the maximum $\frac{AB}{A+B}$ is achieved when $\{X_k\}=\lambda \{Y_k\}$. In a more elementary way, the difference between the LHS and the RHS of $(A)$ is given by the sum over $i\neq j$ of $\frac{1}{(X_i+Y_i)(X_j+Y_j)}$ times

$$\left[(X_i+Y_i)(X_j+Y_j)(X_i Y_j+X_j Y_i)\right]-\left[X_j Y_j(X_i+Y_i)^2+X_i Y_i(X_j+Y_j)^2\right]$$ which can be checked to be the square of $Y_i X_j - X_i Y_j$.

$\endgroup$
1
$\begingroup$

Here is a proof using the Hessian, inspired by https://math.stackexchange.com/a/452822/7072 . Let $$f(x)=\frac1{\sum_i x_i^{-1}},$$ Then the Hessian is given by $$D_{ij}f=2 f^3 A \quad \text{where } \ A_{ij}= \begin{cases}-x_i^{-3}\sum_{k\neq i}x_k^{-1} \quad &\text{ if }\ i=j \\ x_i^{-2}x_j^{-2} \quad &\text{ if }\ i\ne j \end{cases}$$ We are to prove that $v^TAv\le 0$ for every vector $v$. (We are assuming that $f(x)$ is non-negative.) We find $$v^TAv=\left(\sum_{i=1}^n \frac{v_i}{x_i^2}\right)^2- \sum_{i=1}^n \frac{v_i^2}{x_i^3}\sum_j\frac1{x_i},$$ which is $\le 0$ by the Cauchy-Schwarz inequality applied to $(\frac{v_i}{x_i^{3/2}})\cdot (\frac{1}{x_i^{1/2}}) $.

My understanding from http://groups.uni-paderborn.de/fg-qi/courses/CMSC691/2016/assignments/CMSC691_Fall2016_A2.pdf is that every power mean is concave for $p<1$. I suppose it makes sense the proofs are somewhat similar.


I was curious about what happens in the general $p$ case. In this case $f(x) = \left(\sum_i x_i^p\right)^{1/p}$ and we get $$D_{ij}f=\frac1{1-p} f^{1-2p} A \quad \text{where } \ A_{ij}= \begin{cases}-x_i^{p-2}\sum_{k\neq i}x_k^p \quad &\text{ if }\ i=j \\ x_i^{p-1}x_j^{p-1} \quad &\text{ if }\ i\ne j \end{cases} $$ Again, we find $$v^TAv=\left(\sum_{i=1}^n v_i x_i^{p-1}\right)^2- \sum_{i=1}^n v_i^2 x_i^{p-2}\sum_jx_i^p,$$ which is $\le 0$ by the Cauchy-Schwarz inequality applied to $( v_i x^{p/2-1})\cdot (x_i^{p/2}) $.

Note the same proof shows convexity for $p>1$ when the factor $\frac1{1-p}$ is positive.

$\endgroup$
2
  • $\begingroup$ I cannot follow how you obtained Hessian in the general form but the result is wrong because at least for $0<p<1$, the p norm is neither convex nor concave: math.stackexchange.com/questions/2819671/… $\endgroup$ – Piyush Singh Jan 20 at 11:12
  • $\begingroup$ @Piyush right, it should say on the domain of positive numbers. $\endgroup$ – Thomas Ahle Jan 20 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.