Konvexer Kegel - Convex cone

Ein konvexer Kegel (hellblau). Darin besteht der hellrote Konvexkegel aus allen Punkten αx + βy mit α, β > 0 , für das dargestellte x und y . Die Kurven oben rechts symbolisieren, dass die Regionen unendlich groß sind.

In der linearen Algebra , ein konvexer Kegel ist eine Teilmenge von einem Vektorraum über ein geordneten Feld das ist geschlossen unter linearen Kombinationen mit positiven Koeffizienten.

Definition

Eine Teilmenge C eines Vektorraums V über einem geordneten Körper F ist ein Kegel (oder manchmal auch ein linearer Kegel genannt ), wenn für jedes x in C und einen positiven Skalar α in F das Produkt αx in C ist . Beachten Sie, dass einige Autoren einen Kegel mit dem Skalar α definieren , der sich über alle nicht-negativen Skalare erstreckt (anstatt alle positiven Skalare, die 0 nicht einschließen).

Ein Kegel C ist ein konvexer Kegel , wenn & agr; x + & bgr; y gehört C , für jeden positiven Skalar & alpha , β , und jeder x , y in C . Ein Kegel C ist genau dann konvex, wenn C + C ⊆ C .

Dieses Konzept ist für jeden Vektorraum sinnvoll, der das Konzept von "positiven" Skalaren zulässt, z. B. Räume über den rationalen , algebraischen oder (häufiger) den reellen Zahlen . Beachten Sie auch, dass die Skalare in der Definition positiv sind, was bedeutet, dass der Ursprung nicht zu C gehören muss. Einige Autoren verwenden eine Definition, die sicherstellt, dass der Ursprung zu C gehört . Wegen der Skalierungsparameter α und β sind Kegel unendlich groß und nicht beschränkt.

Wenn C ein konvexer Kegel ist, dann gilt für jeden positiven Skalar α und jedes x in C der Vektor. Daraus folgt, dass ein konvexer Kegel C ein Spezialfall eines linearen Kegels ist . ${\displaystyle \alpha x={\tfrac {\alpha}{2}}x+{\tfrac {\alpha}{2}}x\in C.}$

Aus der obigen Eigenschaft folgt, dass ein konvexer Kegel auch als linearer Kegel definiert werden kann, der unter konvexen Kombinationen oder nur unter Additionen abgeschlossen ist . Kurz gesagt ist eine Menge C genau dann ein konvexer Kegel, wenn αC = C und C + C = C für jeden positiven Skalar α ist .

Beispiele

Konvexer Kegel, der keine konische Kombination endlich vieler Generatoren ist.

Konvexer Kegel, der durch die konische Kombination der drei schwarzen Vektoren erzeugt wird.

Ein Kegel (die Vereinigung zweier Strahlen), der kein konvexer Kegel ist.

Besondere Beispiele

Affine konvexe Kegel

Ein affiner konvexer Kegel ist die Menge, die sich aus der Anwendung einer affinen Transformation auf einen konvexen Kegel ergibt. Ein gängiges Beispiel ist die Verschiebung eines konvexen Kegels um einen Punkt p : p + C . Technisch können solche Transformationen Nicht-Kegel erzeugen. Wenn beispielsweise p = 0 ist , ist p + C kein linearer Kegel. Es wird jedoch immer noch als affiner konvexer Kegel bezeichnet.

Halbräume

Eine (lineare) Hyperebene ist eine Menge in der Form, wobei f ein lineares Funktional auf dem Vektorraum V ist. Ein abgeschlossener Halbraum ist eine Menge in der Form oder und ebenso verwendet ein offener Halbraum strikte Ungleichung. ${\displaystyle \{x\in V\mid f(x)=c\}}$${\displaystyle \{x\in V\mid f(x)\leq c\}}$${\displaystyle \{x\in V\mid f(x)\geq c\},}$

Halbräume (offen oder geschlossen) sind affine konvexe Kegel. Außerdem (in endlichen Dimensionen) muss jeder konvexe Kegel C , der nicht der ganze Raum V ist, in einem geschlossenen Halbraum H von V enthalten sein ; dies ist ein Sonderfall von Farkas' Lemma .

Polyedrische und endlich erzeugte Kegel

Polyedrische Kegel sind spezielle Kegelarten, die auf verschiedene Weise definiert werden können:

• Ein Kegel C ist polyedrisch, wenn er die Kegelkombination endlich vieler Vektoren ist (diese Eigenschaft wird auch endlich erzeugt genannt ). Dh es gibt eine Menge von Vektoren, so dass .${\displaystyle \{v_{1},\ldots,v_{k}\}}$${\displaystyle C=\{a_{1}v_{1}+\cdots +a_{k}v_{k}\mid a_{i}\in\mathbb{R}_{\geq 0},v_{i }\in\mathbb{R}^{n}\}}$
• Ein Kegel ist polyedrisch, wenn er der Schnittpunkt einer endlichen Anzahl von Halbräumen ist, deren Rand 0 hat (dies wurde 1935 von Weyl bewiesen).
• Ein Kegel C ist polyedrisch, wenn es eine Matrix gibt, so dass .${\displaystyle A}$${\displaystyle C=\{x\in\mathbb{R}^{n}\mid Ax\geq 0\}}$
• Ein Kegel ist polyedrisch, wenn er die Lösungsmenge eines Systems homogener linearer Ungleichungen ist. Algebraisch wird jede Ungleichung durch eine Zeile der Matrix A definiert . Geometrisch definiert jede Ungleichung einen Halbraum, der durch den Ursprung geht.

Jeder endlich erzeugte Kegel ist ein polyedrischer Kegel, und jeder polyedrische Kegel ist ein endlich erzeugter Kegel. Jeder polyedrische Kegel hat eine eindeutige Darstellung als konische Hülle seiner Extremalgeneratoren und eine eindeutige Darstellung von Schnittpunkten von Halbräumen, da jede den Halbräumen zugeordnete lineare Form auch eine Stützhyperebene einer Facette definiert.

Polyederkegel spielen eine zentrale Rolle in der Darstellungstheorie von Polyedern . Zum Beispiel besagt der Zerlegungssatz für Polyeder, dass jedes Polyeder als Minkowski-Summe eines konvexen Polytops und eines polyedrischen Kegels geschrieben werden kann. Polyederkegel spielen auch eine wichtige Rolle beim Beweis des verwandten Finite-Basis-Theorems für Polytope, der zeigt, dass jedes Polytop ein Polyeder und jedes beschränkte Polyeder ein Polytop ist.

Die beiden Darstellungen eines polyedrischen Kegels - durch Ungleichungen und durch Vektoren - können sehr unterschiedliche Größen haben. Betrachten Sie zum Beispiel den Kegel aller nicht-negativen n- mal- n- Matrizen mit gleichen Zeilen- und Spaltensummen. Die Ungleichungsdarstellung erfordert n ² Ungleichungen und 2( n − 1) Gleichungen, aber die Vektordarstellung erfordert n ! Vektoren (siehe das Birkhoff-von-Neumann-Theorem ). Das Gegenteil kann auch passieren - die Anzahl der Vektoren kann polynomiell sein, während die Anzahl der Ungleichungen exponentiell ist.

Die beiden Darstellungen zusammen bieten einen effizienten Weg, um zu entscheiden, ob ein gegebener Vektor im Kegel liegt: Um zu zeigen, dass er sich im Kegel befindet, reicht es aus, wenn er eine Kegelkombination der definierenden Vektoren darstellt; um zu zeigen, dass sie nicht im Kegel liegt, reicht es aus, eine einzelne definierende Ungleichung darzustellen, die sie verletzt. Diese Tatsache ist als Lemma von Farkas bekannt .

Ein subtiler Punkt bei der Darstellung durch Vektoren ist, dass die Anzahl der Vektoren in der Dimension exponentiell sein kann, sodass der Beweis, dass ein Vektor im Kegel liegt, exponentiell lang sein kann. Glücklicherweise garantiert der Satz von Carathéodory, dass jeder Vektor im Kegel höchstens durch d definierende Vektoren dargestellt werden kann, wobei d die Dimension des Raums ist.

Stumpfe, spitze, flache, markante und richtige Zapfen

Ist C nach obiger Definition ein konvexer Kegel, so ist auch C ∪ { 0 } ein konvexer Kegel. Ein konvexer Kegel heißt zeigt, wenn0inC ist, undstumpf, wenn0nicht inC ist. Stumpfe Kegel können aus der Definition des konvexen Kegels ausgeschlossen werden, indem in der Bedingung von α, β "positiv" durch "nicht negativ" ersetzt wird.

Ein Kegel heißt flach, wenn er einen von Null verschiedenen Vektor x und sein Gegenstück − x enthält , was bedeutet , dass C einen linearen Unterraum der Dimension mindestens 1 enthält und ansonsten hervorstechend ist . Ein stumpfer konvexer Kegel ist notwendigerweise hervorstechend, aber das Umgekehrte gilt nicht unbedingt. Ein konvexer Kegel C ist genau dann hervorstechend, wenn C ∩ − C ⊆ { 0 }. Ein Kegel C heißt erzeugend, wenn C  −  C gleich dem ganzen Vektorraum ist.

Einige Autoren verlangen, dass ausgeprägte Zapfen zugespitzt werden. Der Begriff "spitz" wird auch häufig verwendet, um sich auf einen geschlossenen Kegel zu beziehen, der keine vollständige Linie enthält (dh keinen nichttrivialen Unterraum des Umgebungsvektorraums V oder einen sogenannten ausgeprägten Kegel). Der Begriff des eigentlichen ( konvexen ) Kegels wird je nach Kontext und Autor unterschiedlich definiert. Es bedeutet oft einen Kegel, der andere Eigenschaften wie konvex, geschlossen, spitz, hervorstehend und volldimensional erfüllt. Aufgrund dieser unterschiedlichen Definitionen sollte der Kontext oder die Quelle für die Definition dieser Begriffe herangezogen werden.

Rationale Kegel

Eine Art von Kegel, der für reine Mathematiker von besonderem Interesse ist, ist die teilweise geordnete Menge rationaler Kegel. "Rationale Kegel sind wichtige Objekte in der torischen algebraischen Geometrie, der kombinatorischen kommutativen Algebra, der geometrischen Kombinatorik und der Integer-Programmierung." Dieses Objekt entsteht, wenn wir Zapfen zusammen mit dem Gitter untersuchen . Ein Kegel heißt rational (hier gehen wir von "spitz" aus, wie oben definiert), wenn seine Generatoren alle ganzzahlige Koordinaten haben, dh wenn es ein rationaler Kegel ist, dann . ${\displaystyle \mathbb{R}^{d}}$ ${\displaystyle \mathbb{Z} ^{d}}$${\displaystyle C}$${\displaystyle C=\{a_{1}v_{1}+\cdots +a_{k}v_{k}\mid a_{i}\in\mathbb{R}_{+},v_{i}\ in \mathbb{Z}^{d}\}}$

Doppelkegel

Sei C ⊂ V eine Menge, nicht notwendigerweise eine konvexe Menge, in einem reellen Vektorraum V mit einem inneren Produkt . Der (stetige oder topologische) Doppelkegel zu C ist die Menge

${\displaystyle C^{*}=\{v\in V\mid \forall w\in C,\langle w,v\rangle\geq 0\},}$

das ist immer ein konvexer Kegel. Hier ist die Dualitätspaarung zwischen C und V , dh . ${\displaystyle\langle w,v\rangle}$${\displaystyle \langle w,v\rangle =v(w)}$

Allgemeiner ausgedrückt ist der (algebraische) Dualkegel zu C ⊂ V in einem linearen Raum V eine Teilmenge des Dualraums V* definiert durch:

${\displaystyle C^{*}:=\left\{v\in V^{*}\mid \forall w\in C,v(w)\geq 0\right\}.}$

Mit anderen Worten, wenn V* der algebraische Dualraum von V ist , ist dies die Menge der linearen Funktionale, die auf dem Primärkegel C nichtnegativ sind . Wenn wir V* als stetigen Dualraum nehmen, dann ist es die Menge der stetigen linearen Funktionale, die auf C nichtnegativ sind . Dieser Begriff erfordert nicht die Angabe eines inneren Produkts auf V .

In endlichen Dimensionen sind die beiden Begriffe des dualen Kegels im Wesentlichen gleich, da jedes endlichdimensionale lineare Funktional stetig ist und jedes stetige lineare Funktional in einem inneren Produktraum einen linearen Isomorphismus (nicht singuläre lineare Abbildung) von V* nach V induziert , und dies Isomorphismus wird den durch die zweite Definition gegebenen dualen Kegel in V* auf den durch die erste Definition gegebenen übernehmen; siehe den Riesz-Darstellungssatz .

Wenn C gleich seiner doppelten Konus, dann C wird als Selbst dual . Ein Kegel kann ohne Bezug auf ein gegebenes inneres Produkt als selbstdual bezeichnet werden, wenn es ein inneres Produkt gibt, bezüglich dessen er nach der ersten Definition seinem Dual gleich ist.

Konstruktionen

• Gegeben eine abgeschlossene konvexe Teilmenge K des Hilbertraums V ist der nach außen gerichtete Normalkegel auf die Menge K im Punkt x in K gegeben durch

  ${\displaystyle N_{K}(x)=\left\{p\in V\colon \forall x^{*}\in K,\left\langle p,x^{*}-x\right\rangle\ leq 0\rechts\}.}$

• Gegeben eine abgeschlossene, konvexe Teilmenge K von V , ist der Tangentenkegel (oder kontingenter Kegel ) an die Menge K im Punkt x gegeben durch

  ${\displaystyle T_{K}(x)={\overline {\bigcup_{h>0}{\frac {Kx}{h}}}}.}$

• Bei einer geschlossenen, konvexen Teilmenge K des Hilbertraums V kann der Tangentenkegel an die Menge K im Punkt x in K als Polarkegel zu Außennormalkegel definiert werden : ${\displaystyle N_{K}(x)}$

  ${\displaystyle T_{K}(x)=N_{K}^{*}(x)\ {\overset {\underset {\mathrm {def} }{}}{=}}\ \{y\in V \mid\forall\xi\in N_{K}(x):\langle y,\xi\rangle\leqslant 0\}}$

Sowohl der normale als auch der tangentiale Kegel haben die Eigenschaft, geschlossen und konvex zu sein.

Sie sind wichtige Konzepte in den Bereichen konvexe Optimierung , Variationsungleichungen und projizierte dynamische Systeme .

Eigenschaften

Wenn C ein nicht leerer konvexer Kegel in X ist , dann ist die lineare Spanne von C gleich C - C und der größte in C enthaltene Vektorunterraum von X ist gleich C ∩ (− C ).

Teilordnung definiert durch einen konvexen Kegel

Ein spitzer und hervorstechender konvexer Kegel C induziert eine partielle Ordnung "≤" auf V , definiert so, dass genau dann, wenn (Wenn der Kegel flach ist, dieselbe Definition nur eine Vorordnung ergibt .) Summen und positive skalare Vielfache gültiger Ungleichungen bezüglich zu dieser Ordnung bleiben gültige Ungleichungen. Ein Vektorraum mit einer solchen Ordnung wird als geordneter Vektorraum bezeichnet . Beispiele sind die Produktordnung auf reellwertigen Vektoren und die Loewner-Ordnung auf positiven semidefiniten Matrizen. Eine solche Ordnung findet man häufig in der positiv semidefiniten Programmierung.${\displaystyle x\leq y}$${\displaystyle yx\in C.}$${\displaystyle \mathbb{R}^{n},}$

Siehe auch

• Kegel (Begriffsklärung)
  • Kegel (Geometrie)
  • Kegel (Topologie)
• Farkas' Lemma
• Bipolares Theorem
• Lineare Kombination
• Geordneter Vektorraum

Anmerkungen

Verweise

• Bourbaki, Nicolas (1987). Topologische Vektorräume . Elemente der Mathematik. Berlin, New York: Springer-Verlag . ISBN 978-3-540-13627-9.
• Narici, Lawrence ; Beckenstein, Edward (2011). Topologische Vektorräume . Reine und angewandte Mathematik (Zweite Aufl.). Boca Raton, FL: CRC-Presse. ISBN 978-1584888666. OCLC  144216834 .
• Rockafellar, RT (1997) [1970]. Konvexe Analyse . Princeton, NJ: Princeton University Press. ISBN 1-4008-7317-7.
• Schäfer, Helmut H. ; Wolff, Manfred P. (1999). Topologische Vektorräume . GTM . 8 (Zweite Aufl.). New York, NY: Springer New York Impressum Springer. ISBN 978-1-4612-7155-0. OCLC  840278135 .
• Trèves, François (2006) [1967]. Topologische Vektorräume, Verteilungen und Kernel . Mineola, NY: Dover-Veröffentlichungen. ISBN 978-0-486-45352-1. OCLC  853623322 .
• Zălinescu, C. (2002). Konvexe Analyse in allgemeinen Vektorräumen . River Edge, NJ: World Scientific. ISBN 981-238-067-1. MR  1.921.556 .