Let C⊆Rn be a set. The set C is a convex set if and only if the line segment between any two of its points lies in C.
tx+(1−t)y∈C∀x,y∈C,t∈[0,1]
Let x1,…,xk∈Rn and λ1,…,λk≥0 with ∑i=1kλi=1. The vector ∑i=1kλixi is a convex combination of x1,…,xk. A set is convex if and only if it contains every convex combination of its points.
Let X⊆Rn be a set. The convex hull of X, written conv(X), is the set of all convex combinations of points of X. The convex hull of X is the smallest convex set containing X.
Let a∈Rn∖{0} and b∈R. The hyperplane with normal a and offset b is the set {x:a⊺x=b}. The half-space with normal a and offset b is the set {x:a⊺x≤b}.
A polyhedron is an intersection of finitely many half-spaces and hyperplanes.
Convex sets have the following properties:
- Rn, hyperplanes, half-spaces and balls {x:∥x−x0∥≤r} are convex;
- any intersection of convex sets is convex;
- every polyhedron is convex.
Let C⊆Rn be a convex set and f:C→R be a function. The function f is a convex function if and only if the line segment between any two points on its graph lies on or above the graph.
f(tx+(1−t)y)≤tf(x)+(1−t)f(y)∀x,y∈C,t∈[0,1]
Let C⊆Rn be a convex set and f:C→R be a function. The function f is strictly convex if and only if the inequality above is strict for all x=y and t∈(0,1).
Let C⊆Rn be a convex set and f:C→R be a function. The function f is concave if and only if −f is convex. The function f is strictly concave if and only if −f is strictly convex.
Let C⊆Rn be a convex set, f:C→R be a function and μ>0. The function f is strongly convex with parameter μ if and only if f(x)−2μ∥x∥2 is convex. Equivalently, f is strongly convex with parameter μ if and only if
f(tx+(1−t)y)≤tf(x)+(1−t)f(y)−2μt(1−t)∥x−y∥2∀x,y∈C,t∈[0,1].
Strong convexity implies strict convexity, which implies convexity. Neither implication reverses: f(x)=x4 is strictly but not strongly convex on R.
Let a∈Rn and b∈R. An affine function is a function of the form f(x)=a⊺x+b. An affine function is both convex and concave, and the affine functions are the only functions that are both. Every norm is convex, as are x2, ∣x∣ and ex on R and −logex on (0,∞).
Let C⊆Rn be a convex set and f:C→R be a function. The epigraph of f is the set of points on or above its graph.
epif:={(x,s)∈C×R:s≥f(x)}
The function f is convex if and only if epif is a convex subset of Rn+1.
Let C⊆Rn be a set, f:C→R be a function and α∈R. The sublevel set of f at level α is the set of points at which f is at most α.
{x∈C:f(x)≤α}
Every sublevel set of a convex function is convex. The converse is false.
Let C⊆Rn be a convex set and f:C→R be a function. The function f is quasi-convex if and only if every sublevel set of f is convex.
Let C⊆Rn be a convex set, f:C→R be convex, x1,…,xk∈C and λ1,…,λk≥0 with ∑i=1kλi=1. Jensen’s inequality states that the value of f at a convex combination is at most the convex combination of the values of f.
f(i=1∑kλixi)≤i=1∑kλif(xi)
The inequality reverses for concave functions. Jensen’s inequality extends from finite weighted averages to expectations of random variables.
Let C⊆Rn be an open convex set and f:C→R be differentiable. The first-order condition states that f is convex if and only if its graph lies on or above every one of its tangent planes.
f(y)≥f(x)+∇f(x)⊺(y−x)∀x,y∈C
The first-order condition has the following properties:
- f is strictly convex if and only if the inequality is strict for all y=x;
- f is strongly convex with parameter μ if and only if f(y)≥f(x)+∇f(x)⊺(y−x)+2μ∥y−x∥2 for all x,y∈C.
Let C⊆Rn be an open convex set and f∈C2(C). The second-order condition states that f is convex if and only if its Hessian matrix is positive semi-definite at every point of C.
v⊺Hf(x)v≥0∀x∈C,v∈Rn
The second-order condition has the following properties:
- f is strongly convex with parameter μ if and only if every eigenvalue of its Hessian matrix is at least μ at every point of C;
- if the Hessian matrix is positive definite at every point of C then f is strictly convex, but the converse is false since f(x)=x4 has f′′(0)=0;
- for n=1 the condition is f′′(x)≥0 for all x∈C.
Let A∈Rn×n be symmetric, b∈Rn and c∈R. A quadratic function is a function of the form f(x)=21x⊺Ax+b⊺x+c. A quadratic function has Hf=A, so it is convex if and only if A is positive semi-definite and strongly convex if and only if A is positive definite, with μ equal to the smallest eigenvalue of A.
Convexity is preserved by the following operations, which allow the convexity of a function to be established from simpler functions:
- the non-negative weighted sum ∑i=1kwifi with wi≥0 of convex functions fi is convex;
- the composition f(Ax+b) of a convex function f with an affine function is convex;
- the pointwise maximum max{f1(x),…,fk(x)} of convex functions is convex, as is the pointwise supremum of any family of convex functions;
- the composition g(h(x)) is convex if h is convex and g is convex and monotonically increasing, or if h is concave and g is convex and monotonically decreasing;
- f is convex if and only if its restriction to every line t↦f(x+tv) is convex on the interval where it is defined, which reduces convexity to the univariate case.
Let C⊆Rn be a set, f:C→R be a function and x∗∈C. The point x∗ is a local minimiser of f on C if and only if there exists δ>0 with f(x∗)≤f(x) for all x∈C with ∥x−x∗∥<δ. The point x∗ is a global minimiser of f on C if and only if f(x∗)≤f(x) for all x∈C.
Let C⊆Rn be a convex set and f:C→R be convex. Convexity has the following implications for minimisation:
- every local minimiser of f on C is a global minimiser;
- the set of global minimisers is a convex set, since it is a sublevel set;
- if f is strictly convex then it has at most one global minimiser;
- if f is strongly convex and continuous and C is non-empty and closed then f has exactly one global minimiser;
- if f is differentiable and C is open then x∗ is a global minimiser if and only if ∇f(x∗)=0, so every stationary point is a global minimiser;
- if f is differentiable and C is not necessarily open then x∗ is a global minimiser if and only if ∇f(x∗)⊺(x−x∗)≥0 for all x∈C, so that f does not decrease to first order along any direction into C;
- a convex function on an open convex set is continuous.
Maximisation of a convex function has none of these properties, but maximising a concave function f is equivalent to minimising the convex function −f.
A convex optimisation problem is the problem of minimising a convex function over a convex set. The implications above are why convex optimisation problems can be solved reliably.