Convexity of log to sum of exponentials
in [Math]
|
From: Benjamin Biegel on 8 Jul 2010 23:41 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
From: Rob Johnson on 9 Jul 2010 05:51 In article <1757664510.93425.1278661332577.JavaMail.root(a)gallium.mathforum.org>, Benjamin Biegel <benjamin(a)biegel.nu> wrote: >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... 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 <rob(a)trash.whim.org> take out the trash before replying to view any ASCII art, display article in a monospaced font
From: Dan Cass on 9 Jul 2010 08:02 > 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 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.
From: Dan Cass on 9 Jul 2010 08:24 > 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 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.
From: Benjamin Biegel on 9 Jul 2010 08:28
Ahh that is a great answer, many thanks for looking into this Dan! :) |