Convex set: Difference between revisions

Revision as of 11:36, 5 February 2025

Latest revision as of 17:52, 10 May 2025

(3 intermediate revisions by one other user not shown)

Line 3:

[[File:Convex polygon illustration2.svg|right|thumb|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. Equivalently, a '''convex set''' or a '''convex region''' is a set that intersects every [[line (geometry)|line]] in a [[line segment]], single point, or the [[empty set]].<ref>{{cite book|last1=Morris|first1=Carla C.|last2=Stark|first2=Robert M.|title=Finite Mathematics: Models and Applications|date=24 August 2015|publisher=John Wiley & Sons|isbn=9781119015383|page=121|url=https://books.google.com/books?id=ZgJyCgAAQBAJ&q=convex+region&pg=PA121|access-date=5 April 2017|language=en}}</ref><ref>{{cite journal|last1=Kjeldsen|first1=Tinne Hoff|title=History of Convexity and Mathematical Programming|journal=Proceedings of the International Congress of Mathematicians|issue=ICM 2010|pages=3233–3257|doi=10.1142/9789814324359_0187|url=http://www.mathunion.org/ICM/ICM2010.4/Main/icm2010.4.3233.3257.pdf|access-date=5 April 2017|url-status=dead|archive-url=https://web.archive.org/web/20170811100026/http://www.mathunion.org/ICM/ICM2010.4/Main/icm2010.4.3233.3257.pdf|archive-date=2017-08-11}}</ref>

For example, a solid [[cube (geometry)|cube]] is a convex set, but anything that is hollow or has an indent, for example, a [[crescent]] shape, is not convex.

Line 10:

A [[convex function]] is a [[real-valued function]] defined on an [[interval (mathematics)|interval]] with the property that its [[epigraph (mathematics)|epigraph]] (the set of points on or above the [[graph of a function|graph]] of the function) is a convex set. [[Convex minimization]] is a subfield of [[mathematical optimization|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 space]]s, the [[affine space]]s over the [[real number]]s, and certain [[non-Euclidean geometry|non-Euclidean geometries]]. The notion of a convex set in Euclidean spaces can be generalized in several ways by modifying its definition, for instance by restricting the line segments that such a set is required to contain.

== Definitions ==

Line 31:

== Properties ==

Given {{mvar|r}} points {{math|''u''₁, ..., ''u_r''}} in a convex set {{mvar|S}}, and {{mvar|r}}

[[negative number|nonnegative number]]s {{math|''λ''₁, ..., ''λ_r''}} such that {{math|''λ''₁ + ... + ''λ_r'' {{=}} 1}}, the [[affine combination]]

Line 37 ⟶ 36:

belongs to {{mvar|S}}. As the definition of a convex set is the case {{math|1=''r'' = 2}}, this property characterizes convex sets.

Such an affine combination is called a [[convex combination]] of {{math|''u''₁, ..., ''u_r''}}. The '''convex hull''' of a subset {{mvar|S}} of a real vector space is defined as the intersection of all convex sets that contain {{mvar|S}}. More concretely, the convex hull is the set of all convex combinations of points in {{mvar|S}}. In particular, this is a convex set.

A ''(bounded) [[convex polytope]]'' is the convex hull of a finite subset of some Euclidean space {{math|'''R'''^''n''}}.

=== Intersections and unions ===

Line 44 ⟶ 45:

#The [[empty set]] and the whole space are convex.

#The intersection of any collection of convex sets is convex.

#The ''[[union (sets)|union]]'' of a sequencecollection of convex sets is convex, if theythose sets form a [[Total order#Chains|non-decreasing chain]] for(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 ===

Line 52 ⟶ 53:

=== Face of a convex set ===

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> islies alsostrictly abetween convextwo set,points <math>x</math> and for<math>y</math> anyin points<math>C</math>, both <math>x,</math> and <math>y</math> must be in <math>F</math>.{{sfn | Rockafellar| 1997 | p=162}} Equivalently, for any <math>x,y\in C</math> and any real number <math>0<t<1</math> withsuch that <math>(1-t)x+ty</math> is in <math>F</math>, <math>x</math> and <math>y</math> must both be in <math>F</math>.{{sfn |According Rockafellar| 1997 | p=162}}to Forthis exampledefinition, <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 space|compact]] (or equivalently, closed and [[bounded set|bounded]]). Then <math>C</math> is the [[convex hull]] of its extreme points.{{sfn | Rockafellar| 1997 | p=166}} This holds moreMore generally, for aeach compact convex set in anya [[locally convex topological vector space]] is the closed convex hull of its extreme points (the [[Krein–Milman theorem]]).

For example:

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 extremal points are the three vertices.) For another example: the only nontrivial faces of the [[closed unit disk]] <math>\{ (x,y) \in \R^2: x^2+y^2 \leq 1 \}</math> are its extremal points, namely the points on the [[unit circle]] <math>S^1 = \{ (x,y) \in \R^2: x^2+y^2=1 \}</math>.

* 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.)

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 extremal points are the three vertices.) For another example: theThe only nontrivial faces of the [[closed unit disk]] <math>\{ (x,y) \in \R^2: x^2+y^2 \leq 1 \}</math> are its extremalextreme 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 rectangles ===

Line 85 ⟶ 88:

=== Convex hulls ===

{{Main|convex hull}}

Every subset {{mvar|A}} of the vector space is contained within a smallest convex set (called the [[''convex hull]]'' of {{mvar|A}}), namely the intersection of all convex sets containing {{mvar|A}}. The convex-hull operator Conv() has the characteristic properties of a [[closure operator|hull operator]]:

* ''extensive'': {{math|''S''&nbsp;⊆&nbsp;Conv(''S'')}},

* ''[[Monotone function#Monotonicity in order theory|non-decreasing]]'': {{math|''S''&nbsp;⊆&nbsp;''T''}} implies that {{math|Conv(''S'')&nbsp;⊆&nbsp;Conv(''T'')}}, and

Line 155 ⟶ 158:

Given a set {{mvar|X}}, a '''convexity''' over {{mvar|X}} is a collection {{math|''𝒞''}} of subsets of {{mvar|X}} satisfying the following axioms:<ref name="Soltan"/><ref name="Singer"/><ref name="vanDeVel" >{{cite book|last=van De Vel|first=Marcel L. J.|title=Theory of convex structures|series=North-Holland Mathematical Library|publisher=North-Holland Publishing Co.|___location=Amsterdam|year= 1993|pages=xvi+540|isbn=0-444-81505-8|mr=1234493}}</ref>

#The empty set and {{mvar|X}} are in {{math|''𝒞''}}.

#The intersection of any collection from {{math|''𝒞''}} is in {{math|''𝒞''}}.

#The union of a [[Total order|chain]] (with respect to the [[inclusion relation]]) of elements of {{math|''𝒞''}} is in {{math|''𝒞''}}.

Line 176 ⟶ 179:

* [[Complex convexity]]

* [[Convex cone]]

* [[Convex hull]]

* [[Convex series]]

* [[Convex metric space]]

Line 194 ⟶ 196:

{{reflist|30em}}

==SourcesBibliography==

* {{cite book | last=Rockafellar | first=R. T. | author-link=R. Tyrrell Rockafellar | title=Convex Analysis |publisher=Princeton University Press | ___location=Princeton, NJ | orig-year=1970 | year=1997 | isbn=1-4008-7317-7 |url=https://books.google.com/books?id=1TiOka9bx3sC }}