Convex set

a convex set

a non-convex set

In mathematics , a geometric figure or, more generally, a subset of a Euclidean space is called convex if for any two points that belong to the set, their connecting line always lies entirely in the set. This guarantees that the set has no ( concave ) indentation at any point .

History and application

The theory of convex sets founded Hermann Minkowski in his work geometry of numbers , Leipzig 1910. find application for convex sets. B. in convex optimization or computer animation , where convex polytopes are easier to handle than non- convexes in several respects.

Definition of vector spaces

A subset of a real or complex vector space is called convex if for all and for all with always holds: ${\displaystyle M}$ ${\displaystyle V}$ ${\displaystyle a,b\in M}$ ${\displaystyle \lambda \in \mathbb {R} }$ ${\displaystyle 0\leq \lambda \leq 1}$

${\displaystyle \lambda a+(1-\lambda )b\in M.}$

This definition is based on the parameter representation of the connection between and : ${\displaystyle a}$ ${\displaystyle b}$

${\displaystyle {\overline {ab}}:=\{\lambda a+(1-\lambda )b\mid \lambda \in \mathbb {R} ,0\leq \lambda \leq 1\}.}$

In fact, the above definition also includes objects with straight edges, such as squares , which colloquially would not necessarily be called convex .

Examples

Examples of non-convex figures of the plane

• Any vector space that contains is convex, as are half-planes and half-spaces . ${\displaystyle \mathbb {R} }$
• Example subsets of the descriptive Euclidean space :
  • The empty set and any one-element set are convex.
  • Finite sets are convex if and only if they contain at most one element.
  • Lines and lines are convex sets.
  • Every triangular face and all simple regular polygon faces are convex.
  • Circular disks and spheres are convex, even strictly convex.
  • Among the squares are z. B. the parallelograms convex, while there are trapezoids and dragon squares that are non- convex, such as the crossed trapezoid or the arrow square .
  • Cubes , Platonic Solids and Spades are convex.
  • The subset that lies above or below the graph of a convex or concave function is convex.
  • A torus is not convex.
  • The topological boundary of a convex set is generally non-convex.

properties

• Every convex set is star-shaped , so that any point can be chosen as the star center. In particular, every non-empty convex subset of a real or complex vector space is connected and contractible to a point , so it cannot have any holes.

• The intersection of any number of convex sets (also infinitely) is convex. Thus the convex subsets of a vector space form a hull system . In particular, for each subset there is the convex set generated by it, the so-called convex hull of this set. This is nothing more than the average of all convex sets that comprise the given subset.

• The union of convex sets is generally not convex. But the union of an ascending chain of convex sets is convex again.

• In locally convex spaces a compact , convex set is the closure of the convex combinations of its extremal points ( Kerin-Milman theorem ). An extreme point is a point that is not between two points . In finite-dimensional spaces one can even dispense with the final formation, because according to Carathéodory's theorem , every point of a compact, convex subset of an n-dimensional space is a convex combination of at most n + 1 extreme points of this set. ${\displaystyle M}$ ${\displaystyle M}$

Stability under operations

The convexity of a set is stable under certain operations. Examples are:

• Images and archetypes of convex sets under an affine function with and are again convex. As a special case, this includes the translation by the vector (set the identity matrix) and the scaling by the factor (set ). ${\displaystyle f(x)=Ax+b}$ ${\displaystyle A\in \mathbb {R} ^{m\times n}}$ ${\displaystyle b\in \mathbb {R} ^{m}}$ ${\displaystyle b}$ ${\displaystyle A=E}$ ${\displaystyle a}$ ${\displaystyle A=aE,\,b=0}$
• The Minkowski sum of two convex sets is again convex. ${\displaystyle K_{1}+K_{2}=\{x_{1}+x_{2}|\,x_{1}\in K_{1},\,x_{2}\in K_{2}\}}$
• The Cartesian product of two convex sets is again convex. ${\displaystyle K_{1}\times K_{2}}$
• Every projection of a convex set onto a coordinate axis is again convex. ${\displaystyle f(x)=x_{i}}$
• If the term for each , then the image of the convex set is under the function ${\displaystyle x\in K}$ ${\displaystyle c^{T}x+d>0}$ ${\displaystyle K}$

${\displaystyle f(x)={\frac {Ax+b}{c^{T}x+d}}}$

again convex. Similarly, the archetype of a convex set is again convex under this function.

Special cases

Convex sets can be further restricted in several ways:

• A set is called strictly convex if the open line connecting any two points in the set lies completely inside the set. Clearly, strictly convex sets have no straight boundary parts. ${\displaystyle M}$
• A set is called smoothly convex if every boundary point of the set has a unique supporting hyperplane . Clearly, smooth convex sets have no corners or edges. ${\displaystyle M}$

Standardized spaces

Convexity Conditions

In normalized spaces , that is, in vector spaces with a norm that assigns its length to each vector , convex sets can be constructed using the norm. The most important convex set for the theory of normalized spaces is the unit sphere . ${\displaystyle (V,\|\cdot \|)}$ ${\displaystyle V}$ ${\displaystyle \|\cdot \|}$ ${\displaystyle x\in V}$ ${\displaystyle \|x\|}$ ${\displaystyle B_{V}:=\{x\in V;\,\|x\|\leq 1\}}$

Certain convexity conditions that can be placed on the unit sphere of a standardized space and that sharpen the convexity of the unit sphere define room classes of standardized spaces. This leads to concepts such as strictly convex , uniformly convex or smooth spaces .

Normal structure

A point of a bounded, convex set is called diametrical for M if is equal to the diameter of . In the unit sphere, exactly the edge points, i.e. the vectors of length 1, are diametrically opposite. For a segment in a normalized space, the end points of this segment are exactly diametrical. In these two examples there are always non-diametrical points. This is considered a "normal" property and defines: ${\displaystyle x}$ ${\displaystyle M\subset V}$ ${\displaystyle \sup\{\|x-y\|;\,y\in M\}}$ ${\displaystyle M}$

A bounded, convex set has normal structure if every closed and convex subset it contains with at least two points contains non-diametrical points with respect to . ${\displaystyle M}$ ${\displaystyle M}$

One can show that every compact, convex set in a normalized space has a normal structure. Since bounded, closed sets in finite-dimensional spaces are compact according to Heine-Borel's theorem , all bounded, convex sets in finite-dimensional spaces have normal structures. The occurrence of bounded, convex sets without a normal structure is therefore a purely infinite-dimensional phenomenon.

Generalizations

In general, considerably weaker prerequisites for the geometry that apply to are sufficient for a meaningful definition of convexity . From Hilbert's system of axioms of Euclidean geometry, one only needs the axioms of connection and those of arrangement. The convexity depends in particular on the definition of a straight connection path. The half-plane defined by is convex in the Euclidean plane , but non- convex in the Moulton plane : For example, the “straight line” runs between and over the point (not included in the set) . See also collinear . ${\displaystyle M}$ ${\displaystyle \{(x,y)\in \mathbb {R} ^{2}\mid x+y\leq 0\}}$ ${\displaystyle (-1,1)}$ ${\displaystyle (1,-1)}$ ${\displaystyle (0,{\tfrac {1}{3}})}$

Depending on the mathematical context, different generalizations are used, some of which are not coherent.

Convexity space

The following axiomatic generalizes the fundamental properties of convex sets on a level comparable to that of topology .

A set together with a set of subsets is called a convexity space if : ${\displaystyle X}$ ${\displaystyle {\mathcal {K}}\subseteq {\mathcal {P}}(X)}$ ${\displaystyle {\mathcal {K}}}$

• the empty set and yourself lie in ${\displaystyle X}$ ${\displaystyle {\mathcal {K}}}$
• the intersection of any number of sets is again in ${\displaystyle {\mathcal {K}}}$ ${\displaystyle {\mathcal {K}}}$
• If a subset totally ordered is with respect to inclusion , so that lies union of all sets of in . ${\displaystyle K\subset {\mathcal {K}}}$ ${\displaystyle K}$ ${\displaystyle {\mathcal {K}}}$

Then the sets from are called the convex sets of . ${\displaystyle {\mathcal {K}}}$ ${\displaystyle X}$

Metrically convex space

A circle is metrically convex, but as a subset of Euclidean space, it is non-convex.

A metric space is called metrically convex if there is always a third point for every two different points such that the triangle inequality is even equal: ${\displaystyle (X,d)}$ ${\displaystyle x,y\in X}$ ${\displaystyle z\in X\setminus \{x,y\}}$

${\displaystyle d(x,y)=d(x,z)+d(z,y)}$ .

From a point which satisfies this condition one then says: ${\displaystyle z\in X\setminus \{x,y\}}$

${\displaystyle z}$lies between and ${\displaystyle x}$ ${\displaystyle y}$ .

Here, however, it is no longer true that the intersection of metrically convex sets is metrically convex again. The circular line with the metric of the arc length is metrically convex, two closed semicircles , which are disjoint apart from their two end points , are also metrically convex (partial) sets, but their two-element section is not. ${\displaystyle x,y}$ ${\displaystyle \{x,y\}}$

The basic result about metrically convex spaces is Menger's connectivity theorem .

Geodetically convex manifolds

Semi-Riemannian manifolds have an inherent metric that determines the geodesics of the manifold. If every pair of points in a neighborhood can be connected by a single geodesic of the manifold that lies entirely in this neighborhood, this neighborhood is simply called convex . ${\displaystyle (M,g)}$

A submanifold a Riemannian manifold is geodetically convex if any two points by a curve in can be connected to an in length minimizing global geodesic is. ${\displaystyle C\subset M}$ ${\displaystyle (M,g)}$ ${\displaystyle x,y\in C}$ ${\displaystyle C}$ ${\displaystyle (M,g)}$

Examples and differences

• The rational numbers with the usual spacing form a metrically convex subset of that is not convex. ${\displaystyle \mathbb {R} }$
• The same applies to what is also not geodetically convex as a Riemannian manifold. ${\displaystyle \mathbb {R} ^{2}\backslash \{0\}}$
• A convex subset of Euclidean space is always metrically convex with respect to the metric induced by the norm . The reverse also applies to closed subsets.

Curvature of curves

A function is convex if and only if its epigraph , in this picture the green set above the blue function graph , is a convex set.

In two-dimensional , the curvature of a continuously differentiable curve can be examined at a point in relation to the viewer: ${\displaystyle x_{0}}$

• If the neighboring points in the same tangential - half plane as the viewer, so it's there for him concaved . ${\displaystyle x_{0}}$
• If there is a surrounding area so that all points from it lie in the other tangential half-plane, then the curve in is convexly curved for the viewer . ${\displaystyle x_{0}}$ ${\displaystyle x_{0}}$

Corners are called convex if all interior angles are at most 180 °.

Similarly, the curvature of hyperplanes can be investigated in higher dimensions , but for this purpose the object must be orientable .

Classical results over convex sets (selection)

• Bieberbach's inequality
• Blaschke's selection sentence
• Brunn-Minkowski inequality
• Cauchy's theorem
• Euler's polyhedron formula
• Helly theorem
• Jung's theorem
• Lemma of Kakutani
• Minkowski's theorem
• Minkovskian grid point theorem
• Theorem of Pick
• Theorem of radon
• Separation sentence

See also

• Absolutely convex set
• Hilbert metric
• Convex function
• Simplex (math)
• Generalized convexity

literature

• Tommy Bonnesen , Werner Fennel : Theory of convex bodies . Corrected reprint. Springer-Verlag , Berlin (inter alia) 1974, ISBN 3-540-06234-3 .
• Arne Brøndsted: An introduction to convex polytopes . Springer-Verlag, New York (inter alia) 1983, ISBN 0-387-90722-X .
• Leonard M. Blumenthal : Theory and Applications of Distance Geometry (=  Chelsea Scientific Books ). 2nd Edition. Chelsea Publishing Company , Bronx, New York 1970, ISBN 0-8284-0242-6 .
• WA Coppel: Foundations of Convex Geometry . Cambridge University Press , Cambridge 1998, ISBN 0-521-63970-0 .
• Kazimierz Goebel , William A. Kirk : Topics in Metric Fixed Point Theory (=  Cambridge Studies in Advanced Mathematics . Volume 28 ). Cambridge University Press , Cambridge 1990, ISBN 0-521-38289-0 .
• Peter M. Gruber: Convex and Discrete Geometry . Springer-Verlag, Berlin (inter alia) 2007, ISBN 978-3-540-71132-2 .
• Isaak M. Jaglom and WG Boltjansky : Convex figures . German Science Publishing House , Berlin 1956.
• Otto Kerner, Joseph Maurer, Jutta Steffens, Thomas Thode, Rudolf Voller: Vieweg Mathematik Lexikon . Vieweg Verlag , Braunschweig (inter alia) 1988, ISBN 3-528-06308-4 , p. 159-160 .
• Victor L. Klee (Ed.): Convexity . Proceedings of the Seventh Symposium in Pure Mathematics of the American Mathematical Society, held at the University of Washington, Seattle, Washington, June 13-15, 1961. American Mathematical Society , Providence, RI 1963.
• Steven R. Lay: Convex sets and their applications . John Wiley & Sons , New York (et al.) 1982, ISBN 0-471-09584-2 .
• Kurt Leichtweiß: Convex sets . Springer-Verlag, Berlin [a. a.] 1980, ISBN 3-540-09071-1 .
• Jürg T. Marti: Convex Analysis . Birkhäuser , Basel (inter alia) 1977, ISBN 3-7643-0839-7 .
• Willi Rinow : The inner geometry of the metric spaces (=  The basic teachings of the mathematical sciences in individual representations with special consideration of the areas of application . Volume 105 ). Springer Verlag , Berlin, Göttingen, Heidelberg 1961.
• Frederick A. Valentine : Convex sets (=  BI university pocket books. 402 / 402a). Bibliographical Institute , Mannheim 1968.

Web links

Commons : (non) convex sets  - collection of images, videos and audio files

• Convex on PlanetMath
• Niels Lauritzen: Lectures on Convex Sets (pdf)
• Convex set in the Encyclopaedia of Mathematics

Individual evidence

1. ^ Robert Plato: Numerical Mathematics compact . Springer, 2013, ISBN 978-3-322-93922-7 , pp. 365 .
2. ↑ Jürg T. Marti: Convex Analysis . Springer, 2013, ISBN 978-3-0348-5910-3 , pp. 108 .
3. ^ Vasile I. Istratescu: Strict Convexity and Complex Strict Convexity, Theory and Applications , Taylor & Francis Inc. (1983), ISBN 0-8247-1796-1 , sentence 2.11.20