Konvexer Satz - Convex set

Illustration einer konvexen Menge, die wie ein deformierter Kreis aussieht. Das oben schwarz dargestellte Liniensegment, das die Punkte x und y verbindet, liegt vollständig innerhalb der grün dargestellten Menge. Da dies für alle möglichen Orte von zwei beliebigen Punkten innerhalb der obigen Menge gilt, ist die Menge konvex.
Illustration einer nicht-konvexen Menge. Illustriert durch das obige Liniensegment, wobei es von schwarz nach rot wechselt. Ein Beispiel dafür, warum diese obige Menge, grün dargestellt, nicht konvex ist.

In Geometrie , eine Teilmenge eines euklidischen Raum oder allgemein ein affiner Raum über den reellen Zahlen ist konvex , wenn zwei beliebige Punkte in der Untergruppe angegeben, enthält die Teilmenge der gesamten Liniensegment , das sie verbindet. Äquivalent ist eine konvexe Menge oder ein konvexer Bereich eine Teilmenge, die jede Linie in ein einzelnes Liniensegment (möglicherweise leer) schneidet . Zum Beispiel kann ein fester Würfel ist eine konvexe Menge, aber alles , das hohl ist oder eine Kerbe hat, beispielsweise eine sichelförmige Form, konvex nicht.

Der Rand einer konvexen Menge ist immer eine konvexe Kurve . Der Durchschnitt aller konvexen Mengen, die eine gegebene Teilmenge A des euklidischen Raums enthalten, wird als konvexe Hülle von A bezeichnet . Es ist die kleinste konvexe Menge, die A enthält .

Eine konvexe Funktion ist eine reellwertige Funktion, die auf einem Intervall definiert ist, mit der Eigenschaft, dass ihr Epigraph (die Menge der Punkte auf oder über dem Graphen der Funktion) eine konvexe Menge ist. Die konvexe Minimierung ist ein Teilgebiet der Optimierung , das das Problem der Minimierung konvexer Funktionen über konvexen Mengen untersucht. Der Zweig der Mathematik, der sich dem Studium der Eigenschaften konvexer Mengen und konvexer Funktionen widmet, wird als konvexe Analysis bezeichnet .

Der Begriff einer konvexen Menge kann wie unten beschrieben verallgemeinert werden.

Definitionen

Eine Funktion ist genau dann konvex, wenn ihr Epigraph , der Bereich (in Grün) über ihrem Graphen (in Blau), eine konvexe Menge ist.

Sei S ein Vektorraum oder ein affiner Raum über den reellen Zahlen oder allgemeiner über einem geordneten Körper . Dazu gehören euklidische Räume, die affine Räume sind. Eine Teilmenge C von S ist konvex, wenn für alle x und y in C das Liniensegment , das x und y verbindet, in C enthalten ist . Das bedeutet, dass die affine Kombination (1 − t ) x + ty zu C gehört , für alle x und y in C , und t im Intervall [0, 1] . Dies impliziert, dass Konvexität (die Eigenschaft, konvex zu sein) unter affinen Transformationen invariant ist . Dies bedeutet auch , dass eine konvexe Menge in einem realen oder komplexen topologischen Vektorraum ist wegzusammenhängend damit verbunden .

Eine Menge C ist streng konvex, wenn jeder Punkt auf dem Liniensegment, dasxundy verbindet, außer den Endpunkten innerhalb desInnerenvonC liegt.

Eine Menge C ist absolut konvex, wenn sie konvex und ausgeglichen ist .

Die konvexen Teilmengen von R (die Menge der reellen Zahlen) sind die Intervalle und die Punkte von R . Einige Beispiele für konvexe Teilmengen der euklidischen Ebene sind feste regelmäßige Vielecke , feste Dreiecke und Schnittpunkte von festen Dreiecken. Einige Beispiele für konvexe Teilmengen eines euklidischen 3-dimensionalen Raums sind die archimedischen Körper und die platonischen Körper . Die Kepler-Poinsot-Polyeder sind Beispiele für nichtkonvexe Mengen.

Nicht-konvexe Menge

Eine nichtkonvexe Menge heißt nichtkonvexe Menge . Ein Polygon , das kein konvexes Polygon ist, wird manchmal als konkaves Polygon bezeichnet , und einige Quellen verwenden im Allgemeinen den Begriff konkave Menge , um eine nicht konvexe Menge zu bezeichnen, aber die meisten Behörden verbieten diese Verwendung.

Das Komplement einer konvexen Menge, wie der Epigraph einer konkaven Funktion , wird manchmal als umgekehrte konvexe Menge bezeichnet , insbesondere im Zusammenhang mit der mathematischen Optimierung .

Eigenschaften

Gegeben r Punkte u 1 , ..., u r in einer konvexen Menge S und r nicht negative Zahlen λ 1 , ..., λ r , so dass λ 1 + ... + λ r = 1 , die Affinkombination

gehört zur S . Da die Definition einer konvexen Menge der Fall r = 2 ist , charakterisiert diese Eigenschaft konvexe Mengen.

Eine solche affine Kombination wird als konvexe Kombination von u 1 , ..., u r bezeichnet .

Kreuzungen und Verbindungen

Die Sammlung konvexer Teilmengen eines Vektorraums, eines affinen Raums oder eines euklidischen Raums hat die folgenden Eigenschaften:

  1. Die leere Menge und der ganze Raum sind konvex.
  2. Der Durchschnitt jeder Sammlung konvexer Mengen ist konvex.
  3. Die Vereinigung einer Folge konvexer Mengen ist konvex, wenn sie eine nicht abnehmende Inklusionskette bilden. Für diese Eigenschaft ist die Beschränkung auf Ketten wichtig, da die Vereinigung zweier konvexer Mengen nicht konvex sein muss.

Geschlossene konvexe Mengen

Geschlossene konvexe Mengen sind konvexe Mengen, die alle ihre Grenzpunkte enthalten . Sie können als Schnittpunkte geschlossener Halbräume (Mengen von Raumpunkten, die auf und neben einer Hyperebene liegen ) charakterisiert werden .

Aus dem eben Gesagten ist klar, dass solche Schnitte konvex sind und auch abgeschlossene Mengen sein werden. Um die Umkehrung zu beweisen, dh jede abgeschlossene konvexe Menge kann als solcher Schnitt dargestellt werden, benötigt man den unterstützenden Hyperebenensatz in der Form, dass es für eine gegebene abgeschlossene konvexe Menge C und einen Punkt P außerhalb davon einen abgeschlossenen Halbraum H gibt , der enthält C und nicht P . Der unterstützende Hyperebenensatz ist ein Spezialfall des Hahn-Banach-Satzes der Funktionalanalysis .

Konvexe Mengen und Rechtecke

Sei C ein konvexer Körper in der Ebene (eine konvexe Menge, deren Inneres nicht leer ist). Wir können ein Rechteck r in C einschreiben, so dass eine homothetische Kopie R von r um C umschrieben ist . Das positive Homothetitätsverhältnis beträgt höchstens 2 und:


Blaschke-Santaló-Diagramme

Die Menge aller ebenen konvexen Körper kann durch den Durchmesser D des konvexen Körpers , seinen Innenradius r (der größte im konvexen Körper enthaltene Kreis) und seinen Umkreis R (der kleinste Kreis, der den konvexen Körper enthält) parametrisiert werden . Tatsächlich kann diese Menge durch die Menge der Ungleichungen beschrieben werden, die gegeben ist durch

und kann als Bild der Funktion g visualisiert werden , die einen konvexen Körper auf den durch ( r / R , D /2 R ) gegebenen R 2 -Punkt abbildet . Das Bild dieser Funktion ist als ( r , D , R ) Blachke-Santaló-Diagramm bekannt.
Blaschke-Santaló ( r , D , R ) Diagramm für planare konvexe Körper. bezeichnet das Liniensegment, das gleichseitige Dreieck, das Reuleaux-Dreieck und den Einheitskreis.

Alternativ kann die Menge auch durch ihre Breite (der kleinste Abstand zwischen zwei verschiedenen parallelen Stützhyperebenen), Umfang und Fläche parametrisiert werden.

Andere Eigenschaften

Sei X ein topologischer Vektorraum und konvex.

  • und sind beide konvex (dh der Abschluss und das Innere konvexer Mengen sind konvex).
  • Wenn und dann (wo ).
  • Wenn dann:
    • , und
    • , wo ist das
algebraische Innere von C .

Konvexe Hüllen und Minkowski-Summen

Konvexe Hüllen

Jede Teilmenge A des Vektorraums ist in einer kleinsten konvexen Menge (genannt die konvexe Hülle von A ) enthalten, nämlich dem Durchschnitt aller konvexen Mengen, die A enthalten . Der Konvexhüllenoperator Conv() hat die charakteristischen Eigenschaften eines Hüllenoperators :

  • umfangreich : S  ⊆ Conv( S ) ,
  • nicht abnehmend : S  ⊆  T impliziert, dass Conv( S ) ⊆ Conv( T ) , und
  • idempotent : Conv(Conv( S )) = Conv( S ) .

Die konvexe Hüllen-Operation wird benötigt, damit die Menge der konvexen Mengen ein Gitter bildet , in dem die " Verknüpfung "-Operation die konvexe Hülle der Vereinigung zweier konvexer Mengen ist

Der Schnittpunkt einer beliebigen Sammlung konvexer Mengen ist selbst konvex, sodass die konvexen Teilmengen eines (reellen oder komplexen) Vektorraums ein vollständiges Gitter bilden .

Minkowski-Zusatz

Im nichtnegativen Quadranten der kartesischen Ebene sind drei Quadrate dargestellt.  Das Quadrat Q1 = [0, 1] × [0, 1] ist grün.  Das Quadrat Q2 = [1, 2] × [1, 2] ist braun und liegt innerhalb des türkisfarbenen Quadrats Q1+Q2=[1,3]×[1,3].
Minkowski-Ergänzung von Sätzen. Die Summe der Quadrate Q 1 =[0,1] 2 und Q 2 =[1,2] 2 ist das Quadrat Q 1 +Q 2 =[1,3] 2 .

In einem reellen Vektorraum ist die Minkowski-Summe zweier (nicht leerer) Mengen S 1 und S 2 definiert als die Menge S 1  +  S 2 , die durch die elementweise Addition von Vektoren aus den Summandenmengen gebildet wird

Allgemeiner ausgedrückt ist die Minkowski-Summe einer endlichen Familie von (nicht leeren) Mengen S n die Menge, die durch elementweise Addition von Vektoren gebildet wird

Für die Minkowski-Addition hat die Nullmenge  {0}, die nur den Nullvektor  0 enthält, besondere Bedeutung : Für jede nichtleere Teilmenge S eines Vektorraums

in der algebraischen Terminologie ist {0} das Identitätselement der Minkowski-Addition (auf die Sammlung nichtleerer Mengen).

Konvexe Hüllen von Minkowski-Summen

Die Minkowski-Addition verhält sich gut in Bezug auf die Operation des Nehmens konvexer Hüllen, wie der folgende Satz zeigt:

Seien S 1 , S 2 Teilmengen eines reellen Vektorraums, die konvexe Hülle ihrer Minkowski-Summe ist die Minkowski-Summe ihrer konvexen Hüllen

Dieses Ergebnis gilt allgemeiner für jede endliche Sammlung von nicht leeren Mengen:

In mathematischer Terminologie, die Operationen der Minkowski Summation und die Bildung konvexe Hüllen sind Pendel Operationen.

Minkowski-Summen konvexer Mengen

Die Minkowski-Summe zweier kompakter konvexer Mengen ist kompakt. Die Summe einer kompakten konvexen Menge und einer abgeschlossenen konvexen Menge ist abgeschlossen.

Der folgende berühmte Satz, der 1966 von Dieudonné bewiesen wurde, liefert eine hinreichende Bedingung dafür, dass die Differenz zweier abgeschlossener konvexer Teilmengen abgeschlossen ist. Es verwendet das Konzept eines Rezessionskegels einer nicht leeren konvexen Teilmenge S , definiert als:

wobei diese Menge ein konvexer Kegel ist, der enthält und erfüllt . Beachten Sie, dass wenn
S abgeschlossen und konvex ist, dann ist abgeschlossen und für alle gilt

Satz (Dieudonné). Seien A und B nichtleere, abgeschlossene und konvexe Teilmengen eines lokal konvexen topologischen Vektorraums , der also ein linearer Teilraum ist. Wenn

A oder B ist lokal kompakt dann A  -  B geschlossen ist.

Verallgemeinerungen und Erweiterungen für Konvexität

Der Begriff der Konvexität im euklidischen Raum kann verallgemeinert werden, indem die Definition in einigen oder anderen Aspekten modifiziert wird. Der gebräuchliche Name "generalisierte Konvexität" wird verwendet, weil die resultierenden Objekte bestimmte Eigenschaften von konvexen Mengen beibehalten.

Sternkonvexe (sternförmige) Sätze

Sei C eine Menge in einem reellen oder komplexen Vektorraum. C ist Stern konvex (sternförmig) , wenn es eine gibt x 0 in C , so dass das Liniensegment von x 0 zu einem beliebigen Punkt y in C in enthalten ist C . Daher ist eine nichtleere konvexe Menge immer sternkonvex, aber eine sternkonvexe Menge ist nicht immer konvex.

Orthogonale Konvexität

Ein Beispiel für verallgemeinerte Konvexität ist die orthogonale Konvexität .

Ein Satz S im euklidischen Raum heißt orthogonal konvex oder ortho-konvex , wenn ein Segment parallel zu einem der beiden Punkte des Verbindens Koordinatenachsen S liegt vollständig innerhalb S . Es ist leicht zu beweisen, dass ein Schnittpunkt einer Sammlung orthokonvexer Mengen orthokonvex ist. Einige andere Eigenschaften konvexer Mengen sind ebenfalls gültig.

Nichteuklidische Geometrie

Die Definition einer konvexen Menge und einer konvexen Hülle erstreckt sich natürlich auf Geometrien, die nicht euklidisch sind, indem eine geodätisch konvexe Menge definiert wird , die die Geodäten enthält, die zwei beliebige Punkte in der Menge verbinden.

Bestelltopologie

Die Konvexität kann für eine vollständig geordnete Menge X erweitert werden, die mit der Ordnungstopologie ausgestattet ist .

Sei YX . Der Unterraum Y ist eine konvexe Menge , wenn für jedes Paar von Punkten a , b in Y , so daß einb , das Intervall [ a , b ] = { xX | axb } ist auch enthalten in Y . Das heißt, Y ist konvex , wenn und nur wenn für alle a , b in Y , ab bedeutet , [ ein , b ] ⊆ Y .

Eine konvexe Menge ist im Allgemeinen nicht zusammenhängend: Ein Gegenbeispiel ist der Unterraum {1,2,3} in Z , der sowohl konvex als auch nicht zusammenhängend ist.

Konvexitätsräume

Der Begriff der Konvexität kann auf andere Objekte verallgemeinert werden, wenn bestimmte Eigenschaften der Konvexität als Axiome ausgewählt werden .

Gegeben eine Menge X ist eine Konvexität über X eine Sammlung 𝒞 von Teilmengen von X, die die folgenden Axiome erfüllen:

  1. Die leere Menge und X sind in 𝒞
  2. Der Schnittpunkt einer beliebigen Sammlung aus 𝒞 liegt in 𝒞 .
  3. Die Vereinigung einer Kette (in Bezug auf die Einschlussbeziehung ) von Elementen der c ist in c .

Die Elemente von 𝒞 heißen konvexe Mengen und das Paar ( X , 𝒞 ) heißt Konvexitätsraum . Für die gewöhnliche Konvexität gelten die ersten beiden Axiome und das dritte ist trivial.

Eine alternative Definition der abstrakten Konvexität, die besser für die diskrete Geometrie geeignet

ist , finden Sie in den konvexen Geometrien, die mit Antimatroiden verbunden sind .

Siehe auch

Verweise

Externe Links