Английская Википедия:Convex set

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Файл:Convex polygon illustration1.svg

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.

Файл: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 subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex region is a subset that intersects every line into a single line segment (possibly empty). 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 Шаблон:Mvar of Euclidean space is called the convex hull of Шаблон:Mvar. It is the smallest convex set containing Шаблон: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.

The notion of a convex set can be generalized as described below.

Definitions

Файл: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 Шаблон: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 Шаблон:Mvar of Шаблон:Mvar is convex if, for all Шаблон:Mvar and Шаблон:Mvar in Шаблон:Mvar, the line segment connecting Шаблон:Mvar and Шаблон:Mvar is included in Шаблон:Mvar.

This means that the affine combination Шаблон:Math belongs to Шаблон:Mvar for all Шаблон:Mvar in Шаблон:Mvar and Шаблон:Mvar in the interval Шаблон: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 Шаблон:Mvar is Шаблон:Visible anchor if every point on the line segment connecting Шаблон:Mvar and Шаблон:Mvar other than the endpoints is inside the topological interior of Шаблон:Mvar. A closed convex subset is strictly convex if and only if every one of its boundary points is an extreme point.

A set Шаблон:Mvar is absolutely convex if it is convex and balanced.

Examples

The convex subsets of Шаблон:Math (the set of real numbers) are the intervals and the points of Шаблон: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 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 Шаблон:Mvar points Шаблон:Math in a convex set Шаблон:Mvar, and Шаблон:Mvar nonnegative numbers Шаблон:Math such that Шаблон:Math, the affine combination <math display=block>\sum_{k=1}^r\lambda_k u_k</math> belongs to Шаблон:Mvar. As the definition of a convex set is the case Шаблон:Math, this property characterizes convex sets.

Such an affine combination is called a convex combination of Шаблон:Math.

Intersections and unions

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

1. The empty set and the whole space are convex.
2. The intersection of any collection of convex sets is convex.
3. The union of a sequence of convex sets is convex, if they form a non-decreasing chain for 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 point 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 Шаблон:Mvar and point Шаблон:Mvar outside it, there is a closed half-space Шаблон:Mvar that contains Шаблон:Mvar and not Шаблон:Mvar. The supporting hyperplane theorem is a special case of the Hahn–Banach theorem of functional analysis.

Convex sets and rectangles

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

Blaschke-Santaló diagrams

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 <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 Шаблон:Math point given by (r/R, D/2R). The image of this function is known a (r, D, R) Blachke-Santaló diagram.

Файл: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.

Other properties

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 sums

Convex hulls

Шаблон:Main Every subset Шаблон:Mvar of the vector space is contained within a smallest convex set (called the convex hull of Шаблон:Mvar), namely the intersection of all convex sets containing Шаблон:Mvar. The convex-hull operator Conv() has the characteristic properties of a hull operator:

• extensive: Шаблон:Math,
• non-decreasing: Шаблон:Math implies that Шаблон:Math, and
• idempotent: Шаблон: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 addition

Three squares are shown in the nonnegative quadrant of the Cartesian plane. The square Шаблон:Math is green. The square Шаблон:Math is brown, and it sits inside the turquoise square Шаблон:Math.

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, Шаблон:Math and Шаблон:Math, is defined to be the set Шаблон: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 Шаблон: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 Шаблон:Math containing only the zero vector Шаблон:Math has special importance: For every non-empty subset S of a vector space <math display=block>S+\{0\}=S;</math> in algebraic terminology, Шаблон:Math is the identity element of Minkowski addition (on the collection of non-empty sets).

Convex hulls of Minkowski sums

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

Let Шаблон: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.

Minkowski sums of convex sets

The Minkowski sum of two compact convex sets is compact. The sum of a compact convex set and a closed convex set is closed.

The following famous theorem, proved by Dieudonné in 1966, gives a sufficient condition for the difference of two closed convex subsets to be closed. 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 convexity

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) sets

Шаблон:Main Let Шаблон:Mvar be a set in a real or complex vector space. Шаблон:Mvar is star convex (star-shaped) if there exists an Шаблон:Math in Шаблон:Mvar such that the line segment from Шаблон:Math to any point Шаблон:Mvar in Шаблон:Mvar is contained in Шаблон:Mvar. Hence a non-empty convex set is always star-convex but a star-convex set is not always convex.

Orthogonal convexity

Шаблон:Main An example of generalized convexity is orthogonal convexity.

A set Шаблон: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 Шаблон:Mvar lies totally within Шаблон: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 geometry

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 topology

Convexity can be extended for a totally ordered set Шаблон:Mvar endowed with the order topology.

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

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

Convexity spaces

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

Given a set Шаблон:Mvar, a convexity over Шаблон:Mvar is a collection Шаблон:Math of subsets of Шаблон:Mvar satisfying the following axioms:

1. The empty set and Шаблон:Mvar are in Шаблон:Math
2. The intersection of any collection from Шаблон:Math is in Шаблон:Math.
3. The union of a chain (with respect to the inclusion relation) of elements of Шаблон:Math is in Шаблон:Math.

The elements of Шаблон:Math are called convex sets and the pair Шаблон: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 spaces

Convexity can be generalised as an abstract algebraic structure: a space is convex if it is possible to take convex combinations of points.

See also

• Absorbing set
• Algorithmic problems on convex sets
• Bounded set (topological vector space)
• Brouwer fixed-point theorem
• Complex convexity
• Convex hull
• Convex series
• Convex metric space
• Carathéodory's theorem (convex hull)
• Choquet theory
• Helly's theorem
• Holomorphically convex hull
• Integrally-convex set
• John ellipsoid
• Pseudoconvexity
• Radon's theorem
• Shapley–Folkman lemma
• Symmetric set

External links

• Шаблон:Springer
• Lectures on Convex Sets, notes by Niels Lauritzen, at Aarhus University, March 2010.