Kegel (Lineare Algebra)

Teilmenge eines Vektorraums
(Weitergeleitet von Semidefiniter Kegel)

In der linearen Algebra ist ein (linearer) Kegel eine Teilmenge eines Vektorraums, die abgeschlossen bzgl. Multiplikation mit positiven Skalaren ist. Fordert man zusätzlich, dass der Kegel abgeschlossen bezüglich der Addition ist, so nennt man den Kegel einen konvexen Kegel.

Ein Kegel im

Definition

Bearbeiten

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

Eine gleichwertige Charakterisierung lautet: Eine Teilmenge   eines Vektorraums   ist genau dann ein (linearer) Kegel, wenn für jeden nicht-negativen Skalar   gilt. Manchmal wird dies auch als   geschrieben.

Arten von Kegeln

Bearbeiten

Spitze und stumpfe Kegel

Bearbeiten

Ein Kegel   heißt spitz, wenn er keine Gerade enthält, das heißt  , 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   ist nicht enthalten) und Kegel mit 0 unterscheiden.

Konvexer Kegel

Bearbeiten

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   ist also genau dann ein konvexer Kegel, wenn für alle   gilt, dass  . Konvexe Kegel spielen eine wichtige Rolle in der linearen Optimierung.

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   entsprechen dem intuitiven Kegelbegriff am ehesten.

Affiner Kegel

Bearbeiten

Wenn   für ein   und   ein Kegel ist, so nennt man   (affinen) Kegel mit Spitze  . Anschaulich wird also ein (linearer) Kegel entlang des Ortsvektors   verschoben.

Beispiele

Bearbeiten
  • Die Halbgerade
 
ist ein Kegel im  . Allgemeiner ist jeder Strahl, der von Null ausgeht, ein Kegel.
 
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 liegt der Punkt   in seinem Inneren) und ist abgeschlossen. Somit ist er ein echter Kegel. Er ist sogar ein polyedrischer Kegel, da ein Vektor   in   liegt, genau dann, wenn
  ist.
  • Die offene rechte Halbebene
 
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
 
ist ein konvexer Kegel mit null, aber nicht spitz, da er als Gerade   enthält mit  .

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   als auch   konvex sind, dies sind die linearen Funktionen. Auch die konkaven Funktionen bilden einen Kegel.
  • Die Posynomialfunktionen bilden einen konvexen Kegel im Vektorraum aller Funktionen  , die Monomialfunktionen immerhin noch einen (punktierten) Unterkegel, der aber nicht konvex ist.

Eigenschaften

Bearbeiten
  • Der Schnitt einer Familie von Kegeln ist ein Kegel. Somit bilden die Kegel ein Hüllensystem, der zugehörige Hüllenoperator ist die Kegelhülle.
  • Die Vereinigung einer Familie von Kegeln ist wieder ein Kegel.
  • Das Komplement eines Kegels ist wieder ein Kegel.
  • Für zwei Kegel   sind   und die Summe   jeweils Kegel.
  • Für zwei Kegel   ist das direkte Produkt   wieder ein Kegel im jeweiligen Produktraum.
  • Ist der Kegel konvex, abgeschlossen und hat ein nichtleeres Inneres, so definiert er eine Halbordnung. Diese führt dann zu verallgemeinerten Ungleichungen und zur Definition von K-konvexen Funktionen, die konvexe Funktionen verallgemeinern.

Operatoren

Bearbeiten

Kegelhülle

Bearbeiten

Die Kegelhülle   ordnet einer beliebigen Teilmenge   den kleinsten Kegel, der   ganz enthält, zu. Sie ist definiert als

 .

Dualer Kegel und Polarer Kegel

Bearbeiten

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

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  , die nur positive Einträge haben.

 .

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   ist definiert durch

 .

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

Lorentz-Kegel

Bearbeiten

ist   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:

 .

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

Euklidischer Kegel

Bearbeiten

Für einen Winkel   ist der euklidische Kegel die Menge aller Vektoren in  , die mit einem vorgegebenen Vektor   einen Winkel kleiner als   einschließen:

 .

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

Positiv semidefiniter Kegel

Bearbeiten

Auf dem Vektorraum

 

der symmetrischen reellen  -Matrizen bilden die positiv semidefiniten Matrizen einen Kegel

 ,

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, da er als Ordnungskegel eine Halbordnung auf dem   definiert, die Loewner-Halbordnung.

Sphärischer Schnitt

Bearbeiten

Ist der Vektorraum   durch   normiert, so lässt sich die Zentralprojektion eines Kegels   auf den Einheitskreis   betrachten. Diese ist durch

 

erklärt. Ihr Bild   ist offenbar gleich dem Schnitt des Kegels mit dem Einheitskreis.

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

 

Siehe auch

Bearbeiten

Einzelnachweise

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