7
$\begingroup$

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

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

In the case of the arithmetic mean function $f(x_1, ...,x_n) = (x_1 ...x_n)^{1/n}$ how would we prove convexity? I have been trying all day to find a proof, mostly by induction, but also considering the Hessian, which if always negative semidefinite implies convexity. Any tips?

$\endgroup$
  • 1
    $\begingroup$ Did you try applying $ln()$ to the arithmetic mean function ? $\endgroup$ – Samatix Jul 26 '13 at 12:31
10
$\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$
  • 1
    $\begingroup$ Is there any intuitive trick to derive the summation expression for $v^TAv$ directly from (1)? $\endgroup$ – Barun Sep 16 '14 at 13:27
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$
0
$\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$
  • $\begingroup$ You should post it here... $\endgroup$ – Royi Nov 2 '15 at 23:22

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.