Convex function

# Convex function

Overview
In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, a real-valued function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

defined on an interval
Interval (mathematics)
In mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers satisfying is an interval which contains and , as well as all numbers between them...

is called convex (or convex downward or concave upward) if the graph of the function lies below the line segment joining any two points of the graph. Equivalently, a function is convex if its epigraph
Epigraph (mathematics)
In mathematics, the epigraph of a function f : Rn→R is the set of points lying on or above its graph:and the strict epigraph of the function is:The set is empty if f \equiv \infty ....

(the set of points on or above the graph of the function) is a convex set
Convex set
In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...

.
Discussion

Recent Discussions
Encyclopedia
In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, a real-valued function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

defined on an interval
Interval (mathematics)
In mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers satisfying is an interval which contains and , as well as all numbers between them...

is called convex (or convex downward or concave upward) if the graph of the function lies below the line segment joining any two points of the graph. Equivalently, a function is convex if its epigraph
Epigraph (mathematics)
In mathematics, the epigraph of a function f : Rn→R is the set of points lying on or above its graph:and the strict epigraph of the function is:The set is empty if f \equiv \infty ....

(the set of points on or above the graph of the function) is a convex set
Convex set
In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...

. More generally, this definition of convex functions makes sense for functions defined on a convex subset of any vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

.

Convex functions play an important role in many areas of mathematics. They are especially important in the study of optimization
Optimization
Optimization or optimality may refer to:* Mathematical optimization, the theory and computation of extrema or stationary points of functionsEconomics and business* Optimality, in economics; see utility and economic efficiency...

problems where they are distinguished by a number of convenient properties. For instance, a (strictly) convex function on an open set has no more than one minimum. Even in infinite-dimensional spaces, under suitable additional hypotheses, convex functions continue to satisfy such properties and, as a result, they are the most well-understood functionals in the calculus of variations
Calculus of variations
Calculus of variations is a field of mathematics that deals with extremizing functionals, as opposed to ordinary calculus which deals with functions. A functional is usually a mapping from a set of functions to the real numbers. Functionals are often formed as definite integrals involving unknown...

. In probability theory
Probability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...

, a convex function applied to the expected value
Expected value
In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...

of a random variable
Random variable
In probability and statistics, a random variable or stochastic variable is, roughly speaking, a variable whose value results from a measurement on some type of random process. Formally, it is a function from a probability space, typically to the real numbers, which is measurable functionmeasurable...

is always less or equal to the expected value of the convex function of the random variable. This result, known as Jensen's inequality
Jensen's inequality
In mathematics, Jensen's inequality, named after the Danish mathematician Johan Jensen, relates the value of a convex function of an integral to the integral of the convex function. It was proved by Jensen in 1906. Given its generality, the inequality appears in many forms depending on the context,...

underlies many important inequalities (including, for instance, the arithmetic-geometric mean inequality and Hölder's inequality
Hölder's inequality
In mathematical analysis Hölder's inequality, named after Otto Hölder, is a fundamental inequality between integrals and an indispensable tool for the study of Lp spaces....

).

## Definition

A real
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

valued function defined on a convex set
Convex set
In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...

X in a vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

is called convex if, for any two points and in X and any ,

The function is called strictly convex if

for every , , and .

A function f is said to be (strictly) concave
Concave function
In mathematics, a concave function is the negative of a convex function. A concave function is also synonymously called concave downwards, concave down, convex upwards, convex cap or upper convex.-Definition:...

if −f is (strictly) convex.

## Properties

Suppose f is a function of one real
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

variable defined on an interval, and let

(note that is the slope of the purple line in the above drawing; note also that the function R is symmetric in ). f is convex if and only if is monotonically non-decreasing in , for fixed (or viceversa). This characterization of convexity is quite useful to prove the following results.

A convex function f defined on some open interval C is continuous
Continuous function
In mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...

on C and Lipschitz continuous on any closed subinterval. f admits left and right derivatives, and these are monotonically non-decreasing. As a consequence, f is differentiable
Differentiable function
In calculus , a differentiable function is a function whose derivative exists at each point in its domain. The graph of a differentiable function must have a non-vertical tangent line at each point in its domain...

at all but at most countably many points. If C is closed, then f may fail to be continuous at the endpoints of C (an example is shown in the examples' section).

A function is midpoint convex on an interval C if

for all and in C. This condition is only slightly weaker than convexity. For example, a real valued Lebesgue measurable function that is midpoint convex will be convex. In particular, a continuous function that is midpoint convex will be convex.

A differentiable function of one variable is convex on an interval if and only if its derivative
Derivative
In calculus, a branch of mathematics, the derivative is a measure of how a function changes as its input changes. Loosely speaking, a derivative can be thought of as how much one quantity is changing in response to changes in some other quantity; for example, the derivative of the position of a...

is monotonically non-decreasing on that interval. If a function is differentiable and convex then it is also continuously differentiable.

A continuously differentiable function of one variable is convex on an interval if and only if the function lies above all of its tangent
Tangent
In geometry, the tangent line to a plane curve at a given point is the straight line that "just touches" the curve at that point. More precisely, a straight line is said to be a tangent of a curve at a point on the curve if the line passes through the point on the curve and has slope where f...

s:
for all x and y in the interval. In particular, if f '(c) = 0, then c is a global minimum of f(x).

A twice differentiable function of one variable is convex on an interval if and only if its second derivative
Second derivative
In calculus, the second derivative of a function ƒ is the derivative of the derivative of ƒ. Roughly speaking, the second derivative measures how the rate of change of a quantity is itself changing; for example, the second derivative of the position of a vehicle with respect to time is...

is non-negative there; this gives a practical test for convexity.
If its second derivative is positive then it is strictly convex, but the converse does not hold. For example, the second derivative of f(x) = x4 is f "(x) = 12 x2, which is zero for x = 0, but x4 is strictly convex.

More generally, a continuous, twice differentiable function of several variables is convex on a convex set if and only if its Hessian matrix
Hessian matrix
In mathematics, the Hessian matrix is the square matrix of second-order partial derivatives of a function; that is, it describes the local curvature of a function of many variables. The Hessian matrix was developed in the 19th century by the German mathematician Ludwig Otto Hesse and later named...

is positive semidefinite
Positive-definite matrix
In linear algebra, a positive-definite matrix is a matrix that in many ways is analogous to a positive real number. The notion is closely related to a positive-definite symmetric bilinear form ....

on the interior of the convex set.

Any local minimum of a convex function is also a global minimum. A strictly convex function will have at most one global minimum.

For a convex function f, the sublevel sets {x | f(x) < a} and {x | f(x) ≤ a} with a ∈ R are convex sets. However, a function whose sublevel sets are convex sets may fail to be a convex function. A function whose sublevel sets are convex is called a quasiconvex function
Quasiconvex function
In mathematics, a quasiconvex function is a real-valued function defined on an interval or on a convex subset of a real vector space such that the inverse image of any set of the form is a convex set...

.

Jensen's inequality
Jensen's inequality
In mathematics, Jensen's inequality, named after the Danish mathematician Johan Jensen, relates the value of a convex function of an integral to the integral of the convex function. It was proved by Jensen in 1906. Given its generality, the inequality appears in many forms depending on the context,...

applies to every convex function f. If X is a random variable taking values in the domain of f, then (Here denotes the mathematical expectation
Expected value
In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...

.)

If a function f is convex, and f(0) ≤ 0, then f is superadditive on the positive half-axis. Proof:
• since f is convex, let y = 0, for every

• ## Convex function calculus

• If and are convex functions, then so are and
• If and are convex functions and is non-decreasing, then is convex.
• If is concave and is convex and non-increasing, then is convex.
• Convexity is invariant under affine maps: that is, if is convex with , then so is with , where
• If is convex in then is convex in provided for some
• If is convex, then its perspective (whose domain is ) is convex.
In mathematics, the additive inverse, or opposite, of a number a is the number that, when added to a, yields zero.The additive inverse of a is denoted −a....

of a convex function is a concave function
Concave function
In mathematics, a concave function is the negative of a convex function. A concave function is also synonymously called concave downwards, concave down, convex upwards, convex cap or upper convex.-Definition:...

.

## Strongly convex functions

The concept of strong convexity extends and parametrizes the notion of strict convexity. A strongly convex function is also strictly convex, but not vice-versa.

A differentiable function f is called strongly convex with parameter m > 0 if the following inequality holds for all points x,y in its domain:
Some authors, such as
refer to functions satisfying this inequality as elliptic
Elliptic operator
In the theory of partial differential equations, elliptic operators are differential operators that generalize the Laplace operator. They are defined by the condition that the coefficients of the highest-order derivatives be positive, which implies the key property that the principal symbol is...

functions.

An equivalent condition is the following:

It is not necessary for a function to be differentiable in order to be strongly convex. A third definition for a strongly convex function, with parameter m, is that, for all x,y in the domain and ,
Notice that this definition approaches the definition for strict convexity as , and is identical to the definition of a convex function when m = 0. Despite this, functions exist that are strictly convex but are not strongly convex for any m > 0 (see example below).

If the function f is twice continuously differentiable, then f is strongly convex with parameter m if and only if for all x in the domain, where I is the identity and is the Hessian matrix
Hessian matrix
In mathematics, the Hessian matrix is the square matrix of second-order partial derivatives of a function; that is, it describes the local curvature of a function of many variables. The Hessian matrix was developed in the 19th century by the German mathematician Ludwig Otto Hesse and later named...

, and the inequality means that is positive definite
Positive-definite matrix
In linear algebra, a positive-definite matrix is a matrix that in many ways is analogous to a positive real number. The notion is closely related to a positive-definite symmetric bilinear form ....

. This is equivalent to requiring that the minimum eigenvalue of be at least m for all x. If the domain is just the real line, then is just the second derivative , so the condition becomes . If m = 0, then this means the Hessian is positive semidefinite (or if the domain is the real line, it means that ), which implies the function is convex, and perhaps strictly convex, but not strongly convex.

Assuming still that the function is twice continuously differentiable, we show that the lower bound of implies that it is strongly convex. Start by using Taylor's Theorem
Taylor's theorem
In calculus, Taylor's theorem gives an approximation of a k times differentiable function around a given point by a k-th order Taylor-polynomial. For analytic functions the Taylor polynomials at a given point are finite order truncations of its Taylor's series, which completely determines the...

:
for some (unknown) .
Then by the assumption about the eigenvalues, and hence we recover the second strong convexity equation above.

The distinction between convex, strictly convex, and strongly convex can be subtle at first glimpse. If is twice continuously differentiable and the domain is the real line, then we can characterize it as follows:
convex if and only if for all
strictly convex if for all (note: this is sufficient, but not necessary)
strongly convex if and only if for all

For example, consider a function that is strictly convex, and suppose there is a sequence of points such that . Even though , the function is not strongly convex because will become arbitrarily small.

Strongly convex functions are in general easier to work with than convex or strictly convex functions, since they are a smaller class. Like strictly convex functions, strongly convex functions have unique minima.

## Examples

• The function has at all points, so f is a convex function. It is also strongly convex (and hence strictly convex too), with strong convexity constant 2.
• The function has , so f is a convex function. It is strictly convex, even though the second derivative is not strictly positive at all points. It is not strongly convex.
• The absolute value
Absolute value
In mathematics, the absolute value |a| of a real number a is the numerical value of a without regard to its sign. So, for example, the absolute value of 3 is 3, and the absolute value of -3 is also 3...

function is convex, even though it does not have a derivative at the point x = 0. It is not strictly convex.
• The function for 1 ≤ p is convex.
• The exponential function
Exponential function
In mathematics, the exponential function is the function ex, where e is the number such that the function ex is its own derivative. The exponential function is used to model a relationship in which a constant change in the independent variable gives the same proportional change In mathematics,...

is convex. It is also strictly convex, since , but it is not strongly convex since the second derivative can be arbitrarily close to zero. More generally, the function is logarithmically convex
Logarithmically convex function
In mathematics, a function f defined on a convex subset of a real vector space and taking positive values is said to be logarithmically convex if \log f is a convex function of x....

if
f is a convex function. The term "superconvex" is sometimes used instead.
• The function f with domain [0,1] defined by f(0) = f(1) = 1, f(x) = 0 for 0 < x < 1 is convex; it is continuous on the open interval (0, 1), but not continuous at 0 and 1.
• The function x3 has second derivative 6x; thus it is convex on the set where x ≥ 0 and concave
Concave function
In mathematics, a concave function is the negative of a convex function. A concave function is also synonymously called concave downwards, concave down, convex upwards, convex cap or upper convex.-Definition:...

on the set where
x ≤ 0.
• Every linear transformation
Linear transformation
In mathematics, a linear map, linear mapping, linear transformation, or linear operator is a function between two vector spaces that preserves the operations of vector addition and scalar multiplication. As a result, it always maps straight lines to straight lines or 0...

taking values in is convex but not strictly convex, since if
f is linear, then This statement also holds if we replace "convex" by "concave".
• Every affine function taking values in , i.e., each function of the form , is simultaneously convex and concave.
• Every norm
Norm (mathematics)
In linear algebra, functional analysis and related areas of mathematics, a norm is a function that assigns a strictly positive length or size to all vectors in a vector space, other than the zero vector...

is a convex function, by the triangle inequality
Triangle inequality
In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side ....

and positive homogeneity.
• Examples of functions that are monotonically increasing
Monotonic function
In mathematics, a monotonic function is a function that preserves the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order theory....

but not convex include and g(x) = log(x).
• Examples of functions that are convex but not monotonically increasing
Monotonic function
In mathematics, a monotonic function is a function that preserves the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order theory....

include and .
• The function f(x) = 1/x has which is greater than 0 if x > 0, so f(x) is convex on the interval (0, +∞). It is concave on the interval (-∞,0).
• The function f(x) = 1/x2, with f(0) = +∞, is convex on the interval (0, +∞) and convex on the interval (-∞,0), but not convex on the interval (-∞, +∞), because of the singularity at x = 0.

• Concave function
Concave function
In mathematics, a concave function is the negative of a convex function. A concave function is also synonymously called concave downwards, concave down, convex upwards, convex cap or upper convex.-Definition:...

• Convex optimization
• Geodesic convexity
Geodesic convexity
In mathematics — specifically, in Riemannian geometry — geodesic convexity is a natural generalization of convexity for sets and functions to Riemannian manifolds...

• Kachurovskii's theorem
Kachurovskii's theorem
In mathematics, Kachurovskii's theorem is a theorem relating the convexity of a function on a Banach space to the monotonicity of its Fréchet derivative.-Statement of the theorem:...

, which relates convexity to monotonicity of the derivative
• Logarithmically convex function
Logarithmically convex function
In mathematics, a function f defined on a convex subset of a real vector space and taking positive values is said to be logarithmically convex if \log f is a convex function of x....

• Pseudoconvex function
Pseudoconvex function
In convex analysis and the calculus of variations, branches of mathematics, a pseudoconvex function is a function that behaves like a convex function with respect to finding its local minima, but need not actually be convex...

• Quasiconvex function
Quasiconvex function
In mathematics, a quasiconvex function is a real-valued function defined on an interval or on a convex subset of a real vector space such that the inverse image of any set of the form is a convex set...

• Subderivative
Subderivative
In mathematics, the concepts of subderivative, subgradient, and subdifferential arise in convex analysis, that is, in the study of convex functions, often in connection to convex optimization....

of a convex function
• Jensen's inequality
Jensen's inequality
In mathematics, Jensen's inequality, named after the Danish mathematician Johan Jensen, relates the value of a convex function of an integral to the integral of the convex function. It was proved by Jensen in 1906. Given its generality, the inequality appears in many forms depending on the context,...

• Karamata's inequality
Karamata's inequality
In mathematics, Karamata's inequality, named after Jovan Karamata, also known as the majorization inequality, is a theorem in elementary algebra for convex and concave real-valued functions, defined on an interval of the real line...