Convex set

Lore & Background

A subset C of a vector space or affine space over the real numbers is convex if, for all x and y in C, the line segment connecting x and y is included in C. This means the affine combination (1 − t)x + ty belongs to C for all x,y in C and t in [0, 1]. Convexity is invariant under affine transformations, and a convex set in a real or complex topological vector space is path-connected. The convex subsets of the real numbers are the intervals and points. Examples in the Euclidean plane include solid regular polygons, solid triangles, and intersections of solid triangles. In 3-dimensional space, the Archimedean solids and Platonic solids are convex, while the Kepler–Poinsot polyhedra are non-convex.

Reader's Guide

The concept of a convex set is fundamental in geometry and optimization. The intersection of all convex sets containing a given subset A is called the convex hull of A, which is the smallest convex set containing A. A convex function is defined by its epigraph being a convex set, and convex minimization studies minimizing convex functions over convex sets. Properties include that the intersection of any collection of convex sets is convex, and a closed convex set can be characterized as the intersection of closed half-spaces. The supporting hyperplane theorem, a special case of the Hahn–Banach theorem, is used to prove this. Faces of a convex set include the set itself and the empty set as trivial faces; extreme points are points that are faces. The Krein–Milman theorem states that a compact convex set in a locally convex topological vector space is the closed convex hull of its extreme points.

Did You Know?

• A set is strictly convex if every point on the line segment connecting two points, other than the endpoints, is inside the topological interior.
• The union of a collection of convex sets is convex only if those sets form a chain under inclusion.
• A convex polytope is the convex hull of a finite subset of some Euclidean space.
• The complement of a convex set is sometimes called a reverse convex set, though this term is niche and not part of the established canon in optimization.

The Core Idea: Containing Every Connecting Segment

A set of points qualifies as convex when a single geometric condition is met: for any two points chosen within the set, the entire straight line segment connecting them must also reside inside the set. This deceptively simple rule produces an intuitive visual test. A solid cube passes it with ease, whereas a crescent shape or any figure with a hollow indentation fails, because some chord between two interior points would cut through empty space. In the plane, the boundary of a convex set always forms a convex curve with no inward dents. The concept admits refinements. A set is strictly convex when every interior point of a connecting segment lies in the topological interior of the set rather than on its boundary; for closed convex sets, this is equivalent to every boundary point being an extreme point. An absolutely convex set is one that is both convex and balanced. Because the underlying definition depends only on affine combinations of points, convexity is invariant under affine transformations. In real or complex topological vector spaces, this invariance guarantees that every convex set is path-connected, and consequently connected.

Convex Combinations and the Convex Hull

The two-point definition of convexity extends elegantly to any finite collection of points. Given r points in a convex set and r nonnegative weights that sum to one, the weighted average—called a convex combination—must also belong to the set. This generalized closure property is not merely a consequence of the original definition; it actually characterizes convex sets, with the two-point case being the simplest instance. The convex hull builds directly on this idea. For any subset of Euclidean space, the convex hull is defined as the intersection of every convex set that contains the original subset, making it the smallest convex set that encloses it. Equivalently, it consists of all possible convex combinations of the subset's points. In finite-dimensional Euclidean space, the convex hull of a finite point set yields a bounded convex polytope, a structure that includes the familiar Platonic solids and Archimedean solids. By contrast, the Kepler–Poinsot polyhedra, with their self-intersecting faces, serve as classic examples of non-convex sets. In one dimension, the convex subsets of the real line are simply intervals and single points.

Algebraic Structure: Intersections, Unions, and Closed Sets

Convex sets enjoy a particularly well-behaved algebraic structure. The empty set and the entire ambient space are both convex. The intersection of any collection—finite or infinite—of convex sets remains convex, a property that makes the family of convex sets closed under arbitrary intersections. Unions, however, require more care: the union of convex sets is convex only when those sets form a chain under inclusion, meaning any two of them are nested. The union of just two convex sets can easily fail to be convex, which is why the chain condition is essential. Closed convex sets, which contain all their limit points, admit a powerful geometric characterization. They can be described exactly as intersections of closed half-spaces, where each half-space is the set of points lying on or to one side of a hyperplane. Proving that every closed convex set can be written this way relies on the supporting hyperplane theorem, which guarantees that for any point outside a closed convex set, there exists a closed half-space containing the set but excluding that point. This theorem is itself a special case of the Hahn–Banach theorem from functional analysis, linking convex geometry to deep results in analysis.

Convex Functions, Optimization, and Broader Context

Convexity extends beyond sets of points into the theory of functions. A real-valued function defined on an interval is called convex when its epigraph—the region of points lying on or above its graph—forms a convex set. This geometric criterion gives convex functions a rich structure that makes them especially tractable for computation. The subfield of convex minimization focuses on the problem of finding the minimum of a convex function over a convex set, a task that arises throughout engineering, economics, and machine learning. The broader branch of mathematics dedicated to studying the properties of convex sets and convex functions is known as convex analysis. The framework is not restricted to flat Euclidean space. Convex sets can be defined in Euclidean spaces, in affine spaces over the real numbers, and even in certain non-Euclidean geometries, provided the underlying structure supports the notion of line segments. In optimization contexts, the complement of a convex set is sometimes termed a reverse convex set, a label that appears especially when dealing with the epigraphs of concave functions. Sets that fail the convexity test are called non-convex, and in polygonal geometry they are often referred to as concave polygons.