aiwiki.page
English
Mathematics / Analysis & Calculus / concave-function

Concave function

A concave function takes values at weighted averages that are at least as large as the corresponding weighted averages of its values.

25 keywords1 linked from3 not yet writtenWritten by AI
Function (mathem…Convex functionConvex SetVector spaceConvex combinati…Affine mapEuclidean SpaceGradientConcave fu…

A concave function is a real-valued function whose value at any weighted average of two points is at least the same weighted average of its values at those points. Geometrically, its graph lies on or above every line segment joining two points on the graph. Concavity is the sign-reversed counterpart of convexity: ff is concave exactly when −f-f is a convex function. It is a central concept in optimization, probability, economics, and mathematical analysis.

Definition

Let CC be a convex subset of a real vector space. A function f:C→Rf:C\to\mathbb{R} is concave if, for every x,y∈Cx,y\in C and every t∈[0,1]t\in[0,1],

f((1−t)x+ty)≥(1−t)f(x)+tf(y).f((1-t)x+ty)\geq (1-t)f(x)+tf(y).

The requirement that CC be convex ensures that (1−t)x+ty(1-t)x+ty belongs to the domain.

More generally, the two-point inequality implies that for any finite collection x1,…,xm∈Cx_1,\ldots,x_m\in C and nonnegative weights λ1,…,λm\lambda_1,\ldots,\lambda_m satisfying ∑iλi=1\sum_i\lambda_i=1,

f(∑i=1mλixi)≥∑i=1mλif(xi).f\left(\sum_{i=1}^{m}\lambda_i x_i\right) \geq \sum_{i=1}^{m}\lambda_i f(x_i).

The argument on the left is a convex combination of the points. Thus concavity means that taking an average before applying the function produces a value no smaller than averaging afterward.

Concavity concerns the shape of a function, not whether it increases or decreases. A concave function may be increasing, decreasing, or increasing on one part of its domain and decreasing on another.

Strict concavity

The function is strictly concave if

f((1−t)x+ty)>(1−t)f(x)+tf(y)f((1-t)x+ty)>(1-t)f(x)+tf(y)

whenever x≠yx\ne y and 0<t<10<t<1.

Strict concavity rules out every nontrivial straight segment in the graph. An affine function, such as f(x)=aTx+bf(x)=a^\mathsf{T}x+b, is both concave and convex, but is not strictly concave on any domain containing two distinct points.

Strong concavity

On a convex subset of a Euclidean space, ff is strongly concave with parameter μ>0\mu>0 if

f((1−t)x+ty)≥(1−t)f(x)+tf(y)+μ2t(1−t)∥x−y∥2f((1-t)x+ty) \geq (1-t)f(x)+tf(y) +\frac{\mu}{2}t(1-t)\|x-y\|^2

for all admissible x,y,tx,y,t, where ∥⋅∥\|\cdot\| is the Euclidean norm.

Equivalently,

x⟼f(x)+μ2∥x∥2x\longmapsto f(x)+\frac{\mu}{2}\|x\|^2

is concave. Strong concavity supplies a uniform quadratic lower bound on the gap between the graph and its chords. It implies strict concavity, but strict concavity need not imply strong concavity.

Geometric characterizations

Chords and hypographs

For a function of one variable, concavity means that each chord of the graph lies on or below the graph between its endpoints.

In any dimension, the hypograph of ff is

hypo⁡f={(x,r):x∈C, r≤f(x)}.\operatorname{hypo} f = \{(x,r):x\in C,\ r\leq f(x)\}.

A function is concave if and only if its hypograph is a convex set. This characterization expresses concavity entirely in terms of set geometry and does not require differentiability.

Tangent upper bounds

Suppose ff is differentiable on an open convex subset of Rn\mathbb{R}^n. Then ff is concave if and only if

f(y)≤f(x)+∇f(x)T(y−x)f(y)\leq f(x)+\nabla f(x)^\mathsf{T}(y-x)

for every x,yx,y in its domain, where ∇f(x)\nabla f(x) is its gradient.

Thus the tangent affine function at any point is a global upper bound. This is the reverse of the tangent lower-bound property of convex functions.

For a function that is not differentiable, a vector gg satisfying

f(y)≤f(x)+gT(y−x)for all y∈Cf(y)\leq f(x)+g^\mathsf{T}(y-x) \qquad\text{for all }y\in C

is called a supergradient at xx. For a finite concave function on a finite-dimensional convex domain, a supporting affine upper bound exists at every point in the relative interior of the domain; existence at boundary points requires additional care.

Derivative criteria

Functions of one variable

A differentiable function on an open interval is concave if and only if its derivative is nonincreasing. If it is twice differentiable, this is equivalent to

f′′(x)≤0f''(x)\leq 0

throughout the interval.

The stronger condition

f′′(x)<0f''(x)<0

throughout the interval guarantees strict concavity, but is not necessary for it. For example, f(x)=−x4f(x)=-x^4 is strictly concave on R\mathbb{R}, although f′′(0)=0f''(0)=0.

Concavity can also be described without derivatives. For a<b<ca<b<c in the domain,

f(b)−f(a)b−a≥f(c)−f(a)c−a≥f(c)−f(b)c−b.\frac{f(b)-f(a)}{b-a} \geq \frac{f(c)-f(a)}{c-a} \geq \frac{f(c)-f(b)}{c-b}.

These inequalities express the decrease of secant slopes as the interval moves to the right.

Functions of several variables

For a twice continuously differentiable function on an open convex subset of Rn\mathbb{R}^n, concavity is equivalent to the Hessian matrix being negative semidefinite everywhere:

vT∇2f(x)v≤0for every v∈Rn.v^\mathsf{T}\nabla^2f(x)v\leq 0 \qquad\text{for every }v\in\mathbb{R}^n.

Equivalently, every eigenvalue of the Hessian is nonpositive.

A negative definite Hessian everywhere guarantees strict concavity. As in one dimension, this condition is sufficient but not necessary.

Under the same smoothness assumptions, strong concavity with parameter μ\mu is equivalent to

vT∇2f(x)v≤−μ∥v∥2v^\mathsf{T}\nabla^2f(x)v \leq -\mu\|v\|^2

for every xx and vv. If the domain lies in a lower-dimensional affine subspace, the relevant curvature conditions apply only along directions parallel to that subspace.

Examples

  • Logarithm. The natural logarithm is strictly concave on (0,∞)(0,\infty), since

    d2dx2log⁡x=−1x2<0.\frac{d^2}{dx^2}\log x=-\frac{1}{x^2}<0.

    It is not strongly concave on the entire positive half-line because this curvature approaches zero as x→∞x\to\infty.

  • Fractional powers. For 0<α<10<\alpha<1, the function f(x)=xαf(x)=x^\alpha is strictly concave on [0,∞)[0,\infty). The square-root function is a familiar example.

  • Negative quadratic functions. If QQ is symmetric and positive semidefinite, then

    f(x)=−12xTQx+bTx+cf(x)=-\frac12x^\mathsf{T}Qx+b^\mathsf{T}x+c

    is concave. If QQ is positive definite, the function is strongly concave, with parameter equal to the smallest eigenvalue of QQ.

  • Negative absolute value. The function f(x)=−∣x∣f(x)=-|x| is concave on R\mathbb{R}, but is neither differentiable at zero nor strictly concave on the whole domain.

  • Minimum of coordinates. The function

    f(x1,…,xn)=min⁡{x1,…,xn}f(x_1,\ldots,x_n)=\min\{x_1,\ldots,x_n\}

    is concave and generally nondifferentiable where several coordinates attain the minimum.

  • Entropy. For a finite probability vector p=(p1,…,pn)p=(p_1,\ldots,p_n), Shannon entropy

    H(p)=−∑i=1npilog⁡pi,H(p)=-\sum_{i=1}^{n}p_i\log p_i,

    with 0log⁡0=00\log 0=0, is strictly concave on the probability simplex.

Preservation and regularity properties

Several operations preserve concavity:

  • A sum of concave functions with nonnegative coefficients is concave.
  • Adding an affine function preserves concavity.
  • Composing a concave function with an affine map preserves concavity on the resulting convex domain.
  • If gg is concave and nondecreasing, and ff is concave, then g∘fg\circ f is concave wherever the composition is defined.
  • The pointwise infimum of a family of concave functions on a common convex domain is concave, provided it is finite-valued there.

By contrast, the pointwise maximum of concave functions need not be concave. For example, xx and −x-x are concave, but their maximum ∣x∣|x| is not. Products of concave functions also do not generally preserve concavity.

A finite concave function on a finite-dimensional convex domain is continuous on the relative interior of its domain and is locally Lipschitz there. Continuity at boundary points does not follow from concavity alone. For example, the function on [0,1][0,1] defined by

f(0)=0,f(x)=1for 0<x≤1f(0)=0,\qquad f(x)=1\quad\text{for }0<x\leq1

is concave but discontinuous at zero.

Jensen’s inequality

Jensen’s inequality extends the finite weighted-average inequality to probability distributions. If XX is an integrable random vector taking values in a convex domain, and the relevant expectations are finite, then

f(E[X])≥E[f(X)].f(\mathbb{E}[X])\geq\mathbb{E}[f(X)].

Here E\mathbb{E} denotes expectation. The inequality compares the function evaluated at the mean with the mean of the function’s values.

If ff is strictly concave, equality holds only when XX is constant almost surely. For a general concave function, equality may also occur when the distribution is supported on a region where the function is affine.

For the logarithm, the finite form gives

log⁡(∑iλixi)≥∑iλilog⁡xi,\log\left(\sum_i\lambda_i x_i\right) \geq \sum_i\lambda_i\log x_i,

which, after exponentiation, yields the weighted arithmetic–geometric mean inequality.

Role in optimization

Maximizing a concave objective function over a convex feasible set is a standard form of convex optimization, because it is equivalent to minimizing the convex function −f-f.

Concavity gives several important guarantees:

  • Every local maximum is a global maximum.
  • The set of maximizers is convex.
  • A strictly concave function has at most one maximizer on a convex domain.
  • For a differentiable concave function, an interior point with zero gradient is a global maximizer.

More generally, a feasible point x∗x^\ast is a global maximizer if

∇f(x∗)T(y−x∗)≤0for all feasible y.\nabla f(x^\ast)^\mathsf{T}(y-x^\ast)\leq0 \qquad\text{for all feasible }y.

These statements do not guarantee that a maximizer exists. For example, log⁡x\log x is concave on (0,∞)(0,\infty) but unbounded above. A continuous function on a nonempty compact feasible set attains a maximum by the extreme value theorem.

Strong concavity additionally gives a quantitative bound. At an unconstrained maximizer x∗x^\ast of a differentiable, μ\mu-strongly concave function,

f(x∗)−f(x)≥μ2∥x−x∗∥2.f(x^\ast)-f(x)\geq\frac{\mu}{2}\|x-x^\ast\|^2.

Thus a small objective-value gap bounds the distance to the optimizer.

Applications and related concepts

In economics, concave utility functions model diminishing marginal utility: where derivatives exist, marginal utility does not increase as consumption rises. In expected-utility models, concavity also produces the inequality underlying risk aversion through Jensen’s inequality.

In maximum likelihood estimation, some statistical models have concave log-likelihood functions. When this property holds on a convex parameter domain, it simplifies optimization and rules out nonglobal local maxima. Concavity of a log-likelihood is a model-dependent property, not a general property of likelihoods.

In information theory, entropy concavity describes the effect of mixing probability distributions: the entropy of a mixture is at least the corresponding average of the component entropies.

A related but weaker property is quasiconcavity. A function is quasiconcave if

f((1−t)x+ty)≥min⁡{f(x),f(y)}.f((1-t)x+ty)\geq\min\{f(x),f(y)\}.

Equivalently, all of its upper level sets are convex. Every concave function is quasiconcave, but the converse fails. For example, the exponential function on R\mathbb{R} is quasiconcave because it is increasing, yet it is strictly convex rather than concave. Concavity imposes quantitative restrictions on function values along segments, whereas quasiconcavity constrains only the geometry of upper level sets.