Let C⊆RnC\subseteq\mathbb{R}^n be a set. The 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.

Let X⊆RnX\subseteq\mathbb{R}^n be a set. The convex hull of X,X, written conv(X),\mathrm{conv}(X), is the set of all convex combinations of points of X.X. The convex hull of XX is the smallest convex set containing X.X.

Let a‾∈Rn∖{0‾}\underline{a}\in\mathbb{R}^n\setminus\{\underline{0}\} and b∈R.b\in\mathbb{R}. The hyperplane with normal a‾\underline{a} and offset bb is the set {x‾:a‾⊺x‾=b}.\{\underline{x}:\underline{a}^\intercal\underline{x}=b\}. The half-space with normal a‾\underline{a} and offset bb is the set {x‾:a‾⊺x‾≤b}.\{\underline{x}:\underline{a}^\intercal\underline{x}\leq b\}.

A polyhedron is an intersection of finitely many half-spaces and hyperplanes.

Convex sets have the following properties:

  • Rn,\mathbb{R}^n, hyperplanes, half-spaces and balls {x‾:∥x‾−x‾0∥≤r}\{\underline{x}:\lVert\underline{x}-\underline{x}_0\rVert\leq r\} are convex;
  • any intersection of convex sets is convex;
  • every polyhedron is convex.

Let C⊆RnC\subseteq\mathbb{R}^n be a convex set and f:C→Rf:C\rightarrow\mathbb{R} be a function. The 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]

Let C⊆RnC\subseteq\mathbb{R}^n be a convex set and f:C→Rf:C\rightarrow\mathbb{R} be a function. The function ff is strictly convex if and only if the inequality above is strict for all x‾≠y‾\underline{x}\neq\underline{y} and t∈(0,1).t\in\left(0,1\right).

Let C⊆RnC\subseteq\mathbb{R}^n be a convex set and f:C→Rf:C\rightarrow\mathbb{R} be a function. The function ff is concave if and only if −f-f is convex. The function ff is strictly concave if and only if −f-f is strictly convex.

Let C⊆RnC\subseteq\mathbb{R}^n be a convex set, f:C→Rf:C\rightarrow\mathbb{R} be a function and μ>0.\mu>0. The function 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. Equivalently, ff is strongly convex with parameter μ\mu if and only if

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. Neither implication reverses: f(x)=x4f(x)=x^4 is strictly but not strongly convex on R.\mathbb{R}.

Let a‾∈Rn\underline{a}\in\mathbb{R}^n and b∈R.b\in\mathbb{R}. An affine function is a function of the form f(x‾)=a‾⊺x‾+b.f(\underline{x})=\underline{a}^\intercal\underline{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^2, ∣x∣\lvert x\rvert and exe^x on R\mathbb{R} and −log⁡ex-\log_e x on (0,∞).\left(0,\infty\right).

Let C⊆RnC\subseteq\mathbb{R}^n be a convex set and f:C→Rf:C\rightarrow\mathbb{R} be a function. 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\}

The function ff is convex if and only if epi f\mathrm{epi}\,f is a convex subset of Rn+1.\mathbb{R}^{n+1}.

Let C⊆RnC\subseteq\mathbb{R}^n be a set, f:C→Rf:C\rightarrow\mathbb{R} be a function and α∈R.\alpha\in\mathbb{R}. The sublevel set of ff at level α\alpha is the set of points at which ff is at most α.\alpha.

{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.

Let C⊆RnC\subseteq\mathbb{R}^n be a convex set and f:C→Rf:C\rightarrow\mathbb{R} be a function. The function ff is quasi-convex if and only if every sublevel set of ff is convex.

Let C⊆RnC\subseteq\mathbb{R}^n be a convex set, f:C→Rf:C\rightarrow\mathbb{R} be 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. Jensen’s inequality states that 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. Jensen’s inequality 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

The first-order condition has the following properties:

  • ff is strictly convex if and only if the inequality is strict for all y‾≠x‾;\underline{y}\neq\underline{x};
  • ff is strongly convex with parameter μ\mu if and only if f(y‾)≥f(x‾)+∇f(x‾)⊺(y‾−x‾)+μ2∥y‾−x‾∥2f(\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 for all x‾,y‾∈C.\underline{x},\underline{y}\in C.

Let C⊆RnC\subseteq\mathbb{R}^n be an open convex set and 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.

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

The second-order condition has the following properties:

  • ff is 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;
  • 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)≥0f''(x)\geq 0 for all x∈C.x\in C.

Let A∈R n×nA\in\mathbb{R}^{\,n\times n} be symmetric, b‾∈Rn\underline{b}\in\mathbb{R}^n and c∈R.c\in\mathbb{R}. A quadratic function is a function of the form f(x‾)=12x‾⊺Ax‾+b‾⊺x‾+c.f(\underline{x})=\frac{1}{2}\underline{x}^\intercal A\underline{x}+\underline{b}^\intercal\underline{x}+c. A quadratic function has Hf=A,H_f=A, so it 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 if 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 set, f:C→Rf:C\rightarrow\mathbb{R} be a function and x‾∗∈C.\underline{x}^*\in C. The point x‾∗\underline{x}^* 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. The point x‾∗\underline{x}^* is a global minimiser of ff on CC if and only if f(x‾∗)≤f(x‾)f(\underline{x}^*)\leq f(\underline{x}) for all x‾∈C.\underline{x}\in C.

Let C⊆RnC\subseteq\mathbb{R}^n be a convex set and f:C→Rf:C\rightarrow\mathbb{R} be convex. 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 and CC is open 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 and CC is not necessarily open then x‾∗\underline{x}^* is a global minimiser if and only if ∇f(x‾∗)⊺(x‾−x‾∗)≥0\nabla f(\underline{x}^*)^\intercal\left(\underline{x}-\underline{x}^*\right)\geq 0 for all x‾∈C,\underline{x}\in C, so that ff does not decrease to first order along any direction into C;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 ff is equivalent to minimising the convex function −f.-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.