8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Composition rules for preserving convexity. But it didn't work $\endgroup$ – Finley Sep 6 '17 at 4:18
  • $\begingroup$ What about using induction? $\endgroup$ – Sergio Enrique Yarza Acuña Sep 6 '17 at 4:53
  • $\begingroup$ A possible duplicate of math.stackexchange.com/questions/2416837/… $\endgroup$ – Math Lover Sep 6 '17 at 4:58
  • $\begingroup$ @MathLover : It seems that I need to compute the Hessian of $f(x)$ that I tried to avoid before. $\endgroup$ – Finley Sep 6 '17 at 5:10
  • $\begingroup$ @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. $\endgroup$ – Math Lover Sep 6 '17 at 5:13
7
$\begingroup$

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)$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How to prove Jensen's inequality holds when $0 \le t \le 1$ more than $t=1/2$? $\endgroup$ – Finley Sep 6 '17 at 6:10
  • $\begingroup$ According to definition of function convexity. $f(x)$ is convex if and only if Jensen's inequality holds for any $t \in [0,1]$ $\endgroup$ – Finley Sep 6 '17 at 6:13
  • $\begingroup$ 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 $\endgroup$ – Satish Ramanathan Sep 6 '17 at 6:26
  • $\begingroup$ (+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. $\endgroup$ – Sangchul Lee Sep 6 '17 at 6:37
  • $\begingroup$ 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})$? $\endgroup$ – user1551 Sep 6 '17 at 6:49
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mong H. Ng Sep 8 at 23:48

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.