Logarithmically concave function

In convex analysis, a non-negative function f : RnR+ is logarithmically concave (or log-concave for short) if its domain is a convex set, and if it satisfies the inequality


    f(\theta x + (1 - \theta) y) \geq f(x)^{\theta} f(y)^{1 - \theta}

for all x,y ∈ dom f and 0 < θ < 1. If f is strictly positive, this is equivalent to saying that the logarithm of the function, log ∘ f, is concave; that is,


   \log  f(\theta x + (1 - \theta) y) \geq \theta \log f(x) + (1-\theta) \log f(y)

for all x,y ∈ dom f and 0 < θ < 1.

Examples of log-concave functions are the 0-1 indicator functions of convex sets (which requires the more flexible definition), and the Gaussian function.

Similarly, a function is log-convex if it satisfies the reverse inequality


    f(\theta x + (1 - \theta) y) \leq f(x)^{\theta} f(y)^{1 - \theta}

for all x,y ∈ dom f and 0 < θ < 1.

Properties

f''(x)=e^{-\frac{x^2}{2}} (x^2-1) \nleq 0
f(x)\nabla^2f(x) \preceq \nabla f(x)\nabla f(x)^T,[1]
i.e.
f(x)\nabla^2f(x) - \nabla f(x)\nabla f(x)^T is
negative semi-definite. For functions of one variable, this condition simplifies to
f(x)f''(x) \leq (f'(x))^2

Operations preserving log-concavity

\log\,f(x) + \log\,g(x) = \log(f(x)g(x))
is concave, and hence also f g is log-concave.
g(x)=\int f(x,y) dy
is log-concave (see Prékopa–Leindler inequality).
(f*g)(x)=\int f(x-y)g(y) dy = \int h(x,y) dy
is log-concave.

Log-concave distributions

Log-concave distributions are necessary for a number of algorithms, e.g. adaptive rejection sampling.

As it happens, many common probability distributions are log-concave. Some examples:[2]

Note that all of the parameter restrictions have the same basic source: The exponent of non-negative quantity must be non-negative in order for the function to be log-concave.

The following distributions are non-log-concave for all parameters:

Note that the cumulative distribution function (CDF) of all log-concave distributions is also log-concave. However, some non-log-concave distributions also have log-concave CDF's:

The following are among the properties of log-concave distributions:

Notes

  1. Stephen Boyd and Lieven Vandenberghe, Convex Optimization (PDF) p.105
  2. See Mark Bagnoli and Ted Bergstrom (1989), "Log-Concave Probability and Its Applications", University of Michigan.
  3. 1 2 András Prékopa (1971), "Logarithmic concave measures with application to stochastic programming". Acta Scientiarum Mathematicarum, 32, pp. 301–316.

References

See also

This article is issued from Wikipedia - version of the Thursday, March 17, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.