# Why log-of-sum-of-exponentials $f(x)=\log\left(\sum\limits_{i=1}^n e^ {x_i}\right)$ is a convex function for $x \in R^n$

How to prove $f(x)=\log(\sum_{i=1}^n e^{x_i})$ is a convex function?

EDIT1: for above function $f(x)$, following inequalities hold:

$$\max\{x_1,x_2,...,x_n\} \le f(x) \le \max\{x_1,x_2,...,x_n\}+\log n$$

and I have tried proving its convexity via definition of a convex function with above inequalities. But that didn't work.

EDIT2: I have posted my answers below.

• Composition rules for preserving convexity. But it didn't work – Finley Sep 6 '17 at 4:18
• What about using induction? – Sergio Enrique Yarza Acuña Sep 6 '17 at 4:53
• A possible duplicate of math.stackexchange.com/questions/2416837/… – Math Lover Sep 6 '17 at 4:58
• @MathLover : It seems that I need to compute the Hessian of $f(x)$ that I tried to avoid before. – Finley Sep 6 '17 at 5:10
• @Finley At this moment, I can't think of any other way to prove that the function is convex. The individual entries of the Hessian matrix are given in math.stackexchange.com/questions/2416837/…. A proof is also given based on the C-S inequality. – Math Lover Sep 6 '17 at 5:13

Proof:

Let $u_i=e^ {x_i} ,v_i=e^ {y_i}$. So $f(\theta x+(1-\theta)y)=log(\sum_ {i=1}^n e^{\theta x_i + (1-\theta)y_i})=log(\sum_ {i=1}^n u_i^ \theta v_i^{(1-\theta)})$

From Hölder's inequality:

$$\sum_ {i=1}^n x_iy_i \le (\sum_ {i=1}^n|x_i|^p)^{\frac{1}{p}} \cdot (\sum_ {i=1}^n|x_i|^q)^{\frac{1}{q}}$$ where $1/p+1/q=1$.

Applying this inequality to $f(\theta x+(1-\theta)y)$: $$log(\sum_ {i=1}^n u_i^ \theta v_i^{(1-\theta)}) \le log[(\sum_ {i=1}^n u_i^ {\theta \cdot \frac{1}{\theta}})^ \theta \cdot (\sum_ {i=1}^n v_i^ {1-\theta \cdot \frac{1}{1-\theta}})^ {1-\theta}]$$ Right formula can be reduced to:

$$\theta log\sum_ {i=1}^n u_i+(1-\theta)log\sum_ {i=1}^n v_i$$

Here I regard $\theta$ as $\frac{1}{p}$ and $1-\theta$ as $\frac{1}{q}$.

So I achieve that $f(\theta x+(1-\theta)y) \le \theta f(x) + (1-\theta)f(y)$.

Another way to prove the convexity of this function is to use the Jensen's Inequality which states that a function is convex if and only if

$$f(tX+(1-t)Y) \le t f(X) + (1-t)f(Y)$$

Now let $X$ be represented by the vector $({X_1, X_2, X_3,... X_n})$,

and let $Y$ be represented by the vector $({Y_1, Y_2, Y_3,... Y_n})$

Let $t = \dfrac{1}{2}$

$$f(tX+(1-t)Y) = \log\left(\sum_{i=1}^{n} e^{\frac{X_i+Y_i}{2}}\right)$$

$$\text{RHS} = \frac{1}{2} \log\left(\sum_{i = 1}^{n} e^{X_i}\right)+ \frac{1}{2} \log\left(\sum_{i = 1}^{n} e^{Y_i}\right)$$

$$\text{RHS} = \frac{1}{2} \log\left(\sum_{i = 1}^{n} e^{X_i}\sum_{i = 1}^{n} e^{Y_i}\right)$$

RHS contains more cross product terms than the LHS thus making it larger than LHS and hence the function is convex.

• How to prove Jensen's inequality holds when $0 \le t \le 1$ more than $t=1/2$? – Finley Sep 6 '17 at 6:10
• According to definition of function convexity. $f(x)$ is convex if and only if Jensen's inequality holds for any $t \in [0,1]$ – Finley Sep 6 '17 at 6:13
• what t=(0,1) suggests is that you are taking a point in between X and Y vector. For any value of t between two point would range from 0-1. It not only applies for t= .5 but also any t within (0,1) which is essentially what you want – Satish Ramanathan Sep 6 '17 at 6:26
• (+1) It is also a consequence of CS-inequality: $$\sum_{i=1}^{n} e^{X_i/2}e^{Y_i/2} \leq \left( \sum_{i=1}^{n} e^{X_i} \right)^{1/2}\left( \sum_{i=1}^{n} e^{Y_i} \right)^{1/2}$$ This suggests that for general $t \in [0, 1]$ the same proof works by using Hölder's inequality instead. – Sangchul Lee Sep 6 '17 at 6:37
• I don't follow. Why is $\log(\sum_{i=1}^{n}e^{\frac{X_i+Y_i}2})=\frac12\log(\sum_{i=1}^{n}e^{X_i})+\log(\sum_{i=1}^ne^{Y_i})$? – user1551 Sep 6 '17 at 6:49

For a multivariate function to be convex, it's equivalent to show that its Hessian matrix is positive semi-definite. That is, you can calculate $$\nabla^2 f(\mathbf{x})$$ here and show it is positive semi-definite.

This can be proved using Cauchy Schwarz inequality as shown here.

• If anyone doesn't understand how CS-inequality is applied at the end of the linked slide, Boyd's book section 3.1.5 has a proof on this as well. – Mong H. Ng Sep 8 at 23:48