# Proving upperbound using convexity

The original question is to prove

$$\frac{1}{n}\sum_{i=1}^n x_i \leq \log{(\frac{1}{n}\sum_{i=1}^n e^{x_i})} \leq \max_{1 \leq i \leq} x_i$$

I show that

$$x_{max} = \max_{1 \leq i \leq} x_i$$

$$\log{(\frac{1}{n}\sum_{i=1}^n e^{x_{max}})} =\max_{1 \leq i \leq} x_i$$

However I don't how to show the left inequality, the solution say this is trivial by the convexity of exponential function, what does that mean? I understand what convexity means but what does convexity have to do with the upper bound? You can easily have two convex functions that cross each other at one point, how will covexity help me

$$\exp{(\frac{1}{n}\sum_{i=1}^nx_i) } \leq \frac{1}{n}\sum_{i=1}^n e^{x_i}$$

• You take logs of both sides of the last equation you wrote down. You are nearly there. – Stephen Montgomery-Smith May 14 '14 at 1:36

The function $f(x) = \exp (x)$ has a positive second derivative for every $x$ and is convex.

Convexity can be used to prove your last assertion

$$\exp(\frac{1}{n}\sum_{i=1}^{n} x_i) \leq \frac{1}{n}\sum_{i=1}^{n} \exp(x_i)$$

A convex function has the property

$$f[(\lambda x_1 + (1-\lambda)x_2] \leq \lambda f(x_1) + (1-\lambda)f(x_2)$$

for $0 \leq \lambda \leq1$.

You can use Taylor's theorem to prove that a twice-differentiable function with a positive second derivative is convex.

This generalizes to yield your inequality.

If $f$ is convex then using $\lambda = 1/2$ we get

$$f[(x_1 + x_2)/2] \leq \ [f(x_1) + f(x_2)]/2$$ and we can extend this by induction to $n$ variables (Jensen inequality):

$$f(\frac{1}{n}\sum_{i=1}^{n} x_i) \leq \frac{1}{n}\sum_{i=1}^{n} f(x_i)$$

I will show how this is done for $n=3$.

By convexity,

$$f\Big(\frac{1}{3}x_1+\frac{1}{3}x_2+\frac{1}{3}x_3\Big) = f\Big[\frac{1}{3}x_1 + \frac{2}{3}\Big( \frac{x_2/3+x_3/3}{2/3}\Big) \leq \frac{1}{3}f(x_1) + \frac{2}{3}f\Big( \frac{x_2/3+x_3/3}{2/3}\Big)\Big] \leq \frac{1}{3}f(x_1) + \frac{2}{3}f (x_2/2+x_3/2) \leq \frac{1}{3}f(x_1)+\frac{1}{3}f(x_2)+\frac{1}{3}f(x_2)$$