Kegel (Lineare Algebra)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der linearen Algebra ist ein (linearer) Kegel eine Teilmenge eines Vektorraums, die abgeschlossen bzgl. Multiplikation mit positiven Skalaren ist.

Definition[Bearbeiten]

Sei K ein geordneter Körper, beispielsweise die reellen oder auch die rationalen Zahlen. Eine Teilmenge C eines K-Vektorraums V heiße (linearer) Kegel, wenn für jedes Element x \in C und jeden nicht-negativen Skalar \lambda \in K;\lambda \ge 0 auch \lambda x \in C ist.[1]

Eine gleichwertige Charakterisierung lautet: Eine Teilmenge C eines Vektorraums V ist genau dann ein (linearer) Kegel, wenn für jeden nicht-negativen Skalar \lambda C \subseteq C gilt. Manchmal wird dies auch als  [0,\infty)C\subseteq C geschreiben

Abweichende Definitionen[Bearbeiten]

  • Manchmal wird nur gefordert, das wenn  x \in K ist, dass dann  \lambda x \in K für echt positives  \lambda > 0 ist. Dies führt dann zu dem unten besprochenen Begriff des punktierten Kegels.
  • Gelegentlich wird auch gefordert, dass ein Kegel auch abgeschlossen gegenüber Addition sein soll. Dies führt zum stärkeren Begriff des konvexen Kegels.

Arten von Kegeln[Bearbeiten]

Spitze und stumpfe Kegel[Bearbeiten]

Ein Kegel C heißt spitz, wenn er keine Gerade enthält, das heißt -C \cap C \subseteq \{0\}, andernfalls stumpf.

Punktierter Kegel[Bearbeiten]

Manche Autoren schränken obige Definition auf die Abgeschlossenheit unter der Multiplikation mit echt positiven Skalaren ein. In diesem Fall lassen sich punktierte Kegel (d.h. die 0_V ist nicht enthalten) und Kegel mit 0 unterscheiden.

Konvexer Kegel[Bearbeiten]

Hauptartikel: Konvexer Kegel

Ein konvexer Kegel ist ein Kegel, der konvex ist. Das Konvexitätskriterium für Mengen reduziert sich für Kegel zur Abgeschlossenheit bezüglich der Addition. Der Kegel K ist also genau denn ein konvexer Kegel , wenn für alle x,y \in K gilt, dass  x+y \in K . Konvexe Kegel spielen eine wichtige Rolle in der linearen Optimierung.

Affiner Kegel[Bearbeiten]

Wenn C-v für ein C \subseteq V und v \in V ein Kegel ist, so nennt man C (affinen) Kegel mit Spitze v. Anschaulich wird also ein (linearer) Kegel entlang des Ortsvektors \vec v verschoben.

Polyedrischer Kegel[Bearbeiten]

Ein Kegel  C \subset \mathbb{R}^n heißt ein Polyedrischer Kegel, wenn es eine Matrix  A gibt, so dass

 C= \{ x \in \mathbb{R}^n | Ax\leq 0 \}

ist. Ein Kegel ist genau dann ein polyedrischer Kegel, wenn er von einer endlichen Menge an Vektoren erzeugt wird.

Echter Kegel[Bearbeiten]

Ein Kegel wird ein echter Kegel genannt, wenn er konvex, spitz und abgeschlossen ist sowie ein nichtleeres Inneres hat. Echte Kegel im  \mathbb{R}^n entsprechen dem intuitiven Kegelbegriff am ehesten.

Beispiele[Bearbeiten]

  • Die Halbgerade
 \lambda \begin{pmatrix} 1 \\ 1 \end{pmatrix} \, , \, \lambda \geq 0
ist ein Kegel im  \mathbb{R}^2 . Allgemeiner ist jeder Strahl, der von der null ausgeht, ein Kegel.
 Q= \{x \in \mathbb{R}^2 \, , \, x_1,x_2 \geq 0 \}
ist ein konvexer Kegel, da Summen von Vektoren mit positiven Einträgen wieder positive Einträge haben und er daher abgeschlossen bezüglich Addition ist. Außerdem ist er spitz (er enthält keine Gerade), hat ein nichtleeres Inneres (zum Beispiel der Punkt  (1,1)^T liegt in seinem Inneren) und ist abgeschlossen. Somit ist er ein echter Kegel. Er ist sogar ein polyedrischer Kegel, da ein Vektor  x in  Q liegt, genau dann, wenn
 \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix} x \leq 0 ist.
  • Die offene rechte Halbebene
 O=\{x \in \mathbb{R}^2 \, , \, x_1> 0 \}
ist ein punktierter Kegel, da sie den Nullpunkt nicht enthält, aber abgeschlossen bezüglich der Multiplikation mit echt positiven Skalaren ist.
  • Die abgeschlossene rechte Halbebene
 A=\{x \in \mathbb{R}^2 \, , \, x_1\geq 0 \}
ist ein konvexer Kegel mit null, aber nicht spitz, da er als Gerade  \lambda (0,1)^T enthält mit  \lambda \in \mathbb{R} .

Abgesehen von den hier aufgeführten „anschaulichen“ Kegeln gibt es Beispiele für Kegel auch in beliebigen Vektorräumen. Beispiele wären:

  • Über dem Vektorraum der stetigen Funktionen bilden die konvexen Funktionen einen konvexen Kegel. Er ist nicht spitz, da es Funktionen gibt, für die sowohl  f als auch  -f konvex sind, dies sind die linearen Funktionen. Auch die konkaven Funktionen bilden einen Kegel.
  • Die Posynomialfunktionen bilden einen konvexen Kegel im Vektorraum aller Funktionen \mathbb{R}^n_{++} \to \mathbb{R}, die Monomialfunktionen immerhin noch einen (punktierten) Unterkegel, der aber nicht konvex ist.

Eigenschaften[Bearbeiten]

Operatoren[Bearbeiten]

Kegelhülle[Bearbeiten]

Hauptartikel: Kegelhülle

Die Kegelhülle \operatorname{cone}(X) ordnet einer beliebigen Teilmenge X \subseteq V den kleinsten Kegel der X ganz enthält zu. SIe ist definiert als

\operatorname{cone}(X) := \{\lambda x: \lambda \in \mathbb{R}_0^+, x \in X\}.

Dualer Kegel und Polarer Kegel[Bearbeiten]

Hauptartikel: Dualer Kegel

Der duale Kegel und der mit ihm eng verwandte polare Kegel lassen sich für jeden Kegel definieren und bilden die Menge aller Vektoren, die mit dem Kegel einen Winkel von weniger als neunzig Grad (im Falle des polaren kegels mit mehr als neunzig Grad) einschließen. Sie werden meist über das Skalarprodukt definiert, können aber auch allgemeiner über die duale Paarung definiert werden.

Konische Hülle[Bearbeiten]

Hauptartikel: Konische Hülle

Jeder Teilmenge eines Vektorraumes lässt sich ein kleinster konvexer Kegel zuordnen, der diese Menge enthält. Dieser Kegel wird die konische Hülle der Menge genannt.

Wichtige Kegel[Bearbeiten]

Positiver Orthant[Bearbeiten]

Der positive Orthant ist die Menge aller Vektoren im  \mathbb{R}^n , die nur positive Einträge haben.

 O=\{x \in \mathbb{R}^n \, | \, x_i \geq 0 \text{ für } i=1, \dots, n\} .

Er ist ein echter Kegel, der von den Einheitsvektoren endlich erzeugt wird und ist selbstdual bezüglich des Standardskalarproduktes. Insbesondere ist die von ihm erzeugte verallgemeinerte Ungleichung das "komponentenweise Kleinergleich".

Norm-Kegel[Bearbeiten]

Der Norm-Kegel im  \mathbb{R}^{n+1} ist definiert durch

 N= \{(x,t) \in \mathbb{R}^{n+1} \, | \, \Vert x \Vert \leq t \} .

Sein dualer Kegel ist wieder ein Norm-Kegel, aber bezüglich der dualen Norm

Lorentz-Kegel[Bearbeiten]

ist  \Vert  \cdot \Vert= \Vert \cdot \Vert_2 die Euklidische Norm, so heißt er der Norm-Kegel auch Lorentz-Kegel oder quadratischer Kegel, manchmal auch wie im englischen second order cone bzw ice-cream cone:

 L= \{(x,t) \in \mathbb{R}^{n+1} \, | \, \Vert x \Vert_2 \leq t \} .

Er ist ein echter, selbstdualer Kegel, der bei der Formulierung von SOCPs verwendet wird.

Euklidischer Kegel[Bearbeiten]

Für einen Winkel  \phi \in [0,\pi/2] ist der euklidische Kegel die Menge aller Vektoren in  \mathbb{R}^n , die mit einem vorgegebenen Vektor  c einen Winkel kleiner als  \phi einschließen

 C = \{x \in \mathbb{R}^n \, | \, \sphericalangle(x,c) \leq \phi \} .

Er entsteht durch (nichtsinguläre) lineare Transformation des Lorentz-kegels.

Positiv Semidefiniter Kegel[Bearbeiten]

Auf dem Vektorraum

 S^n:= \{A \in \mathbb{R}^{n \times n} \, | \, A^T=A\}

der symmetrischen reellen  n \times n -Matrizen bilden die positiv semidefiniten Matrizen einen Kegel

 S^n_+:= \{A \in S^n \, | \, x^TAx \geq 0 \text{ für alle } x \in \mathbb{R}^n \} ,

den sogenannten positiv semidefiniten Kegel oder gelegentlich auch nur semidefiniten Kegel. Er ist Konvex und Selbstdual bezüglich des Frobenius-Skalarproduktes. Er spielt eine wichtige Rolle in der semidefiniten Optimierung.

Sphärischer Schnitt[Bearbeiten]

Ist der Vektorraum V durch \|.\| \colon V \to \R normiert, so lässt sich die Zentralprojektion eines Kegels C \subseteq V auf den Einheitskreis S = \{x \in V | \|x\| = 1 \} betrachten. Diese ist durch

\pi_C\ \colon\ C \setminus \{0_V \} \to S\ ;\ x \mapsto \frac{x}{\|x\|}

erklärt. Ihr Bild \operatorname{img}(\pi_C) = C \cap S ist offenbar gleich dem Schnitt des Kegels mit dem Einheitskreis.

Ein Kegel wird durch seinen Kreisschnitt vollständig beschrieben, denn es gilt:

\operatorname{cone} (\operatorname{img}(\pi_C)) = C

Siehe auch[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1.  Andreas Fischer: Lineare Algebra. Teubner, Stuttgart 2003, ISBN 3-519-00370-8, S. 153.