10
$\begingroup$

A function $f: \mathbb R^n \rightarrow \mathbb R$ is said to be concave if

$$\left(\forall x,y \in \mathbb{R}^n \right) \left( \forall \lambda \in [0,1] \right) \left(\lambda f(x) + (1-\lambda)f(y) \le f(\lambda x + (1- \lambda)y)\right)$$

In the case of the geometric mean function (defined below), how would we prove concavity?

$$f(x_1,\dots,x_n) := \left(\prod_{i=1}^n x_i \right)^\frac1n$$

I have been trying all day to find a proof, mostly by induction, but also considering the Hessian, which if always negative semidefinite implies concavity. Any tips, please?

$\endgroup$
1
  • 2
    $\begingroup$ Did you try applying $ln()$ to the arithmetic mean function ? $\endgroup$ Commented Jul 26, 2013 at 12:31

5 Answers 5

16
$\begingroup$

There may be a clever way to prove concavity without the Hessian, but I don't see one. So, here is the Hessian (I'm working under assumption $x_i>0$ for all $i$): $$D_{ij}f=\frac{f}{n^2}A \quad \text{where } \ A_{ij}= \begin{cases}(1-n)x_i^{-2} \quad &\text{ if }\ i=j \\ x_i^{-1}x_j^{-1} \quad &\text{ if }\ i\ne j \end{cases} \tag1 $$ Let $y_i=1/x_i$ to simplify notation. We are to prove that $v^TAv\le 0$ for every vector $v$. And indeed, $$v^TAv=\left(\sum_{i=1}^n y_iv_i\right)^2-n \sum_{i=1}^n y_i^2 v_i^2 \le 0\tag2$$ by the Cauchy-Schwarz inequality applied to $1\cdot (y_iv_i) $.

$\endgroup$
2
  • 1
    $\begingroup$ Is there any intuitive trick to derive the summation expression for $v^TAv$ directly from (1)? $\endgroup$
    – Barun
    Commented Sep 16, 2014 at 13:27
  • $\begingroup$ Very cool proof! I managed to generalize it to show all norms $p<1$ are concave and $p>1$ are convex: math.stackexchange.com/a/3782164/7072 $\endgroup$ Commented Aug 6, 2020 at 17:07
8
$\begingroup$

I was suggested this question while answering a duplicate. I'm cross-posting my proof here for the sake of future readers:

We are going to use the AM-GM inequality: $$\frac{a_1 + a_2+\cdots +a_n}{n} \ge (a_1a_2\ldots a_n)^{1/n}.$$

Applying AM-GM for $a_i = \frac{x_i}{\lambda x_i + (1 - \lambda)y_i}$, then for $a_i = \frac{y_i}{\lambda x_i + (1 - \lambda)y_i}$, we get:

\begin{align} \frac{f(x)}{f(\lambda x + (1 - \lambda)y)} = \left(\prod_{i=1}^n \frac{x_i}{\lambda x_i + (1 - \lambda)y_i} \right)^{1/n} &\le \frac{1}{n}\left(\sum_{i=1}^n \frac{x_i}{\lambda x_i + (1 - \lambda)y_i} \right),\\ \frac{f(y)}{f(\lambda x + (1 - \lambda)y)} =\left(\prod_{i=1}^n \frac{y_i}{\lambda x_i + (1 - \lambda)y_i} \right)^{1/n} &\le \frac{1}{n}\left(\sum_{i=1}^n \frac{y_i}{\lambda x_i + (1 - \lambda)y_i} \right). \end{align} Multiply the first inequality by $\lambda$, and the second by $(1 - \lambda)$, then sum up the two we get \begin{equation} \frac{\lambda f(x) + (1 - \lambda)f(y)}{f(\lambda x + (1 - \lambda)y)} \le 1. \end{equation} We are done.

$\endgroup$
1
  • $\begingroup$ very nice and elegant ! $\endgroup$ Commented Nov 19, 2020 at 15:18
1
$\begingroup$

Here is an apparently non-standard proof, involving no gradients or Hessians: http://www.cs.bgu.ac.il/~mlt142/CsWiki/Blogs/Post_Karyeh_55db5950bd339?format=standalone

$\endgroup$
1
  • $\begingroup$ You should post it here... $\endgroup$
    – Royi
    Commented Nov 2, 2015 at 23:22
1
$\begingroup$

Here is another proof that does not require the Hessian (for the weighted geometric mean). The argument relies on the following identity: $$ \prod_{k=1}^n x_k^{\lambda_k}=\inf_{y_1,\dots,y_n>0}\left(\sum_{k=1}^n \lambda_k\frac{x_k}{y_k}\right)\prod_{k=1}^n y_k^ {\lambda_k} $$ The inequality RHS$\geq$LHS follows from the AM-GM inequality, while LHS$\geq$RHS can be seen by taking $y_k=x_k$. Now it is well-known (and not hard to prove) that the infimum of a family of affine functions (or more generally concave ones) is again concave.

Note that we only used the two properties of $f$, namely, that $f$ is submultiplicative ($f(xy)\leq f(x)f(y)$), and bounded above by a concave function $g$ with $g(1)=1$.

$\endgroup$
0
$\begingroup$

I am not completely sure if I am answering what you really want to ask. You put the definition of concave but are asking the convexity of a function. You call it the arithmetic mean, while that one is usually called the geometric mean.

If it were convex,

$$f(t(1,2)+(1-t)(2,1))=f(t+2-2t,2t+1-t)=\sqrt{(2-t)(1+t)}\leq tf(1,2)+(1-t)f(2,1)=t\sqrt{2}+(1-t)\sqrt{2}=\sqrt{2},$$

which implies

$$2+t-t^2\leq2,$$

which is equivalent to

$$t-t^2=t(1-t)\leq0,$$

which is not true for $t\in(0,1)$.

By the way, it occurred to me that maybe you are putting together convexity and the mean, because you are trying to prove the inequality between the arithmetic and the geometric means using the convexity of some function. In that case, the function you should try to prove concave is $\ln(x)$. Then show that the concavity statement for $\ln(x)$ implies the inequality between the means, by recalling that you can evaluate $\ln$ on positive numbers.

$\endgroup$

You must log in to answer this question.

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