Convex set

Illustration of a convex set shaped like a deformed circle. The line segment joining points x and y lies completely within the set, illustrated in green. Since this is true for any potential locations of two points within the set, the set is convex.

File:Convex polygon illustration2.svg

Illustration of a non-convex set. The line segment joining points x and y partially extends outside of the set, illustrated in red, and the intersection of the set with the line occurs in two places, illustrated in black.

In geometry, a set of points is convex if it contains every line segment between two points in the set.<ref>Template:Cite book</ref><ref>Template:Cite journal</ref> For example, a solid cube is a convex set, but anything that is hollow or has an indent, for example, 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 Template:Mvar of Euclidean space is called the convex hull of Template:Mvar. It is the smallest convex set containing Template:Mvar.

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.

DefinitionsEdit

File:Convex supergraph.svg

A function is convex if and only if its epigraph, the region (in green) above its graph (in blue), is a convex set.

Let Template:Mvar 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 Template:Mvar of Template:Mvar is convex if, for all Template:Mvar and Template:Mvar in Template:Mvar, the line segment connecting Template:Mvar and Template:Mvar is included in Template:Mvar.

This means that the affine combination Template:Math belongs to Template:Mvar for all Template:Mvar in Template:Mvar and Template:Mvar in the interval Template:Math. 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 Template:Mvar is Template:Visible anchor if every point on the line segment connecting Template:Mvar and Template:Mvar other than the endpoints is inside the topological interior of Template:Mvar. A closed convex subset is strictly convex if and only if every one of its boundary points is an extreme point.<ref>Template:Halmos A Hilbert Space Problem Book 1982</ref>

A set Template:Mvar is absolutely convex if it is convex and balanced.

ExamplesEdit

The convex subsets of Template:Math (the set of real numbers) are the intervals and the points of Template:Math. 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 setEdit

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,<ref>Template:Cite book.</ref> and some sources more generally use the term concave set to mean a non-convex set,<ref>{{#invoke:Template wrapper|{{#if:|list|wrap}}|_template=cite web |_exclude=urlname, _debug, id |url = https://mathworld.wolfram.com/{{#if:Concave%7CConcave.html}} |title = Concave |author = Weisstein, Eric W. |website = MathWorld |access-date = |ref = Template:SfnRef }}</ref> but most authorities prohibit this usage.<ref>Template:Cite book</ref><ref>Template:Cite book</ref>

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.<ref>Template:Cite journal.</ref>

PropertiesEdit

Given Template:Mvar points Template:Math in a convex set Template:Mvar, and Template:Mvar nonnegative numbers Template:Math such that Template:Math, the affine combination <math display=block>\sum_{k=1}^r\lambda_k u_k</math> belongs to Template:Mvar. As the definition of a convex set is the case Template:Math, this property characterizes convex sets.

Such an affine combination is called a convex combination of Template:Math. The convex hull of a subset Template:Mvar of a real vector space is defined as the intersection of all convex sets that contain Template:Mvar. More concretely, the convex hull is the set of all convex combinations of points in Template:Mvar. In particular, this is a convex set.

A (bounded) convex polytope is the convex hull of a finite subset of some Euclidean space Template:Math.

Intersections and unionsEdit

The collection of convex subsets of a vector space, an affine space, or a Euclidean space has the following properties:<ref name="Soltan" >Soltan, Valeriu, Introduction to the Axiomatic Theory of Convexity, Ştiinţa, Chişinău, 1984 (in Russian). </ref><ref name="Singer" >Template:Cite book</ref>

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 setsEdit

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 Template:Mvar and point Template:Mvar outside it, there is a closed half-space Template:Mvar that contains Template:Mvar and not Template:Mvar. The supporting hyperplane theorem is a special case of the Hahn–Banach theorem of functional analysis.

Face of a convex setEdit

A face of a convex set <math>C</math> is a convex subset <math>F</math> of <math>C</math> such that whenever a point <math>p</math> in <math>F</math> lies strictly between two points <math>x</math> and <math>y</math> in <math>C</math>, both <math>x</math> and <math>y</math> must be in <math>F</math>.Template:Sfn Equivalently, for any <math>x,y\in C</math> and any real number <math>0<t<1</math> such that <math>(1-t)x+ty</math> is in <math>F</math>, <math>x</math> and <math>y</math> must be in <math>F</math>. According to this definition, <math>C</math> itself and the empty set are faces of <math>C</math>; these are sometimes called the trivial faces of <math>C</math>. An extreme point of <math>C</math> is a point that is a face of <math>C</math>.

Let <math>C</math> be a convex set in <math>\R^n</math> that is compact (or equivalently, closed and bounded). Then <math>C</math> is the convex hull of its extreme points.Template:Sfn More generally, each compact convex set in a locally convex topological vector space is the closed convex hull of its extreme points (the Krein–Milman theorem).

For example:

A triangle in the plane (including the region inside) is a compact convex set. Its nontrivial faces are the three vertices and the three edges. (So the only extreme points are the three vertices.)
The only nontrivial faces of the closed unit disk <math>\{ (x,y) \in \R^2: x^2+y^2 \leq 1 \}</math> are its extreme points, namely the points on the unit circle <math>S^1 = \{ (x,y) \in \R^2: x^2+y^2=1 \}</math>.

Convex sets and rectanglesEdit

Let Template:Mvar be a convex body in the plane (a convex set whose interior is non-empty). We can inscribe a rectangle r in Template:Mvar such that a homothetic copy R of r is circumscribed about Template:Mvar. The positive homothety ratio is at most 2 and:<ref>Template:Cite journal</ref> <math display=block>\tfrac{1}{2} \cdot\operatorname{Area}(R) \leq \operatorname{Area}(C) \leq 2\cdot \operatorname{Area}(r)</math>

Blaschke-Santaló diagramsEdit

The set <math>\mathcal{K}^2</math> of all planar convex bodies can be parameterized in terms of the convex body diameter D, its inradius r (the biggest circle contained in the convex body) and its circumradius R (the smallest circle containing the convex body). In fact, this set can be described by the set of inequalities given by<ref name=":0">Template:Cite journal</ref><ref name=":1">Template:Cite journal</ref> <math display=block>2r \le D \le 2R</math> <math display=block>R \le \frac{\sqrt{3}}{3} D</math> <math display=block>r + R \le D</math> <math display=block>D^2 \sqrt{4R^2-D^2} \le 2R (2R + \sqrt{4R^2 -D^2})</math> and can be visualized as the image of the function g that maps a convex body to the Template:Math point given by (r/R, D/2R). The image of this function is known a (r, D, R) Blachke-Santaló diagram.<ref name=":1" />

File:Blaschke-Santaló diagram for planar convex bodies.pdf

Blaschke-Santaló (r, D, R) diagram for planar convex bodies. <math>\mathbb{L}</math> denotes the line segment, <math>\mathbb{I}_{\frac{\pi}{3}}</math> the equilateral triangle, <math>\mathbb{RT}</math> the Reuleaux triangle and <math>\mathbb{B}_2</math> the unit circle.

Alternatively, the set <math>\mathcal{K}^2</math> can also be parametrized by its width (the smallest distance between any two different parallel support hyperplanes), perimeter and area.<ref name=":0" /><ref name=":1" />

Other propertiesEdit

Let X be a topological vector space and <math>C \subseteq X</math> be convex.

<math>\operatorname{Cl} C</math> and <math>\operatorname{Int} C</math> are both convex (i.e. the closure and interior of convex sets are convex).
If <math>a \in \operatorname{Int} C</math> and <math>b \in \operatorname{Cl} C</math> then <math>[a, b[ \, \subseteq \operatorname{Int} C</math> (where <math>[a, b[ \, := \left\{ (1 - r) a + r b : 0 \leq r < 1 \right\}</math>).
If <math>\operatorname{Int} C \neq \emptyset</math> then:
- <math>\operatorname{cl} \left( \operatorname{Int} C \right) = \operatorname{Cl} C</math>, and
- <math>\operatorname{Int} C = \operatorname{Int} \left( \operatorname{Cl} C \right) = C^i</math>, where <math>C^{i}</math> is the algebraic interior of C.

Convex hulls and Minkowski sumsEdit

Convex hullsEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} Every subset Template:Mvar of the vector space is contained within a smallest convex set (called the convex hull of Template:Mvar), namely the intersection of all convex sets containing Template:Mvar. The convex-hull operator Conv() has the characteristic properties of a closure operator:

extensive: Template:Math,
non-decreasing: Template:Math implies that Template:Math, and
idempotent: Template:Math.

The convex-hull operation is needed for the set of convex sets to form a lattice, in which the "join" operation is the convex hull of the union of two convex sets <math display=block>\operatorname{Conv}(S)\vee\operatorname{Conv}(T) = \operatorname{Conv}(S\cup T) = \operatorname{Conv}\bigl(\operatorname{Conv}(S)\cup\operatorname{Conv}(T)\bigr).</math> The intersection of any collection of convex sets is itself convex, so the convex subsets of a (real or complex) vector space form a complete lattice.

Minkowski additionEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}}

File:Minkowski sum graph - vector version.svg

Minkowski addition of sets. The sum of the squares Q₁=[0,1]² and Q₂=[1,2]² is the square Q₁+Q₂=[1,3]².

In a real vector-space, the Minkowski sum of two (non-empty) sets, Template:Math and Template:Math, is defined to be the set Template:Math formed by the addition of vectors element-wise from the summand-sets <math display=block>S_1+S_2=\{x_1+x_2: x_1\in S_1, x_2\in S_2\}.</math> More generally, the Minkowski sum of a finite family of (non-empty) sets Template:Math is the set formed by element-wise addition of vectors <math display=block> \sum_n S_n = \left \{ \sum_n x_n : x_n \in S_n \right \}.</math>

For Minkowski addition, the zero set Template:Math containing only the zero vector Template:Math has special importance: For every non-empty subset S of a vector space <math display=block>S+\{0\}=S;</math> in algebraic terminology, Template:Math is the identity element of Minkowski addition (on the collection of non-empty sets).<ref>The empty set is important in Minkowski addition, because the empty set annihilates every other subset: For every subset Template:Mvar of a vector space, its sum with the empty set is empty: <math>S+\emptyset=\emptyset</math>.</ref>

Convex hulls of Minkowski sumsEdit

Minkowski addition behaves well with respect to the operation of taking convex hulls, as shown by the following proposition:

Let Template:Math be subsets of a real vector-space, the convex hull of their Minkowski sum is the Minkowski sum of their convex hulls <math display=block>\operatorname{Conv}(S_1+S_2)=\operatorname{Conv}(S_1)+\operatorname{Conv}(S_2).</math>

This result holds more generally for each finite collection of non-empty sets: <math display=block>\text{Conv}\left ( \sum_n S_n \right ) = \sum_n \text{Conv} \left (S_n \right).</math>

In mathematical terminology, the operations of Minkowski summation and of forming convex hulls are commuting operations.<ref>Theorem 3 (pages 562–563): Template:Cite journal</ref><ref name="Schneider">For the commutativity of Minkowski addition and convexification, see Theorem 1.1.2 (pages 2–3) in Schneider; this reference discusses much of the literature on the convex hulls of Minkowski sumsets in its "Chapter 3 Minkowski addition" (pages 126–196): Template:Cite book</ref>

Minkowski sums of convex setsEdit

The Minkowski sum of two compact convex sets is compact. The sum of a compact convex set and a closed convex set is closed.<ref>Lemma 5.3: Template:Cite book</ref>

The following famous theorem, proved by Dieudonné in 1966, gives a sufficient condition for the difference of two closed convex subsets to be closed.<ref name="Zalinescu p. 7">Template:Cite book</ref> It uses the concept of a recession cone of a non-empty convex subset S, defined as: <math display=block>\operatorname{rec} S = \left\{ x \in X \, : \, x + S \subseteq S \right\},</math> where this set is a convex cone containing <math>0 \in X </math> and satisfying <math>S + \operatorname{rec} S = S</math>. Note that if S is closed and convex then <math>\operatorname{rec} S</math> is closed and for all <math>s_0 \in S</math>, <math display=block>\operatorname{rec} S = \bigcap_{t > 0} t (S - s_0).</math>

Theorem (Dieudonné). Let A and B be non-empty, closed, and convex subsets of a locally convex topological vector space such that <math>\operatorname{rec} A \cap \operatorname{rec} B</math> is a linear subspace. If A or B is locally compact then A − B is closed.

Generalizations and extensions for convexityEdit

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.

Star-convex (star-shaped) setsEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} Let Template:Mvar be a set in a real or complex vector space. Template:Mvar is star convex (star-shaped) if there exists an Template:Math in Template:Mvar such that the line segment from Template:Math to any point Template:Mvar in Template:Mvar is contained in Template:Mvar. Hence a non-empty convex set is always star-convex but a star-convex set is not always convex.

Orthogonal convexityEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} An example of generalized convexity is orthogonal convexity.<ref>Rawlins G.J.E. and Wood D, "Ortho-convexity and its generalizations", in: Computational Morphology, 137-152. Elsevier, 1988.</ref>

A set Template:Mvar in the Euclidean space is called orthogonally convex or ortho-convex, if any segment parallel to any of the coordinate axes connecting two points of Template:Mvar lies totally within Template:Mvar. 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.

Non-Euclidean geometryEdit

The definition of a convex set and a convex hull extends naturally to geometries which are not Euclidean by defining a geodesically convex set to be one that contains the geodesics joining any two points in the set.

Order topologyEdit

Convexity can be extended for a totally ordered set Template:Mvar endowed with the order topology.<ref>Munkres, James; Topology, Prentice Hall; 2nd edition (December 28, 1999). Template:ISBN.</ref>

Let Template:Math. The subspace Template:Mvar is a convex set if for each pair of points Template:Math in Template:Mvar such that Template:Math, the interval Template:Math is contained in Template:Mvar. That is, Template:Mvar is convex if and only if for all Template:Math in Template:Mvar, Template:Math implies Template:Math.

A convex set is Template:Em connected in general: a counter-example is given by the subspace {1,2,3} in Template:Math, which is both convex and not connected.

Convexity spacesEdit

The notion of convexity may be generalised to other objects, if certain properties of convexity are selected as axioms.

Given a set Template:Mvar, a convexity over Template:Mvar is a collection Template:Math of subsets of Template:Mvar satisfying the following axioms:<ref name="Soltan"/><ref name="Singer"/><ref name="vanDeVel" >Template:Cite book</ref>

The empty set and Template:Mvar are in Template:Math.
The intersection of any collection from Template:Math is in Template:Math.
The union of a chain (with respect to the inclusion relation) of elements of Template:Math is in Template:Math.

The elements of Template:Math are called convex sets and the pair Template:Math is called a convexity 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 to discrete geometry, see the convex geometries associated with antimatroids.

Convex spacesEdit