Fact-checked by Grok 2 weeks ago

Convex set

In mathematics, a convex set is a subset C of a Euclidean space \mathbb{R}^n such that the line segment connecting any two points in C lies entirely within C. Formally, for all x, y \in C and \theta \in [0, 1], the convex combination \theta x + (1 - \theta) y \in C.^[1] This property captures sets that are "round" or "bowl-shaped" without indentations, distinguishing them from non-convex sets like a crescent moon, where line segments between points may exit the set.^[2] Convex sets encompass a wide range of geometric objects central to fields like optimization, geometry, and functional analysis. Common examples include half-spaces defined by linear inequalities \{ x \mid a^T x \leq b \}, Euclidean balls \{ x \mid \|x - x_c\|_2 \leq [r](/page/Range) \}, ellipsoids \{ x \mid (x - x_c)^T P^{-1} (x - x_c) \leq 1 \} where P \succ 0, polyhedra as intersections of finitely many half-spaces, and the cone of positive semidefinite matrices \mathcal{S}_n^+ = \{ X \in \mathcal{S}_n \mid X \succeq 0 \}.^[1] These structures appear in applications such as linear programming (where feasible regions are polyhedra) and semidefinite programming (involving matrix cones).^[3] Key properties of convex sets ensure their utility in theoretical and computational mathematics. The intersection of any collection of convex sets is convex, and the image of a convex set under an affine mapping Ax + b remains convex.^[1] Operations like Minkowski summation, scaling, and translation preserve convexity, while the closure and relative interior of a convex set are also convex.^[2] In optimization, convex sets define feasible regions for convex problems, guaranteeing that local minima are global and enabling efficient polynomial-time algorithms like interior-point methods.^[4] Theorems such as the separating hyperplane theorem further highlight their role: for disjoint nonempty convex sets C and D, there exists a hyperplane separating them.^[1]

Definitions and Basic Concepts

Formal Definition

A subset C of a real vector space V, often taken to be the Euclidean space \mathbb{R}^n, is called convex if, for any two points x, y \in C and any scalar \lambda \in [0, 1], the convex combination \lambda x + (1 - \lambda) y also belongs to C. This condition ensures that C contains the entire line segment joining any pair of its points. An equivalent formulation states that C is convex if it contains all convex combinations of its points, where a convex combination is a linear combination \sum_{i=1}^k \lambda_i x_i with \sum_{i=1}^k \lambda_i = 1 and each \lambda_i \geq 0.^[5] The empty set and singleton sets \{x\} (for any x \in V) are trivially convex, as the defining condition holds vacuously in these cases.^[6] The concept of a convex set was formalized by Hermann Minkowski in 1896, in the context of the geometry of numbers, where he developed the notion of convex bodies to study lattice points and quadratic forms.^[7] In the plane \mathbb{R}^2, this means that if two points lie in C, then the straight line segment connecting them must lie entirely within C, illustrating the "no dents" geometric intuition behind the definition.^[8]

Examples of Convex Sets

In one dimension, convex sets are precisely the intervals on the real line, which include open intervals like (a, b), closed intervals like [a, b], half-open intervals like [a, b), and unbounded variants such as (-∞, b] or the entire line ℝ.^[9] These sets satisfy the defining property that for any two points x, y within the interval and any λ ∈ [0, 1], the point λx + (1 - λ)y also lies within the interval, as it represents a point between x and y.^[10] In two dimensions, common examples include disks, which are the sets of points at or within a fixed distance from a center, such as the unit disk {(x, y) ∈ ℝ² | x² + y² ≤ 1}, where any line segment connecting two points inside remains entirely inside due to the geometry of circles.^[11] Half-planes, defined by linear inequalities like { (x, y) ∈ ℝ² | ax + by ≤ c }, are also convex, as they consist of all points on one side of a straight line, preserving line segments within the region.^[10] Convex polygons, such as triangles and squares, form another class; for instance, a triangle is the convex hull of three non-collinear vertices, ensuring that all line segments between interior points stay inside the boundaries.^[12] Higher-dimensional examples extend these ideas: balls generalize disks to n dimensions, like the unit ball in ℝⁿ = { x ∈ ℝⁿ | ||x|| ≤ 1 }, where the Euclidean norm ensures convexity by containing all scaled combinations within the sphere. Ellipsoids, affine transformations of balls, such as { x ∈ ℝⁿ | (x - μ)ᵀ Σ⁻¹ (x - μ) ≤ 1 } for a positive definite matrix Σ, remain convex due to the preservation of line segments under affine maps.^[10] Convex polyhedra in ℝ³, like tetrahedra or cubes, are intersections of half-spaces bounded by planes, with the cube [-1, 1]³ exemplifying how facets bulge outward without indentations.^[12] Simplices, the convex hulls of n+1 affinely independent points in ℝⁿ, such as the standard n-simplex { x ∈ ℝⁿ | x_i ≥ 0, ∑ x_i ≤ 1 }, represent the simplest polytope and are fundamental in linear programming.^[13] Functional examples arise in convex analysis, where the epigraph of a convex function f: ℝ → ℝ, defined as epi f = { (x, t) ∈ ℝ² | t ≥ f(x) }, forms a convex set in ℝ². For the quadratic function f(x) = x², the epigraph is the region above the parabola, and any line segment connecting two points (x₁, t₁) and (x₂, t₂) with t₁ ≥ x₁² and t₂ ≥ x₂² lies entirely above the graph due to the convexity inequality f(λx₁ + (1-λ)x₂) ≤ λf(x₁) + (1-λ)f(x₂).^[14] Linear functions f(x) = ax + b yield epigraphs that are half-planes { (x, t) | t ≥ ax + b }, which are convex as unbounded slabs above a line.^[15] In probability theory, the set of all probability distributions over a finite sample space is a convex set, specifically the (n-1)-simplex for n outcomes, where convex combinations correspond to mixtures of distributions, such as averaging two discrete probabilities p and q to get λp + (1-λ)q, which remains a valid probability vector.^[16] More generally, in measure theory, the set of probability measures on a space, equipped with the total variation norm, forms a convex set, as convex combinations of measures are again probability measures preserving the total mass of 1.^[17] Visually, convexity manifests in these sets through the containment of line segments: in a disk, the straight path between two interior points curves no farther than the boundary; in a simplex, edges connect vertices without dipping outside; and in an epigraph, vertical slices above the function graph ensure that interpolated points stay above the curve, illustrating the "no dents" property across dimensions.^[10]

Non-Convex Sets

A non-convex set is one that fails to satisfy the convexity condition, meaning there exist points x, y in the set and \lambda \in (0,1) such that \lambda x + (1-\lambda) y lies outside the set. Unlike convex sets such as disks or balls, non-convex sets allow line segments connecting interior points to exit the set, complicating analysis in fields like optimization.^[18] A basic example in one dimension is the union of two disjoint closed intervals, such as S = [0,1] \cup [2,3] \subseteq \mathbb{R}. This set is non-convex because, for x = 1 \in S, y = 2 \in S, and \lambda = 1/2, the point \lambda x + (1-\lambda) y = 1.5 \notin S.^[19] In higher dimensions, the integer lattice \mathbb{Z}^n \subseteq \mathbb{R}^n provides another discrete example of a non-convex set. For n=1, consider x = 0 \in \mathbb{Z}, y = 1 \in \mathbb{Z}, and \lambda = 1/2; then \lambda x + (1-\lambda) y = 0.5 \notin \mathbb{Z}. This failure extends to higher n due to the discrete nature preventing continuous line segments.^[20] Geometrically, a crescent or kidney shape in \mathbb{R}^2, such as the region between two circular arcs, is non-convex. For instance, points on the inner and outer arcs may have the connecting line segment pass through the excluded central region, violating the condition (see Figure 2.2 for a kidney-shaped illustration).^[18] Non-convex polygons, like an L-shape formed by [0,2] \times [0,1] \cup [0,1] \times [1,2], also fail convexity; taking endpoints of the "arms" (e.g., (2,0) and (0,2)) yields a segment crossing the missing square (1,1) \times (1,2), so part lies outside. Similarly, a star polygon, such as the pentagram, has intersecting sides where line segments between non-adjacent vertices exit the boundary.^[18] In functional contexts, the epigraph of a non-convex function illustrates non-convexity in \mathbb{R}^2. The epigraph of f(x) = \sin x is \{(x,y) \mid y \geq \sin x\}, which is non-convex because \sin x is not convex (its second derivative changes sign). Specifically, a function is convex if and only if its epigraph is convex, so this epigraph fails; for example, points (0, \sin 0) = (0,0) and (\pi, \sin \pi) = (\pi, 0) (both on the graph) have midpoint (\pi/2, 0), but \sin(\pi/2) = 1 > 0, confirming the violation.^[18] In applications, particularly optimization, non-convex sets often lead to multiple local optima, making global minimization challenging compared to convex cases where any local minimum is global. This arises in problems like non-convex quadratic programming or discrete optimization over lattices, where algorithms may converge to suboptimal points.^[18]

Fundamental Properties

Intersections and Unions

One fundamental property of convex sets is their closure under arbitrary intersections. Specifically, the intersection of any family of convex sets, whether finite or infinite, is itself convex. To prove this, let \{C_\alpha\}_{\alpha \in A} be a family of convex sets in a vector space, and let x, y \in \bigcap_{\alpha \in A} C_\alpha. For any \lambda \in [0, 1], the point \lambda x + (1 - \lambda) y belongs to each C_\alpha by convexity of C_\alpha, and thus lies in the intersection \bigcap_{\alpha \in A} C_\alpha.^[21] In contrast, unions of convex sets do not preserve convexity. The union of finitely many convex sets is not necessarily convex; for instance, the union of the closed intervals [0, 1] and [2, 3] on the real line is disconnected, and the line segment joining a point in the first interval to one in the second lies outside the union. While the union itself may lack convexity, the convex hull of the union provides a convex set containing it.^[19] This failure extends to infinite unions. Consider the infinite union \bigcup_{n=1}^\infty [n, n + 1/n] on the real line, where each interval is convex but the sets are disjoint for sufficiently large n; the resulting union is disconnected and hence not convex, as line segments between points in distant intervals pass through gaps.^[19] Convex sets are preserved under convex combinations, which are finite linear combinations with non-negative coefficients summing to one. If x_1, \dots, x_k \in C where C is convex and \lambda_1, \dots, \lambda_k \geq 0 with \sum_{i=1}^k \lambda_i = 1, then \sum_{i=1}^k \lambda_i x_i \in C; this follows by iterated application of the two-point convexity condition. In fact, a set is convex if and only if it contains all convex combinations of its points.^[2] This intersection property has key applications in optimization, particularly linear programming, where the feasible region is defined as the intersection of half-spaces given by linear inequalities a_i^\top x \leq b_i. Each half-space \{x \mid a_i^\top x \leq b_i\} is convex, so their intersection—the feasible region—is convex, ensuring that local optima are global.^[2]

Closed and Open Convex Sets

In Euclidean space \mathbb{R}^n, an open convex set C is defined as a convex set that coincides with the interior of its closure, ensuring that every line segment connecting two points in C lies entirely within an open neighborhood of C.^[22] This property implies that open convex sets are "regular open," meaning they equal the interior of their topological closure, which preserves convexity under such operations.^[22] A closed convex set C in \mathbb{R}^n is the intersection of all closed half-spaces that contain it, where a closed half-space is defined as \{x \in \mathbb{R}^n \mid a^T x + b \leq 0\} for some a \in \mathbb{R}^n and b \in \mathbb{R}.^[10] This representation highlights the topological stability of closed convex sets, as their boundaries are included, and they arise naturally from finite or infinite intersections of such half-spaces. The Hahn-Banach separation theorem further implies that if a closed convex set C is disjoint from another convex set with nonempty interior, there exists a hyperplane strictly separating them, with C lying entirely on one closed side.^[23] For convex sets with empty interior, such as line segments or polyhedra of lower dimension in \mathbb{R}^n, the relative interior provides a useful topological refinement. The relative interior of a convex set C, denoted \operatorname{ri}(C), consists of all points x \in C such that there exists \epsilon > 0 with B(x, \epsilon) \cap \operatorname{aff}(C) \subseteq C, where \operatorname{aff}(C) is the affine hull of C—the smallest affine subspace containing C.^[24] This set \operatorname{ri}(C) is nonempty and convex, shares the same affine hull as C, and satisfies \operatorname{ri}(C) = \operatorname{ri}(\operatorname{cl}(C)) and \operatorname{cl}(\operatorname{ri}(C)) = \operatorname{cl}(C).^[24] Examples illustrate these concepts clearly. The open unit ball \{x \in \mathbb{R}^n \mid \|x\| < 1\} is an open convex set, as it is the interior of its closure, the closed unit ball \{x \in \mathbb{R}^n \mid \|x\| \leq 1\}, which is itself a closed convex set representable as the intersection of closed half-spaces tangent to its boundary.^[10] Similarly, an open half-space \{x \in \mathbb{R}^n \mid a^T x + b < 0\} is open and convex, while its closed counterpart \{x \in \mathbb{R}^n \mid a^T x + b \leq 0\} is closed and convex. For a lower-dimensional example, the relative interior of the line segment [0,1] \times \{0\}^{n-1} in \mathbb{R}^n is the open segment (0,1) \times \{0\}^{n-1} relative to its affine hull, the line through the origin and the standard basis vector.^[24] In general, convex sets in \mathbb{R}^n with nonempty interior can be open (e.g., open balls or open half-spaces), closed (e.g., closed balls or closed half-spaces), or neither, but the closure \operatorname{cl}(C) of a convex set C remains convex, and if C is open, then \operatorname{int}(\operatorname{cl}(C)) = C. Closed convex sets can be obtained as intersections of closed half-spaces containing the original set.^[22]^[10]

Faces and Extreme Points

In convex analysis, a face of a convex set C is a convex subset F \subseteq C such that if x, y \in C and \lambda x + (1 - \lambda) y \in F for some \lambda \in (0,1), then x, y \in F. This definition captures the boundary components that cannot be "entered" from the interior of C via line segments. The empty set and C itself are trivially faces, but proper faces are nonempty and strictly contained in C.^[25] Extreme points are the minimal faces of dimension zero: a point x \in C is extreme if it is not the interior point of any line segment in C, meaning that if x = \lambda y + (1 - \lambda) z with y, z \in C and \lambda \in (0,1), then y = z = x. In closed convex sets, extreme points lie on the boundary.^[26] For example, in a polytope such as a simplex or cube, the vertices are precisely the extreme points, while edges form one-dimensional faces and facets are higher-dimensional faces.^[25] An exposed face is a special type of face that arises as the intersection of C with a supporting hyperplane: F = C \cap H, where H = \{ z \in V \mid \langle w, z \rangle = r \} for some w \in V^* \setminus \{0\} and r \in \mathbb{R} such that \langle w, x \rangle \leq r for all x \in C.^[27] Exposed faces include exposed points, which are extreme points defined by such hyperplanes; not all faces are exposed, as seen in certain non-polyhedral convex sets.^[28] The collection of all faces of C, ordered by inclusion, forms a complete lattice under intersection (meet) and convex hull (join), with the empty set as the bottom element and C as the top. Every nonempty compact convex set in a locally convex topological vector space has at least one extreme point.^[26] More strongly, the Krein-Milman theorem asserts that any compact convex set K equals the closed convex hull of its extreme points: K = \overline{\operatorname{conv}(\operatorname{ext}(K))}. This representation highlights the foundational role of extreme points in structuring compact convex sets.

Convex Hull and Minkowski Operations

Convex Hull

The convex hull of a set S in a real vector space, denoted \operatorname{conv}(S), is defined as the intersection of all convex sets that contain S.^[29] Equivalently, \operatorname{conv}(S) consists of all convex combinations of points from S, that is, all finite sums \sum_{i=1}^k \lambda_i x_i where x_i \in S, \lambda_i \geq 0, and \sum_{i=1}^k \lambda_i = 1.^[29] By construction, \operatorname{conv}(S) is the smallest convex set containing S, and it is itself convex. Carathéodory's theorem provides a refinement for the representation of points in the convex hull: in \mathbb{R}^n, every point in \operatorname{conv}(S) can be expressed as a convex combination of at most n+1 points from S.^[29] This bound is sharp, as the vertices of a simplex in \mathbb{R}^n require exactly n+1 points to form their hull.^[29] Key properties of the convex hull include the preservation of compactness: if S is compact, then \operatorname{conv}(S) is also compact.^[29] Additionally, the affine dimension of \operatorname{conv}(S) equals that of S, defined as the dimension of the affine hull \operatorname{aff}(S), which is the smallest affine subspace containing S.^[30] For a finite set of points in \mathbb{R}^d, \operatorname{conv}(S) forms a convex polytope whose vertices are a subset of the points in S. Computing this polytope can be done using the gift wrapping algorithm (also known as Jarvis's march), which starts from an extreme point (such as the leftmost) and iteratively selects the next hull vertex by finding the point that makes the smallest counterclockwise angle with the previous edge, wrapping around until closing the boundary.^[31] This algorithm runs in O(nh) time, where n is the number of points and h is the number of hull vertices, making it efficient when h is small.^[31] A representative example is the convex hull of the vertices of a polyhedron, which recovers the entire polyhedron itself. In infinite-dimensional spaces, the Krein-Milman theorem extends this idea by stating that a compact convex set is the closed convex hull of its extreme points.^[32]

Minkowski Sum

The Minkowski sum of two sets A and B in a Euclidean space is defined as the set A + B = \{a + b \mid a \in A, b \in B\}. This operation represents the vector addition of all elements from the two sets and is fundamental in convex geometry for combining shapes.^[33] The Minkowski sum preserves convexity: if both A and B are convex, then A + B is also convex. This follows from the fact that any line segment connecting points in A + B can be expressed as a convex combination that lies within the sum due to the convexity of the operands. Similarly, the sum preserves closure and openness: if A and B are closed (or open), so is A + B. Additionally, the operation is compatible with positive scaling, satisfying \lambda (A + B) = \lambda A + \lambda B for any scalar \lambda \geq 0. This homogeneity property underscores the linear nature of the Minkowski sum in convex analysis.^[34]^[35] Representative examples illustrate the geometric effect of the Minkowski sum on convex sets. For instance, the sum of two line segments in the plane yields a parallelogram, with the vertices formed by adding the endpoints of the segments. In three dimensions, the Minkowski sum of two balls centered at the origin with radii r and s results in a ball of radius r + s, demonstrating how the operation expands volumes additively for such symmetric convex bodies.^[36] In applications, Minkowski sums play a key role in robotics for constructing configuration spaces, where the sum of a robot's shape and obstacle geometries defines the forbidden regions for motion planning, enabling efficient collision avoidance. In optimization, the support function of A + B, defined as h_{A+B}(u) = \sup_{x \in A+B} \langle x, u \rangle, equals h_A(u) + h_B(u) for any direction u, facilitating the analysis of composite convex constraints and duality in problems like linear programming over polytopes.^[37]^[38]

Mixed Operations and Properties

A fundamental result concerning the interaction between convex hulls and Minkowski sums states that for any subsets A and B of \mathbb{R}^n, the convex hull of their Minkowski sum equals the Minkowski sum of their convex hulls: \operatorname{conv}(A + B) = \operatorname{conv}(A) + \operatorname{conv}(B). This equality implies that taking convex hulls and forming Minkowski sums commute, preserving the structure of the resulting set as convex. The Brunn–Minkowski inequality provides a key quantitative relation for the volumes of Minkowski sums of compact convex sets. Specifically, for non-empty compact convex sets A and B in \mathbb{R}^n, the inequality asserts that |A + B|^{1/n} \geq |A|^{1/n} + |B|^{1/n}, where |\cdot| denotes the n-dimensional Lebesgue measure. Equality holds if and only if A and B are homothetic, meaning there exist \lambda \geq 0, x \in \mathbb{R}^n, and \mu > 0 such that B = \lambda(A - x) + x or vice versa. Mixed volumes arise naturally in the study of volumes of Minkowski sums and generalize the Brunn–Minkowski inequality. For compact convex sets K_1, \dots, K_n in \mathbb{R}^n, the volume of the sum \lambda_1 K_1 + \cdots + \lambda_n K_n expands as a homogeneous polynomial of degree n: | \lambda_1 K_1 + \cdots + \lambda_n K_n | = \sum_{i_1 + \cdots + i_n = n} \binom{n}{i_1, \dots, i_n} V(K_1[i_1], \dots, K_n[i_n]) \lambda_1^{i_1} \cdots \lambda_n^{i_n}, where V(K_1[i_1], \dots, K_n[i_n]) are the mixed volumes. The case n=2 with two sets recovers the classical mixed area, and in general, mixed volumes encode intrinsic geometric information about the sets involved. These mixed operations and properties find significant applications in convex geometry, particularly in establishing isoperimetric inequalities that relate volumes and surface areas of convex bodies. For instance, the Brunn–Minkowski inequality underpins proofs of the classical isoperimetric inequality for convex sets in \mathbb{R}^n, bounding the surface area in terms of volume.

Extensions and Generalizations

A set S \subseteq \mathbb{R}^n is star-convex (also known as star-shaped or radially convex) if there exists a point x_0 \in S such that for every y \in S, the entire line segment [x_0, y] lies in S.^[39] This point x_0 is called a center or kernel point for S. The kernel of S, denoted \ker S, is the set of all such points x \in S from which every point in S is visible, meaning the line segment connecting them remains in S.^[40] The kernel is itself a convex set, as established by early results in convex geometry. Star-convex sets are always path-connected, since any two points y, z \in S can be joined by a path y to x_0 to z within S, and path-connectedness implies connectedness.^[39] However, star-convexity is a weaker condition than convexity: while every convex set is star-convex (with the kernel being the entire set), the converse does not hold, as star-convex sets need only contain segments from one fixed point, not between arbitrary pairs.^[39] Examples of star-convex sets include cones, where the apex serves as the kernel point, allowing all radial segments to stay within the set.^[40] Certain spiral regions, like a disk with a radial spiral arm emanating from the center, are also star-convex from that center.^[40] In contrast, an annulus (the region between two concentric circles) is not star-convex, as no single point allows visibility to all parts without the segment exiting the set.^[41] A related notion is orthogonal convexity (also called rectilinear or ortho-convexity), which relaxes standard convexity to axis-aligned directions in the plane. A set S \subseteq \mathbb{R}^2 is orthogonally convex if its intersection with every horizontal or vertical line is either empty or a single connected interval.^[42] This ensures the set is "convex" along orthogonal axes but may not be convex in the Euclidean sense; for example, an L-shaped rectilinear polygon (formed by two axis-aligned rectangles sharing a corner) is orthogonally convex, as do any horizontal or vertical line intersects it in at most one segment.^[42] Staircase shapes, such as a monotonically increasing step function boundary in the first quadrant, provide another illustration, useful in computational geometry for bounding rectilinear point sets.^[42] Orthogonal convexity differs from star-convexity but shares the property of being a weakening of full convexity, often applied in contexts like VLSI design where axis-aligned features predominate.^[42]

Convexity in Non-Euclidean Geometry

In non-Euclidean geometries, such as hyperbolic and spherical spaces, the concept of convexity is adapted by replacing Euclidean straight lines with geodesics, the shortest paths on the manifold. This geodesic convexity preserves many intuitive properties while accounting for the underlying curvature, enabling the study of convex sets in spaces where parallel lines diverge (hyperbolic) or converge (spherical). These adaptations are crucial for applications in optimization and geometry on curved spaces, where Euclidean notions fail.^[43] In hyperbolic space \mathbb{H}^n, a set C is geodesically convex if, for any two points in C, the unique hyperbolic geodesic segment joining them lies entirely within C. This definition aligns with the negative curvature of the space, ensuring unique geodesics between points and allowing for globally convex sets without the restrictions seen in positive curvature spaces. The intersection of any family of convex sets is convex, and the convex hull of a set X \subseteq \mathbb{H}^n exists as the smallest convex set containing X, formed by the intersection of all such sets. Examples include hyperbolic balls, which are convex and bounded by hyperspheres, and totally geodesic subspaces analogous to hyperplanes. Unlike Euclidean space, the volume of convex hulls in \mathbb{H}^n is bounded by C_n N for some constant C_n depending on dimension n, growing at most linearly with the number of generating points. Applications arise in machine learning optimization, where hyperbolically convex functions facilitate gradient-based methods on tree-like data structures.^[43]^[44]^[45]^[43] In spherical geometry on the unit sphere S^n, a set is spherically convex if it contains no pair of antipodal points and, for every pair of points in the set, at least one minimal geodesic arc (great circle segment shorter than \pi) joining them lies entirely within the set. Due to the positive curvature, convexity is inherently local: no spherically convex set can exceed a hemisphere, with closed convex sets contained in closed hemispheres and open ones in open hemispheres. The boundary of such sets consists of great circle arcs, and spherical polygons—intersections of hemispheres—serve as prototypical examples. Key properties include Helly-type theorems: for m \geq n+1 spherically convex sets on S^n, if every n+1 intersect nonemptily, then all intersect; and Carathéodory-type results, where any point in the spherical convex hull of a set is an s-convex combination of at most n+1 points from it. These differ from hyperbolic convexity, as multiple minimal geodesics may exist, limiting global extensions and requiring careful handling of antipodes. Applications include motion planning on Riemannian manifolds, such as robotics on curved surfaces, and sampling algorithms for optimization over geodesically convex sets in non-Euclidean domains.^[46]^[47]^[47]^[47]^[48]^[49]

Abstract Convex Structures

Abstract convex structures generalize the notion of convexity from vector spaces to arbitrary sets equipped with suitable axiomatic frameworks, allowing the study of convexity-like properties in combinatorial, order-theoretic, and other non-linear settings. These structures typically involve a family of "convex" subsets closed under intersections and containing certain basic elements, often with additional axioms to ensure geometric or topological coherence. Such generalizations facilitate applications in optimization, geometry, and algebra where traditional Euclidean convexity does not apply. A fundamental example is the convexity space, defined as a pair (X, \mathcal{C}) where X is a set and \mathcal{C} is a family of subsets of X that includes X and all singletons, is closed under arbitrary intersections, and often satisfies further axioms like the Pasch axiom. The Pasch axiom states that for points a, b, c \in X and y \in \mathcal{C}(a, c), z \in \mathcal{C}(b, y), there exists x \in \mathcal{C}(a, b) such that z \in \mathcal{C}(c, x), where \mathcal{C}(p, q) denotes the "interval" or convex hull between p and q. This axiom ensures a form of planarity or separation, analogous to Pasch's axiom in Euclidean geometry. Examples include order-convex sets in partially ordered sets (posets), where a subset C \subseteq P is convex if for all a, b \in C and x \in P with a \leq x \leq b, it follows that x \in C. In posets, the family of order-convex sets forms a convexity space closed under arbitrary intersections.^[50]^[51]^[52] In linearly ordered sets (chains), convex sets coincide with intervals, including open, closed, or half-open variants, and the order topology is generated by these intervals as a basis. This structure preserves key convexity properties like intersection stability and provides a bridge to topological considerations in abstract settings. More generally, in the framework of convex spaces developed by van de Vel, convexity is axiomatized using convex combinations as primitives: a convex space is a set X with operations c_p: X \times X \to X for each p \in [0,1] satisfying idempotence (c_p(x,x) = x), continuity in parameters, and commutativity, allowing the definition of convex sets as those closed under these operations. This approach unifies various convexities, including those from metric spaces and lattices.^[53] Generalizations extend these ideas further; for instance, anticonvex sets in optimization contexts are those where optimization problems involve maximizing convex functions over convex domains or minimizing convex functions over complements, leading to dualities distinct from standard convex programs. Pseudoconvexity generalizes convexity for functions in optimization: a differentiable function f is pseudoconvex on a convex set if for all x, y with f(y) < f(x), the directional derivative satisfies \nabla f(x) \cdot (y - x) < 0, ensuring local minima are global without full convexity. These notions appear in abstract convexity to handle non-linear relaxations.^[54] Key properties of abstract convex structures include preservation under morphisms: a convexity-preserving map f: (X, \mathcal{C}_X) \to (Y, \mathcal{C}_Y) satisfies f(C) \in \mathcal{C}_Y for all C \in \mathcal{C}_X, enabling categorical comparisons between spaces, such as embeddings of poset convexities into metric ones. These structures relate to metric convexity, where convex sets in a metric space are those containing shortest paths (geodesics) between points; abstract frameworks often recover metric convexity when equipped with a compatible distance, as in B-convexity spaces.^[55] The development of abstract convex structures gained momentum in the 1970s and 1980s, driven by applications in combinatorial geometry, such as convex geometries (antimatroids) introduced by Edelman and Jamison in 1985 to model abstract separation and closure properties in discrete settings like posets and graphs. Van de Vel's comprehensive theory in the early 1990s synthesized these advances, emphasizing axiomatic uniformity for non-Euclidean contexts.

References

[1]
[PDF] Convex Optimization
This book is about convex optimization, a special class of mathematical optimiza- tion problems, which includes least-squares and linear programming ...
[2]
[PDF] sets.pdf - Convex Optimization
Convex Optimization. Boyd and Vandenberghe. 2.17. Page 20. Outline. Some standard convex sets. Operations that preserve convexity. Generalized inequalities.
[3]
[PDF] Convex Optimization Overview - Stanford Engineering Everywhere
Oct 19, 2007 · Convex functions give rise to a particularly important type of convex set called an α-sublevel set. Given a convex function f : Rn → R and a ...
[4]
[PDF] Introduction to Convex Constrained Optimization
5.1 Convex Sets and Functions. Convex sets and convex functions play an extremely important role in the study of optimization models. We start with the ...Missing: mathematics | Show results with:mathematics
[5]
[PDF] Lecture 4: Convexity 4.1 Basic Definitions
Definition 4.13 The convex hull of a set C is the set of all convex combinations of the points in C ... We can represent a convex set in two equivalent ways.
[6]
[PDF] 2. Convexity
Note also that the definition doesn't require C to contain two different points, or even a point at all: the empty set is convex, and so is every singleton set.
[7]
(PDF) From measuring tool to geometrical object: Minkowski's ...
Aug 7, 2025 · him to deﬁne the mathematical object we today think of as a convex set. 2.1 The minimum problem in a number theoretical framework.<|control11|><|separator|>
[8]
[PDF] Chapter 3 Basic Properties of Convex Sets - CIS UPenn
We have the following important propo- sition first proved by Minkowski (1896):. Proposition 4.2.1 (Minkowski) Let A be a nonempty closed and convex subset.
[9]
[PDF] Topic 1: Convex sets and functions
1.1. 1 Definition A subset C of a real vector space X is a convex set if it includes the line segment joining any two of its points. That is, C is convex if ...Missing: reliable sources
[10]
[PDF] Lecture 3: September 4 3.1 Convex Sets
3.1 Convex Sets. Definition 3.1 A set C is convex if the line segment between any two points in C lies in C, i.e. ∀x1,x2 ∈ C, ∀θ ∈ [0, 1] θx1 + (1 − θ)x2 ∈ C. ...Missing: reliable sources
[11]
[PDF] Convex sets - CMU School of Computer Science
We say a set C is convex if for any two points x, y ∈ C, the line segment. (1 − α)x + αy, λ ∈ [0, 1], lies in C. The emptyset is also regarded as convex. Notice ...
[12]
[PDF] 1. CONVEX SETS - Dartmouth Mathematics
In three dimensions they are sets, bounded by "pieces" of planes that always "bulge out." For instance, tetrahedra, cubes, octahedra, etc., are all such ...
[13]
[PDF] Introduction to convex sets - Math@LSU
Sep 12, 2007 · An m-dimensional simplex is the convex hull of m + 1 affinely independent vectors in E. The dimension of a convex set C is the largest ...<|control11|><|separator|>
[14]
[PDF] Epigraphs • Closed convex functions - MIT OpenCourseWare
We say that f is convex if epi(f) is⌅a convex set. If f(x) ⌘ for all x ⌘ X and X is convex, the definition “coincides” with the earlier one. We say that f is ...
[15]
[PDF] Convexity I: Sets and Functions
convex. • Epigraph characterization: a function f is convex if and only if its epigraph epi(f) = {(x, t) ∈ dom(f) × R : f(x) ≤ t} is a convex set. • Convex ...
[16]
[PDF] STAT 538 Lecture 5 Convex sets c Marina Meil˘a mmp@stat ...
Convex sets in probability. 1. the parameter space of all normal distributions over Rd is a convex set. 2. the (parameter) space of all discrete distributions ...
[17]
[PDF] Decision Making Based on Convex Sets of Probability Distributions
The thesis advanced by this dissertation is that convex sets of probability distributions provide a powerful representational framework for decision making ...
[18]
None
Below is a merged summary of non-convex sets from "Convex Optimization" by Boyd & Vandenberghe, based on the provided segments. To retain all information in a dense and organized manner, I will use a table in CSV format for each category (Unions, Lattices, Shapes, Epigraphs), followed by a narrative summary for additional context and details not easily captured in tables. The table includes page references, descriptions, and URLs where applicable.
[19]
[PDF] 1 Convex Sets, and Convex Functions
The simple example of the two intervals [0, 1] and [2, 3] on the real line shows that the union of two sets is not necessarily convex. On the other hand, we ...
[20]
Why is the Set of Integers Non-Convex? - Math Stack Exchange
Feb 17, 2022 · The set of integers is automatically a non-convex set. This idea often comes up in Optimization - suppose there is some function you are trying to optimize.
[21]
[PDF] A set S in E is convex iff given any two distinct points x and y in
Definition 1.2: A set S in E¹ is affine iff given any two distinct points x and y in S, the line through x and y is in S.
[22]
[PDF] LECTURE SLIDES ON CONVEX ANALYSIS AND ... - MIT
“Convex Analysis and Optimization,” Athena Sci- ... the relative interior of its closure. • Relative ... • The complement of an open convex set is re-.
[23]
[PDF] The Hahn-Banach separation Theorem and other separation results
Aug 18, 2014 · Abstract. This paper will introduce and prove several theorems involving the separation of convex sets by hyperplanes, along with other ...
[24]
[PDF] Algebra of relative interiors and closures • Continuity of convex ...
− The relative interior of a convex set is equal to the relative interior of its closure. − The closure of the relative interior of a con- vex set is equal to ...
[25]
[PDF] Convex sets, convex functions, & some of their properties. (Part I)
Apr 16, 2014 · Put another way, a face F of a convex set C is a convex subset F⊂C such that whenever λx1 + (1 − λ)x2 ∈ F for some λ ∈ (0, 1), x1, x2 ∈ C, we ...
[26]
https://www.mat.unimi.it/users/libor/AnConvessa/ext.pdf
[27]
[PDF] Faces of convex sets: dimensions and regularity
Oct 29, 2020 · If a face can be represented as the intersection of the convex set with its supporting hyperplane, it is called exposed. If every face of a ...
[28]
[0902.3345] Exposed faces of semidefinitely representable sets - arXiv
Feb 19, 2009 · It is known that every face of a spectrahedron is exposed. This is also true in the general context of rigidly convex sets. We study the ...<|separator|>
[29]
[PDF] Convex and Affine Hulls • Caratheodory's Theorem Reading
The convex hull of a compact set is compact. Proof: Let X be compact. We take a sequence in conv(X) and show that it has a convergent sub-.
[30]
[PDF] 1.2 Convex and Affine Hulls
The dimension of a convex set C is defined to be the dimension of aff(C). Definition:(Affinely Independent) x0, ..., xm ∈ Rn are affinely independent if. X λixi ...
[31]
[PDF] 1 Convex Hulls - Jeff Erickson
Perhaps the simplest algorithm for computing convex hulls simply simulates the process of wrapping a piece of string around the points. This algorithm is ...
[32]
[PDF] Extreme points and the Krein–Milman theorem - Caltech
Definition A face of a convex set is a nonempty subset, F, of A with the property that if x, y ∈ A, θ ∈ (0, 1), and θx + (1 − θ)y ∈ F, then x, y ∈ F. A face, F ...
[33]
CGAL 6.1 - 2D Minkowski Sums: User Manual
Given two sets A,B \in \mathbb{R}^d, their Minkowski sum, denoted by A \oplus B, is their point-wise sum, namely the set \left\{ a + b ~|~ a \in A, b \in B \ ...
[34]
[PDF] Lecture 5: Properties of convex sets - CSE - IIT Kanpur
In general, union of two convex sets is not convex. To obtain convex sets from union, we can take convex hull of the union. Exercise 1. Draw two convex sets, ...
[35]
[PDF] SOLUTIONS TO EXERCISES IN AN INTRODUCTION TO CONVEXITY
(i) Prove that, for every λ ∈ IR and A, B ⊆ IRn, it holds that λ(A + B) = λA + λB. (ii) Is it true that (λ + µ)A = λA + µA for every λ, µ ∈ ...
[36]
[PDF] 1 Warm-up problems: 2 Adding planar figures. - Berkeley Math Circle
(viii) Prove that (an interior of a) convex polygon F is centrally symmetric if and only if it cam be written as a Minkowski sum of some number of segments.<|separator|>
[37]
[PDF] Hybrid Motion Planning Using Minkowski Sums - Robotics
Our Approach. We investigate a method, called M-sum planner, that uses the Minkowski sum of the robot and the obstacles to facilitate the process ...
[38]
[PDF] Projection onto Minkowski Sums with Application to Constrained ...
We propose an efficient algorithm for projecting points onto. Minkowski sums of sets, and provide a thorough conver- gence analysis in both convex and non- ...<|separator|>
[39]
Star Convex -- from Wolfram MathWorld
A star convex set is always pathwise-connected, which in turn is always connected.Missing: definition | Show results with:definition
[40]
[PDF] Starshaped Sets, Distance Functions, and Star Hulls by May 1991
May 4, 1991 · Definition 1.3 The ( convex) kernel of a set S ~ Rd is the set of all points x E S such that every point of S is visible from x via S.
[41]
Proof that a set is non-star-shaped. - Math Stack Exchange
Nov 9, 2015 · This set looks like an Annulus, as shown below. ... A union of finitely many closed convex sets is not necessarily locally star-shaped?Star-Convex Set Centers Form Convex Setgeneral topology - Annulus properties - Mathematics Stack ExchangeMore results from math.stackexchange.com
[42]
On the definition and computation of rectilinear convex hulls
From these studies three distinct definitions of rectilinear convex hulls have emerged. We examine these three definitions for point sets in general, pointing ...
[43]
[PDF] Convexity of sets and functions on the hyperbolic space - arXiv
Oct 13, 2021 · 3 Convex sets on the hyperbolic space. In this section we present some properties of the convex sets of the hyperbolic space. It is worth to.
[44]
[PDF] arXiv:2403.11360v2 [math.MG] 2 Sep 2024
Sep 2, 2024 · ... convex sets in the hyperbolic plane is also convex, so we define the convex hull of a set X Ç H2 as the intersection of all convex sets in H2.
[45]
[PDF] Convex Hulls in the Hyperbolic Space - arXiv
Jun 2, 2011 · The aim of this paper is to prove two fairly basic facts about the volume of convex sets in the hyperbolic space.
[46]
[0708.3149] Convexity of Hypersurfaces in Spherical Spaces - arXiv
Aug 23, 2007 · A spherical set is called convex if for every pair of its points there is at least one minimal geodesic segment that joins these points and lies ...
[47]
None
### Summary of Results on Spherically Convex Sets
[48]
Non-Euclidean motion planning with graphs of geodesically convex ...
Dec 16, 2024 · We define a graph of geodesically convex sets (GGCS), the analogue to GCS on a Riemannian manifold. We prove that this formulation has all the ...
[49]
[PDF] Sampling and Optimization on Convex Sets in Riemannian ... - arXiv
Jul 24, 2019 · Abstract. The Euclidean space notion of convex sets (and functions) generalizes to Riemannian manifolds in a natural sense and is called ...
[50]
Separation properties of convexity spaces
the convexity space (X, G) has the Kakutani separation property. Page 4. Vol ... Setting hi = yi for i > 1 above we see that (Q) implies the Pasch axiom.
[51]
[PDF] LINEARIZATION OF AN ABSTRACT CONVEXITY SPACE A Thesis ...
Pasch*s Axiom : A convexity space (X,C) satisfies Pasch*s axiom, if for y e C(a,c) and z C(b,y) , then there is a x e C(a,b), such that z e C(c,x). 2.5.2 ...
[52]
The convexity lattice of a poset | Order
The authors investigate the lattice Co(P) of convex subsets of a general partially ordered set P. In particular, they determine the conditions under which.
[53]
Axioms for convexity - Cambridge University Press
A convexity space is frequently defined to be a family F of subsets of a set X which contains both X itself and the empty set 0 and which is closed under ...
[54]
Duality for Anticonvex Programs | Journal of Global Optimization
Calling anticonvex a program which is either a maximization of a convex function on a convex set or a minimization of a convex function on the set of point.
[55]
[PDF] Abstract convexity in metric spaces - CORE
In general Pasch's axiom does not imply JHC (Chapter II). However in a B-convexity space when means are singletons Pasch's axiom implies JHC as the ...