Let C⊆RnC\subseteq\mathbb{R}^n be a set. CC is a convex set if and only if the line segment between any two of its points lies in C.C.

t x‾+(1−t)y‾∈C  ∀ x‾,y‾∈C, t∈[0,1]t\,\underline{x}+\left(1-t\right)\underline{y}\in C\,\,\forall\,\underline{x},\underline{y}\in C,\,t\in\left[0,1\right]

Let x‾1,…,x‾k∈Rn\underline{x}_1,\ldots,\underline{x}_k\in\mathbb{R}^n and λ1,…,λk≥0\lambda_1,\ldots,\lambda_k\geq 0 with ∑i=1kλi=1.\sum_{i=1}^k\lambda_i=1. The vector ∑i=1kλix‾i\sum_{i=1}^k\lambda_i\underline{x}_i is a convex combination of x‾1,…,x‾k.\underline{x}_1,\ldots,\underline{x}_k. A set is convex if and only if it contains every convex combination of its points. The convex hull conv(X)\mathrm{conv}(X) of a set X⊆RnX\subseteq\mathbb{R}^n is the set of all convex combinations of points of X,X, which is the smallest convex set containing X.X.

The following sets are convex: Rn;\mathbb{R}^n; the hyperplane {x‾:a‾⊺x‾=b}\{\underline{x}:\underline{a}^\intercal\underline{x}=b\} and half-space {x‾:a‾⊺x‾≤b}\{\underline{x}:\underline{a}^\intercal\underline{x}\leq b\} for a‾∈Rn∖{0‾}\underline{a}\in\mathbb{R}^n\setminus\{\underline{0}\} and b∈R;b\in\mathbb{R}; the ball {x‾:∥x‾−x‾0∥≤r};\{\underline{x}:\lVert\underline{x}-\underline{x}_0\rVert\leq r\}; and any intersection of convex sets. A polyhedron is an intersection of finitely many half-spaces and hyperplanes and is therefore convex.

Let C⊆RnC\subseteq\mathbb{R}^n be a convex set and f:C→Rf:C\rightarrow\mathbb{R} be a function. ff 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(t x‾+(1−t)y‾)≤t f(x‾)+(1−t)f(y‾)  ∀ x‾,y‾∈C, t∈[0,1]f\left(t\,\underline{x}+\left(1-t\right)\underline{y}\right)\leq t\,f(\underline{x})+\left(1-t\right)f(\underline{y})\,\,\forall\,\underline{x},\underline{y}\in C,\,t\in\left[0,1\right]

ff is strictly convex if and only if the inequality is strict for all x‾≠y‾\underline{x}\neq\underline{y} and t∈(0,1).t\in\left(0,1\right). ff is concave if and only if −f-f is convex, and strictly concave if and only if −f-f is strictly convex. Let μ>0.\mu>0. ff is strongly convex with parameter μ\mu if and only if f(x‾)−μ2∥x‾∥2f(\underline{x})-\frac{\mu}{2}\lVert\underline{x}\rVert^2 is convex, which is equivalent to

f(t x‾+(1−t)y‾)≤t f(x‾)+(1−t)f(y‾)−μ2t(1−t)∥x‾−y‾∥2  ∀ x‾,y‾∈C, t∈[0,1].f\left(t\,\underline{x}+\left(1-t\right)\underline{y}\right)\leq t\,f(\underline{x})+\left(1-t\right)f(\underline{y})-\frac{\mu}{2}t\left(1-t\right)\lVert\underline{x}-\underline{y}\rVert^2\,\,\forall\,\underline{x},\underline{y}\in C,\,t\in\left[0,1\right].

Strong convexity implies strict convexity, which implies convexity, and neither implication reverses: f(x)=x4f(x)=x^4 is strictly but not strongly convex on R.\mathbb{R}. An affine function f(x‾)=a‾⊺x‾+bf(\underline{x})=\underline{a}^\intercal\underline{x}+b is both convex and concave, and these are the only functions that are both. Every norm is convex, as are x2,x^2, ∣x∣,\lvert x\rvert, exe^x on R\mathbb{R} and −log⁡ex-\log_e x on (0,∞).\left(0,\infty\right).

The epigraph of ff is the set of points on or above its graph.

epi f:={(x‾,s)∈C×R:s≥f(x‾)}\mathrm{epi}\,f:=\left\{\left(\underline{x},s\right)\in C\times\mathbb{R}:s\geq f(\underline{x})\right\}

ff is convex if and only if epi f\mathrm{epi}\,f is a convex subset of Rn+1.\mathbb{R}^{n+1}. Let α∈R.\alpha\in\mathbb{R}. The sublevel set of ff at level α\alpha is

{x‾∈C:f(x‾)≤α}.\left\{\underline{x}\in C:f(\underline{x})\leq\alpha\right\}.

Every sublevel set of a convex function is convex. The converse is false, and a function all of whose sublevel sets are convex is quasi-convex.

Jensen’s inequality states that if ff is convex, x‾1,…,x‾k∈C\underline{x}_1,\ldots,\underline{x}_k\in C and λ1,…,λk≥0\lambda_1,\ldots,\lambda_k\geq 0 with ∑i=1kλi=1\sum_{i=1}^k\lambda_i=1 then the value of ff at a convex combination is at most the convex combination of the values of f.f.

f(∑i=1kλix‾i)≤∑i=1kλif(x‾i)f\left(\sum_{i=1}^k\lambda_i\underline{x}_i\right)\leq\sum_{i=1}^k\lambda_i f\left(\underline{x}_i\right)

The inequality reverses for concave functions, and extends from finite weighted averages to expectations of random variables.

Let C⊆RnC\subseteq\mathbb{R}^n be an open convex set and f:C→Rf:C\rightarrow\mathbb{R} be differentiable. The first-order condition states that ff 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‾∈Cf(\underline{y})\geq f(\underline{x})+\nabla f(\underline{x})^\intercal\left(\underline{y}-\underline{x}\right)\,\,\forall\,\underline{x},\underline{y}\in C

ff is strictly convex if and only if the inequality is strict for all y‾≠x‾,\underline{y}\neq\underline{x}, and strongly convex with parameter μ\mu if and only if

f(y‾)≥f(x‾)+∇f(x‾)⊺(y‾−x‾)+μ2∥y‾−x‾∥2  ∀ x‾,y‾∈C.f(\underline{y})\geq f(\underline{x})+\nabla f(\underline{x})^\intercal\left(\underline{y}-\underline{x}\right)+\frac{\mu}{2}\lVert\underline{y}-\underline{x}\rVert^2\,\,\forall\,\underline{x},\underline{y}\in C.

Let f∈C2(C).f\in C^2(C). The second-order condition states that ff is convex if and only if its Hessian matrix is positive semi-definite at every point of C,C, and strongly convex with parameter μ\mu if and only if every eigenvalue of its Hessian matrix is at least μ\mu at every point of C.C.

v‾⊺Hf(x‾) v‾≥0  ∀ x‾∈C, v‾∈Rn\underline{v}^\intercal H_f(\underline{x})\,\underline{v}\geq 0\,\,\forall\,\underline{x}\in C,\,\underline{v}\in\mathbb{R}^n

If the Hessian matrix is positive definite at every point of CC then ff is strictly convex, but the converse is false since f(x)=x4f(x)=x^4 has f′′(0)=0.f''(0)=0. For n=1n=1 the condition is f′′(x)≥0  ∀ x∈C.f''(x)\geq 0\,\,\forall\,x\in C. The quadratic function f(x‾)=12x‾⊺Ax‾+b‾⊺x‾+cf(\underline{x})=\frac{1}{2}\underline{x}^\intercal A\underline{x}+\underline{b}^\intercal\underline{x}+c with AA symmetric has Hf=AH_f=A and is convex if and only if AA is positive semi-definite and strongly convex if and only if AA is positive definite, with μ\mu equal to the smallest eigenvalue of A.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\sum_{i=1}^k w_i f_i with wi≥0w_i\geq 0 of convex functions fif_i is convex;
  • the composition f(Ax‾+b‾)f\left(A\underline{x}+\underline{b}\right) of a convex function ff with an affine function is convex;
  • the pointwise maximum max⁡{f1(x‾),…,fk(x‾)}\max\left\{f_1(\underline{x}),\ldots,f_k(\underline{x})\right\} of convex functions is convex, as is the pointwise supremum of any family of convex functions;
  • the composition g(h(x‾))g\left(h(\underline{x})\right) is convex if hh is convex and gg is convex and monotonically increasing, or hh is concave and gg is convex and monotonically decreasing;
  • ff is convex if and only if its restriction to every line t↦f(x‾+t v‾)t\mapsto f\left(\underline{x}+t\,\underline{v}\right) is convex on the interval where it is defined, which reduces convexity to the univariate case.

Let C⊆RnC\subseteq\mathbb{R}^n be a convex set and f:C→Rf:C\rightarrow\mathbb{R} be convex. A point x‾∗∈C\underline{x}^*\in C is a local minimiser of ff on CC if and only if there exists δ>0\delta>0 with f(x‾∗)≤f(x‾)f(\underline{x}^*)\leq f(\underline{x}) for all x‾∈C\underline{x}\in C with ∥x‾−x‾∗∥<δ,\lVert\underline{x}-\underline{x}^*\rVert<\delta, and a global minimiser if and only if f(x‾∗)≤f(x‾)  ∀ x‾∈C.f(\underline{x}^*)\leq f(\underline{x})\,\,\forall\,\underline{x}\in C. Convexity has the following implications for minimisation:

  • every local minimiser of ff on CC is a global minimiser;
  • the set of global minimisers is a convex set, since it is a sublevel set;
  • if ff is strictly convex then it has at most one global minimiser;
  • if ff is strongly convex and continuous and CC is non-empty and closed then ff has exactly one global minimiser;
  • if ff is differentiable on an open convex set CC then x‾∗\underline{x}^* is a global minimiser if and only if ∇f(x‾∗)=0‾,\nabla f(\underline{x}^*)=\underline{0}, so every stationary point is a global minimiser;
  • if ff is differentiable on a convex set CC that need not be open then x‾∗\underline{x}^* is a global minimiser if and only if no direction into CC is a direction of descent.
∇f(x‾∗)⊺(x‾−x‾∗)≥0  ∀ x‾∈C\nabla f(\underline{x}^*)^\intercal\left(\underline{x}-\underline{x}^*\right)\geq 0\,\,\forall\,\underline{x}\in 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 is equivalent to minimising the convex function −f.-f. Minimising a convex function over a convex set is a convex optimisation problem, and the implications above are why such problems can be solved reliably.