Convex

Convex is a term used in geometry, analysis, and optimization to indicate a notion of no indentation or tipping. In Euclidean space, a set C is convex if for any points x and y in C and any t with 0 ≤ t ≤ 1, the point tx + (1−t)y also lies in C. Equivalently, the line segment connecting x and y is contained in C. Sets failing this property are non-convex, often with holes or reentrant corners.

A convex hull of a set S is the smallest convex set containing S; it can be formed as the set of all convex combinations of points of S. Convex sets include Euclidean balls, boxes, and simplices; a polygon is convex exactly when every line segment joining two points of the polygon stays inside it.

A function f defined on a convex domain is convex if f(tx+(1−t)y) ≤ t f(x) + (1−t) f(y) for all x,y in the domain and t ∈ [0,1]. The epigraph, epi f = {(x, α) : α ≥ f(x)}, is a convex set when f is convex. If the inequality is strict for x ≠ y, f is strictly convex. For twice differentiable functions, f is convex iff its Hessian is positive semidefinite on the domain.

Convexity is preserved under several operations: the intersection of convex sets is convex; the convex hull of a set is convex; the Minkowski sum of convex sets is convex; images of convex sets under affine maps are convex; sublevel sets of a convex function are convex; epigraphs are convex.

Convexity underpins convex optimization, where a convex objective on a convex feasible region guarantees that any local minimum is a global minimum. This leads to efficient algorithms and strong duality in many problems, including linear and convex quadratic programming.