Convexity of log to sum of exponentials

[Benjamin Biegel]

My question is:

the function f(x) = log(x) is concave

the function h(z) = log(sum(exp(g_i)) is convex, as long as the functions g_i are convex (the log to a sum of exponentials to convex functions)

How is the last true? The outer function log() is concave and nondecreasing, while the inner function is convex. There is no composition rule for this...

Thansk :)

Benjamin

[Rob Johnson]

In article <1757664510.93425.12786...@gallium.mathforum.org>,

Let D be a derivative in any particular direction. Then applying
the chain rule twice, we get

D^2 log(sum(exp(g_i)))

1
= D( ------------- sum(exp(g_i)Dg_i) )
sum(exp(g_i))

1
= - --------------- (sum(exp(g_i) Dg_i))^2
sum(exp(g_i))^2

1
+ ------------- sum(exp(g_i) (Dg_i)^2)
sum(exp(g_i))

1
+ ------------- sum(exp(g_i) D^2 g_i) [1]
sum(exp(g_i))

The third summand in [1] is positive since each g_i is convex, so we
only need to show that the sum of the first two summands is positive.
This is simply Jensen's inequality with the measure

exp(g_i)
m_i = ------------- [2]
sum(exp(g_i))

That is,

1
- --------------- (sum(exp(g_i) Dg_i))^2
sum(exp(g_i))^2

1
+ ------------- sum(exp(g_i) (Dg_i)^2)
sum(exp(g_i))

= - (sum(m_i Dg_i))^2

+ sum(m_i (Dg_i)^2)

>= 0 [3]

Since x^2 is convex.

Rob Johnson <r...@trash.whim.org>
take out the trash before replying
to view any ASCII art, display article in a monospaced font

[Dan Cass]

Note that for a single function g_1 we have
.. log( exp(g_1) ) = g_1, so that at least for one
function, the log part just undoes the exp part,
resulting in a convex function if g_1 was supposed convex.

This leads me to believe that after the sum is
taken of exp( g_i ), the taking of log of the sum
has little to do with the fact that log is concave,
but more to do with log being the inverse function to exp.

[Dan Cass]

The result holds for two functions.
Call them f and g (for your g_1 and g_2).
Then the second derivative of log( exp(f)+exp(g) )
has a denominator which is the square of a function,
while the numerator contains:
** two terms of the form f '' * positive
** two terms of the form g '' * positive
**three more terms which together factor as
[f' - g']^2 * exp(f) * exp(g).

The assumption that f and g are convex means that
the two second derivatives f '' and g '' are positive,
making the overall second derivative of
log(exp(f)+exp(g)) come out positive, so that the latter
is convex, given that f and g are each convex.

[Benjamin Biegel]

Ahh that is a great answer, many thanks for looking into this Dan! :)

[Dan Cass]

> > My question is:
> >
> > the function f(x) = log(x) is concave
> >
> > the function h(z) = log(sum(exp(g_i)) is convex,
> as
> > long as the functions g_i are convex (the log to a
> > sum of exponentials to convex functions)
> >
> > How is the last true? The outer function log() is
> > concave and nondecreasing, while the inner
> function
> > is convex. There is no composition rule for
> this...
> >
> > Thansk :)
> >
> > Benjamin
>

The following is a re-post with a typo fixed...
> The general case resembles the two-function case:
> Write w for sum(exp(g_i))
> Then the second derivative of log(w) has denominator
> w^2,
> and the numerator, after some algebra, is
> \sum_k (g_k)'' * exp(u_k) * w
> + \sum_{i<j} [g_i' - g_j']^2 * exp(g_i + g_j).
> Hence if each g_k is convex, so that the (g_k)'' are
> positive, then the second derivative of log(w) is
> positive, making log(w) convex as stated.

[Dan Cass]

The general case resembles the two-function case:

Write w for sum(exp(g_i))
Then the second derivative of log(w) has denominator w^2,
and the numerator, after some algebra, is
\sum_k (g_k)'' * exp(u_k) * w
+ \sum_{i<j} [g_i' - g_j']^2 * exp(g_i + g_j).

Hence if each g_k is convex, so that the (g_j)'' are

[lucky.t...@gmail.com]

Hi,
I am not sure about the exp(concave) function. Is it convex? Please see the link below which proves that the function is convex.