Convex set

In geometry, a set of points is convex if it contains every line segment between two points in the set. For example, a solid cube is a convex set, but anything that is hollow or has an indent, such as a crescent shape, is not convex. The boundary of a convex set in the plane is always a convex curve. The intersection of all the convex sets that contain a given subset A of Euclidean space is called the convex hull of A. It is the smallest convex set containing A. A convex function is a real-valued function defined on an interval with the property that its epigraph (the set of points on or above the graph of the function) is a convex set. Convex minimization is a subfield of optimization that studies the problem of minimizing convex functions over convex sets. The branch of mathematics devoted to the study of properties of convex sets and convex functions is called convex analysis. Spaces in which convex sets are defined include the Euclidean spaces, the affine spaces over the real numbers, and certain non-Euclidean geometries.

Definitions

Let S be a vector space or an affine space over the real numbers, or, more generally, over some ordered field (this includes Euclidean spaces, which are affine spaces). A subset C of S is convex if, for all x and y in C, the line segment connecting x and y is included in C. This means that the affine combination (1 − t)x + ty belongs to C for all x,y in C and t in the interval [0, 1]. This implies that convexity is invariant under affine transformations. Further, it implies that a convex set in a real or complex topological vector space is path-connected (and therefore also connected). A set C is strictly convex if for every x and y in C, every point on the line segment connecting x and y other than the endpoints is inside the topological interior of C. A closed convex subset is strictly convex if and only if every one of its boundary points is an extreme point. A set C is absolutely convex if it is convex and balanced.

Examples The convex subsets of R (the set of real numbers) are the intervals and the points of R. Some examples of convex subsets of the Euclidean plane are solid regular polygons, solid triangles, and intersections of solid triangles. Some examples of convex subsets of a Euclidean 3-dimensional space are the Archimedean solids and the Platonic solids. The Kepler–Poinsot polyhedra are examples of non-convex sets.

Non-convex set A set that is not convex is called a non-convex set. A polygon that is not a convex polygon is sometimes called a concave polygon, and some sources more generally use the term concave set to mean a non-convex set, but most authorities prohibit this usage. The complement of a convex set, such as the epigraph of a concave function, is sometimes called a reverse convex set, especially in the context of mathematical optimization.

Properties Given r points u1, ..., ur in a convex set S, and r nonnegative numbers λ1, ..., λr such that λ1 + ... + λr = 1, the affine combination

∑ k = 1 r λ k u k {\displaystyle \sum _{k=1}^{r}\lambda _{k}u_{k}}

belongs to S. As the definition of a convex set is the case r = 2, this property characterizes convex sets. Such an affine combination is called a convex combination of u1, ..., ur. The convex hull of a subset S of a real vector space is defined as the intersection of all convex sets that contain S. More concretely, the convex hull is the set of all convex combinations of points in S. In particular, this is a convex set. A (bounded) convex polytope is the convex hull of a finite subset of some Euclidean space Rn.

Intersections and unions The collection of convex subsets of a vector space, an affine space, or a Euclidean space has the following properties:

The empty set and the whole space are convex. The intersection of any collection of convex sets is convex. The union of a collection of convex sets is convex if those sets form a chain (a totally ordered set) under inclusion. For this property, the restriction to chains is important, as the union of two convex sets need not be convex.

Closed convex sets Closed convex sets are convex sets that contain all their limit points. They can be characterised as the intersections of closed half-spaces (sets of points in space that lie on and to one side of a hyperplane). From what has just been said, it is clear that such intersections are convex, and they will also be closed sets. To prove the converse, i.e., every closed convex set may be represented as such intersection, one needs the supporting hyperplane theorem in the form that for a given closed convex set C and point P outside it, there is a closed half-space H that contains C and not P. The supporting hyperplane theorem is a special case of the Hahn–Banach theorem of functional analysis.

… excerpt ends here. Continue reading the full article.