Ingeometry, aset of points isconvex if it contains everyline segment between two points in the set.[1][2]For example, a solidcube is a convex set, but anything that is hollow or has an indent, such as acrescent shape, is not convex.
Theboundary of a convex set in the plane is always aconvex curve. The intersection of all the convex sets that contain a given subsetA of Euclidean space is called theconvex hull ofA. It is the smallest convex set containingA.
Aconvex function is areal-valued function defined on aninterval with the property that itsepigraph (the set of points on or above thegraph of the function) is a convex set.Convex minimization is a subfield ofoptimization 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 calledconvex analysis.
Spaces in which convex sets are defined include theEuclidean spaces, theaffine spaces over thereal numbers, and certainnon-Euclidean geometries.
LetS be avector space or anaffine space over thereal numbers, or, more generally, over someordered field (this includes Euclidean spaces, which are affine spaces). AsubsetC ofS isconvex if, for allx andy inC, theline segment connectingx andy is included inC.
This means that theaffine combination(1 −t)x +ty belongs toC for allx,y inC andt in theinterval[0, 1]. This implies that convexity is invariant underaffine transformations. Further, it implies that a convex set in areal orcomplextopological vector space ispath-connected (and therefore alsoconnected).
A setC isstrictly convex if every point on the line segment connectingx andy other than the endpoints is inside thetopological interior ofC. A closed convex subset is strictly convex if and only if every one of itsboundary points is anextreme point.[3]
A setC isabsolutely convex if it is convex andbalanced.
The convexsubsets ofR (the set of real numbers) are the intervals and the points ofR. Some examples of convex subsets of theEuclidean plane are solidregular polygons, solid triangles, and intersections of solid triangles. Some examples of convex subsets of aEuclidean 3-dimensional space are theArchimedean solids and thePlatonic solids. TheKepler-Poinsot polyhedra are examples of non-convex sets.
A set that is not convex is called anon-convex set. Apolygon that is not aconvex polygon is sometimes called aconcave polygon,[4] and some sources more generally use the termconcave set to mean a non-convex set,[5] but most authorities prohibit this usage.[6][7]
Thecomplement of a convex set, such as theepigraph of aconcave function, is sometimes called areverse convex set, especially in the context ofmathematical optimization.[8]
Givenr pointsu1, ...,ur in a convex setS, andrnonnegative numbersλ1, ...,λr such thatλ1 + ... +λr = 1, theaffine combinationbelongs toS. As the definition of a convex set is the caser = 2, this property characterizes convex sets.
Such an affine combination is called aconvex combination ofu1, ...,ur. Theconvex hull of a subsetS of a real vector space is defined as the intersection of all convex sets that containS. More concretely, the convex hull is the set of all convex combinations of points inS. In particular, this is a convex set.
A(bounded)convex polytope is the convex hull of a finite subset of some Euclidean spaceRn.
The collection of convex subsets of a vector space, an affine space, or aEuclidean space has the following properties:[9][10]
Closed convex sets are convex sets that contain all theirlimit points. They can be characterised as the intersections ofclosedhalf-spaces (sets of points in space that lie on and to one side of ahyperplane).
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 thesupporting hyperplane theorem in the form that for a given closed convex setC and pointP outside it, there is a closed half-spaceH that containsC and notP. The supporting hyperplane theorem is a special case of theHahn–Banach theorem offunctional analysis.
Aface of a convex set is a convex subset of such that whenever a point in lies strictly between two points and in, both and must be in.[11] Equivalently, for any and any real number such that is in, and must be in. According to this definition, itself and the empty set are faces of; these are sometimes called thetrivial faces of. Anextreme point of is a point that is a face of.
Let be a convex set in that iscompact (or equivalently, closed andbounded). Then is the convex hull of its extreme points.[12] More generally, each compact convex set in alocally convex topological vector space is the closed convex hull of its extreme points (theKrein–Milman theorem).
For example:
LetC be aconvex body in the plane (a convex set whose interior is non-empty). We can inscribe a rectangler inC such that ahomothetic copyR ofr is circumscribed aboutC. The positive homothety ratio is at most 2 and:[13]
The set of all planar convex bodies can be parameterized in terms of the convex bodydiameterD, its inradiusr (the biggest circle contained in the convex body) and its circumradiusR (the smallest circle containing the convex body). In fact, this set can be described by the set of inequalities given by[14][15]and can be visualized as the image of the functiong that maps a convex body to theR2 point given by (r/R,D/2R). The image of this function is known a (r,D,R) Blachke-Santaló diagram.[15]
Alternatively, the set can also be parametrized by its width (the smallest distance between any two different parallel support hyperplanes), perimeter and area.[14][15]
LetX be a topological vector space and be convex.
Every subsetA of the vector space is contained within a smallest convex set (called theconvex hull ofA), namely the intersection of all convex sets containingA. The convex-hull operator Conv() has the characteristic properties of aclosure operator:
The convex-hull operation is needed for the set of convex sets to form alattice, in which the"join" operation is the convex hull of the union of two convex setsThe intersection of any collection of convex sets is itself convex, so the convex subsets of a (real or complex) vector space form a completelattice.
![Three squares are shown in the nonnegative quadrant of the Cartesian plane. The square Q1 = [0, 1] × [0, 1] is green. The square Q2 = [1, 2] × [1, 2] is brown, and it sits inside the turquoise square Q1+Q2=[1,3]×[1,3].](/mt/?noimg=&dark=on&url=https%3a%2f%2fen.wikipedia.org%2fwiki%2fFile%3aMinkowski_sum_graph_-_vector_version.svg)
In a real vector-space, theMinkowski sum of two (non-empty) sets,S1 andS2, is defined to be thesetS1 + S2 formed by the addition of vectors element-wise from the summand-setsMore generally, theMinkowski sum of a finite family of (non-empty) setsSn is the set formed by element-wise addition of vectors
For Minkowski addition, thezero set {0} containing only thezero vector 0 hasspecial importance: For every non-empty subset S of a vector spacein algebraic terminology,{0} is theidentity element of Minkowski addition (on the collection of non-empty sets).[16]
Minkowski addition behaves well with respect to the operation of taking convex hulls, as shown by the following proposition:
LetS1,S2 be subsets of a real vector-space, theconvex hull of their Minkowski sum is the Minkowski sum of their convex hulls
This result holds more generally for each finite collection of non-empty sets:
In mathematical terminology, theoperations of Minkowski summation and of formingconvex hulls arecommuting operations.[17][18]
The Minkowski sum of two compact convex sets is compact. The sum of a compact convex set and a closed convex set is closed.[19]
The following famous theorem, proved by Dieudonné in 1966, gives a sufficient condition for the difference of two closed convex subsets to be closed.[20] It uses the concept of arecession cone of a non-empty convex subsetS, defined as:where this set is aconvex cone containing and satisfying. Note that ifS is closed and convex then is closed and for all,
Theorem (Dieudonné). LetA andB be non-empty, closed, and convex subsets of alocally convex topological vector space such that is a linear subspace. IfA orB islocally compact thenA − B is closed.
The notion of convexity in the Euclidean space may be generalized by modifying the definition in some or other aspects. The common name "generalized convexity" is used, because the resulting objects retain certain properties of convex sets.
LetC be a set in a real or complex vector space.C isstar convex (star-shaped) if there exists anx0 inC such that the line segment fromx0 to any pointy inC is contained inC. Hence a non-empty convex set is always star-convex but a star-convex set is not always convex.
An example of generalized convexity isorthogonal convexity.[21]
A setS in the Euclidean space is calledorthogonally convex orortho-convex, if any segment parallel to any of the coordinate axes connecting two points ofS lies totally withinS. It is easy to prove that an intersection of any collection of orthoconvex sets is orthoconvex. Some other properties of convex sets are valid as well.
The definition of a convex set and a convex hull extends naturally to geometries which are not Euclidean by defining ageodesically convex set to be one that contains thegeodesics joining any two points in the set.
Convexity can be extended for atotally ordered setX endowed with theorder topology.[22]
LetY ⊆X. The subspaceY is a convex set if for each pair of pointsa,b inY such thata ≤b, the interval[a,b] = {x ∈X |a ≤x ≤b} is contained inY. That is,Y is convex if and only if for alla,b inY,a ≤b implies[a,b] ⊆Y.
A convex set isnot connected in general: a counter-example is given by the subspace {1,2,3} inZ, which is both convex and not connected.
The notion of convexity may be generalised to other objects, if certain properties of convexity are selected asaxioms.
Given a setX, aconvexity overX is a collection𝒞 of subsets ofX satisfying the following axioms:[9][10][23]
The elements of𝒞 are called convex sets and the pair(X,𝒞) is called aconvexity space. For the ordinary convexity, the first two axioms hold, and the third one is trivial.
For an alternative definition of abstract convexity, more suited todiscrete geometry, see theconvex geometries associated withantimatroids.
Convexity can be generalised as an abstract algebraic structure: a space is convex if it is possible to take convex combinations of points.
An often seen confusion is a "concave set". Concave and convex functions designate certain classes of functions, not of sets, whereas a convex set designates a certain class of sets, and not a class of functions. A "concave set" confuses sets with functions.
There is no such thing as a concave set.
| Spaces |
| ||||
|---|---|---|---|---|---|
| Theorems | |||||
| Operators | |||||
| Algebras | |||||
| Open problems | |||||
| Applications | |||||
| Advanced topics | |||||
| International | |
|---|---|
| National | |
| Other | |
