nLab convex function

Redirected from "convex maps".
Contents

Contents

Idea

A convex function is a real-valued function defined on a convex set whose graph is the boundary of a convex set.

There is another context where people say a function is convex if it is a Lipschitz function between metric spaces with Lipschitz constant (or Lipschitz modulus) 1. These are different concepts of convexity, although there are relations between convexity and Lipschitz continuity, as we shall see below.

Definition

Let DD be a convex space. A function f:Df \colon D \to \mathbb{R} is convex if the set {(x,z)D×:zf(x)}\{(x, z) \in D \times \mathbb{R}: z \geq f(x)\} is a convex subspace of D×D \times \mathbb{R}. Equivalently, ff is convex if for all x,yDx, y \in D,

f(tx+(1t)y)tf(x)+(1t)f(y)f(t x + (1-t) y) \leq t f(x) + (1-t) f(y)

whenever 0t10 \leq t \leq 1.

This definition obviously extends to functions f:DIf \colon D \to I where II is an interval of \mathbb{R} (whether open or closed or half-open, it doesn’t matter).

The function ff is called concave if it satisfy the reverse inequality to the one given above, or equivalently if f-f is convex.

A function ff is strictly convex if the inequality holds strictly whenever 0<t<10 \lt t \lt 1. In high-school mathematics, one often says concave upward for strictly convex and concave downward for strictly concave.

Examples

  • A homomorphism of convex sets, i.e. a convex-linear map, DD \to \mathbb{R}, is of course convex.

  • The norm function \mathbb{C} \to \mathbb{R} is convex. This follows readily from multiplicativity |xy|=|x||y|{|x y|} = {|x|} \cdot {|y|} and the triangle inequality |x+y||x|+|y|{|x + y|} \leq {|x|} + {|y|}.

  • More generally, for a normed vector space VV, the norm function (){\|(-)\|} is convex, again by the triangle inequality and the scaling axiom αv=|α|v{\|\alpha v\|} = {|\alpha|} \cdot {\|v\|} for scalars α\alpha.

  • For any twice-differentiable function f:(a,b)f \colon (a, b) \to \mathbb{R}, the second derivative ff'' is nonnegative iff ff is convex; this may be proven using the mean value theorem. Examples include the exponential function exp:(,)\exp: (-\infty, \infty) \to \mathbb{R} and the pp-power function [0,):tt p[0, \infty) \to \mathbb{R}: t \mapsto t^p if p1p \geq 1.

  • More generally, for an open convex region D nD \subseteq \mathbb{R}^n in a Euclidean space, a twice-differentiable function f:Df: D \to \mathbb{R} is convex iff its Hessian is a positive semidefinite bilinear form.

  • Any positive \mathbb{R}-linear combination of convex functions on DD is again convex.

  • The pointwise maximum of two convex functions on DD is again convex.

  • If g:VWg: V \to W is a homomorphism or convex-linear map between convex spaces, and if f:Wf: W \to \mathbb{R} is convex, then fg:Vf \circ g: V \to \mathbb{R} is convex.

In the next two examples, II \subseteq \mathbb{R} is an interval.

  • It is not generally true that a composition DgIfD \stackrel{g}{\to} I \stackrel{f}{\to} \mathbb{R} of convex functions is convex. For example, this fails for the case D=D = \mathbb{R} and g(x)=x 2+1g(x) = x^2 + 1 and f:[1,)f: [1, \infty) \to \mathbb{R} given by f(x)=x 1f(x) = x^{-1}.

  • However, if f:If: I \to \mathbb{R} is both monotone increasing and convex, then for any convex function g:DIg: D \to I, the composite fg:Df \circ g: D \to \mathbb{R} is convex (as is easily shown).

A special case of the last class of examples are functions of the form e f=expfe^f = \exp \circ f where ff is convex. We say a function f:D(0,)f: D \to (0, \infty) is log-convex if logf\log f is convex. We see then that log-convex functions are also convex. The identity function on \mathbb{R} is an example of a convex function that is not log-convex (or use xx 2x \mapsto x^2 for a strict example).

Properties

Lemma

If f:(a,b)f: (a, b) \to \mathbb{R} is convex and u<v<w(a,b)u \lt v \lt w \in (a, b), then

f(u)f(v)uvf(u)f(w)uwf(v)f(w)vw.\frac{f(u) - f(v)}{u - v} \leq \frac{f(u) - f(w)}{u - w} \leq \frac{f(v) - f(w)}{v - w}.

Consequently, the function xf(x)f(v)xvx \mapsto \frac{f(x) - f(v)}{x - v} on the domain u<x<vu \lt x \lt v is increasing and is bounded above by f(v)f(w)vw\frac{f(v)-f(w)}{v-w}; similarly, this function on the domain v<x<wv \lt x \lt w is increasing and bounded below by f(u)f(v)uv\frac{f(u)-f(v)}{u-v}.

The proof is virtually trivial; just write vv as a convex combination tu+(1t)wt u + (1-t)w and use the definition of convexity.

Proposition

A convex function f:(a,b)f: (a, b) \to \mathbb{R} is continuous.

Proof

For any point x 0(a,b)x_0 \in (a, b) there are s,t,u,v(a,b)s, t, u, v \in (a, b) with s<t<x 0<u<vs \lt t \lt x_0 \lt u \lt v. Then for any x(t,x 0)(x 0,u)x \in (t, x_0) \cup (x_0, u) we have by Lemma

f(s)f(t)stf(x)f(x 0)xx 0f(u)f(v)uv\frac{f(s)-f(t)}{s-t} \leq \frac{f(x) - f(x_0)}{x-x_0} \leq \frac{f(u)-f(v)}{u-v}

so that K=max{|f(s)f(t)st|,|f(u)f(v)uv|}K = \max\{\left\vert \frac{f(s)-f(t)}{s-t}\right\vert, \left\vert \frac{f(u)-f(v)}{u-v}\right\vert\} serves as a Lipschitz constant, i.e., we have

|f(x)f(x 0)|K|xx 0||f(x) - f(x_0)| \leq K|x - x_0|

for all x(t,u)x \in (t, u). This is enough to force continuity at the point x 0x_0.

In the converse direction, we have the following result which frequently arises in practice.

Proposition

If D nD \subseteq \mathbb{R}^n is a convex set and f:Df: D \to \mathbb{R} is a continuous function such that

f(x+y2)f(x)+f(y)2,f\left(\frac{x+y}{2}\right) \leq \frac{f(x) + f(y)}{2},

then ff is convex.

Proof

For any fixed x,yDx, y \in D, the function h:[0,1]h: [0, 1] \to \mathbb{R} defined by

h(t)=tf(x)+(1t)f(y)f(tx+(1t)y)h(t) = t f(x) + (1-t)f(y) - f(t x + (1-t)y)

is continuous. The inverse image h 1([0,))h^{-1}([0, \infty)) is closed in [0,1][0, 1] and, by an easy induction argument, contains the set of dyadic rational numbers t[0,1]t \in [0, 1], which is dense in [0,1][0, 1]. Being closed and dense, h 1([0,))h^{-1}([0, \infty)) is all of [0,1][0, 1], i.e., h(t)0h(t) \geq 0 for all t[0,1]t \in [0, 1], but this is precisely the condition that ff is convex.

Another easy consequence of Lemma is

Proposition

For a convex function f:(a,b)f: (a, b) \to \mathbb{R}, the right-hand and left-hand derivatives

limxx 0f(x)f(x 0)xx 0,limxx 0f(x)f(x 0)xx 0\underset{x \searrow x_0}{\lim} \frac{f(x)-f(x_0)}{x-x_0}, \qquad \underset{x \nearrow x_0}{\lim} \frac{f(x)-f(x_0)}{x-x_0}

of ff exist at every point x 0(a,b)x_0 \in (a, b), and the left-hand derivative at x 0x_0 is less than or equal to the right-hand derivative at x 0x_0.

It further follows from Lemma that if ff is convex and we define (Df)(x 0)(D f)(x_0) to be the average of the right-hand and left-hand derivatives, then DfD f is monotone increasing and hence is discontinuous at at most countable many points of jump discontinuity (whence DfD f is Riemann-integrable, for instance).

References

See also

Last revised on December 17, 2023 at 01:17:04. See the history of this page for a list of all contributions to it.