Kegel (Lineare Algebra)

Grundbegriff und Definition

In der linearen Algebra ist ein (linearer) Kegel eine Teilmenge eines Vektorraums, die unter der Multiplikation mit nicht-negativen Skalaren abgeschlossen ist. Das bedeutet: Für jedes x ∈ C und jeden nicht-negativen Skalar λ ∈ 𝕂≥0 gilt auch λx ∈ C. Dabei ist 𝕂 ein geordneter Körper, zum Beispiel ℝ oder ℚ. Gleichwertig gilt λC ⊆ C für jeden nicht-negativen Skalar λ; dafür wird auch [0,∞)C ⊆ C geschrieben.

Fordert man zusätzlich die Abgeschlossenheit unter Addition, erhält man einen konvexen Kegel. Für Kegel ist das übliche Konvexitätskriterium damit besonders einfach: C ist genau dann konvex, wenn aus x,y ∈ C stets x+y ∈ C folgt. Konvexe Kegel sind unter anderem für die lineare Optimierung wichtig.

Arten und typische Beispiele

Ein Kegel heißt spitz, wenn er keine Gerade enthält. Formal gilt dann −C ∩ C ⊆ {0}; andernfalls heißt er stumpf. Je nach Definition unterscheiden manche Autoren außerdem Kegel, die nur unter der Multiplikation mit echt positiven Skalaren abgeschlossen sind. Ein punktierter Kegel enthält den Nullvektor 0V nicht, während ein Kegel mit 0 den Nullvektor enthält.

Ein polyedrischer Kegel C ⊆ 𝕂ⁿ lässt sich durch endlich viele lineare Ungleichungen beschreiben: Es gibt eine Matrix A ∈ 𝕂ᵐˣⁿ mit C = {x ∈ 𝕂ⁿ | Ax ≤ 0}. Die Ungleichung ist komponentenweise gemeint, also (Ax)i ≤ 0 für alle i ∈ {1,…,m}. Wegen A(x+y) = Ax+Ay ist jeder polyedrische Kegel unter Addition abgeschlossen und daher konvex.

Ein echter Kegel ist konvex, spitz und abgeschlossen und besitzt außerdem ein nichtleeres Inneres. Solche Kegel entsprechen dem anschaulichen Kegelbegriff im ℝⁿ. Wenn für C ⊆ V und v ∈ V die Menge C−v ein Kegel ist, heißt C ein affiner Kegel mit Spitze v. Anschaulich wird ein linearer Kegel dabei entlang des Ortsvektors v verschoben.

Eine Halbgerade λ(1,1)ᵀ mit λ ≥ 0 ist ein Kegel im ℝ²; allgemein ist jeder von 0 ausgehende Strahl ein Kegel. Der positive Quadrant Q = {x ∈ ℝ² | x₁,x₂ ≥ 0} ist ein echter und polyedrischer Kegel. Er ist durch die Bedingung ((−1,0),(0,−1))x ≤ 0 beschreibbar und enthält beispielsweise (1,1)ᵀ in seinem Inneren.

Die offene rechte Halbebene O = {x ∈ ℝ² | x₁ > 0} ist ein punktierter Kegel. Die abgeschlossene rechte Halbebene A = {x ∈ ℝ² | x₁ ≥ 0} ist ein konvexer Kegel mit 0, aber nicht spitz, weil sie die Gerade λ(0,1)ᵀ für λ ∈ ℝ enthält. Auch in allgemeinen Vektorräumen gibt es Kegel: Die konvexen Funktionen bilden einen konvexen, nicht spitzen Kegel; die konkaven Funktionen bilden ebenfalls einen Kegel. Posynomialfunktionen bilden einen konvexen Kegel, während Monomialfunktionen einen punktierten, aber nicht konvexen Unterkegel bilden.

Eigenschaften und Hülloperatoren

Der Schnitt einer Familie von Kegeln ist wieder ein Kegel. Deshalb bilden die Kegel ein Hüllensystem; der zugehörige Hüllenoperator heißt Kegelhülle. Auch die Vereinigung einer Familie von Kegeln und das Komplement eines Kegels sind wieder Kegel. Für zwei Kegel B und C sind außerdem −B sowie die Summe B+C Kegel. Sind B ⊆ V und C ⊆ W Kegel, so ist auch B×C ⊆ V×W ein Kegel.

Ein konvexer, abgeschlossener Kegel mit nichtleerem Inneren definiert eine Halbordnung. Daraus entstehen verallgemeinerte Ungleichungen und K-konvexe Funktionen, die den Begriff konvexer Funktionen verallgemeinern.

Die Kegelhülle cone(X) einer beliebigen Teilmenge X ⊆ V ist der kleinste Kegel, der X enthält. Sie ist definiert durch cone(X) = {λx | λ ∈ 𝕂≥0 und x ∈ X}.

Die konische Hülle ist dagegen der kleinste konvexe Kegel, der eine gegebene Menge enthält. Sie ist die konvexe Hülle der Kegelhülle beziehungsweise die Kegelhülle der konvexen Hülle.

Der duale Kegel und der eng verwandte polare Kegel bestehen aus Vektoren, die mit dem gegebenen Kegel über das Skalarprodukt beziehungsweise allgemeiner über eine duale Paarung bestimmte Winkelbedingungen erfüllen. Beim dualen Kegel sind die Winkel kleiner als 90 Grad, beim polaren Kegel größer als 90 Grad.

Wichtige Kegel in der Optimierung

Der positive Orthant ist O = {x ∈ ℝⁿ | xi ≥ 0 für i = 1,…,n}. Er besteht aus den Vektoren mit nicht-negativen Einträgen, ist ein echter Kegel und wird endlich durch die Einheitsvektoren erzeugt. Bezüglich des Standardskalarprodukts ist er selbstdual. Die von ihm erzeugte verallgemeinerte Ungleichung ist das komponentenweise Kleiner-gleich.

Der Norm-Kegel im ℝⁿ⁺¹ ist N = {(x,t) ∈ ℝⁿ⁺¹ | ‖x‖ ≤ t}. Sein dualer Kegel ist wieder ein Norm-Kegel, jedoch bezüglich der dualen Norm. Für die euklidische Norm ‖·‖₂ heißt dieser Kegel Lorentz-Kegel oder quadratischer Kegel: L = {(x,t) ∈ ℝⁿ⁺¹ | ‖x‖₂ ≤ t}. Er ist ein echter, selbstdualer Kegel und wird bei der Formulierung von SOCPs verwendet.

Für einen Winkel φ ∈ [0,π/2] ist der euklidische Kegel die Menge C = {x ∈ ℝⁿ | ∠(x,c) ≤ φ} aller Vektoren, die mit einem vorgegebenen Vektor c einen Winkel von höchstens φ einschließen. Er entsteht durch eine nichtsinguläre lineare Transformation des Lorentz-Kegels.

Im Vektorraum Sⁿ = {A ∈ ℝⁿˣⁿ | Aᵀ = A} der symmetrischen reellen n×n-Matrizen bilden die positiv semidefiniten Matrizen den Kegel Sⁿ₊ = {A ∈ Sⁿ | für alle x ∈ ℝⁿ gilt xᵀAx ≥ 0}. Dieser positiv semidefinite Kegel ist konvex und bezüglich des Frobenius-Skalarprodukts selbstdual. Als Ordnungskegel definiert er auf Sⁿ die Loewner-Halbordnung und ist deshalb für die semidefinite Optimierung wichtig.

Sphärischer Schnitt

Ist V ein normierter Vektorraum mit Norm ‖·‖, kann ein Kegel C ⊆ V durch seine Zentralprojektion auf den Einheitskreis S = {x ∈ V | ‖x‖ = 1} untersucht werden. Die Projektion ist definiert durch πC: C \ {0V} → S, x ↦ x/‖x‖. Ihr Bild ist genau C ∩ S, also der Schnitt des Kegels mit dem Einheitskreis.

Ein Kegel wird durch diesen sphärischen Schnitt vollständig bestimmt. Es gilt: cone(img(πC)) = C. Damit enthält der Einheitskreis-Schnitt genau die Richtungen des Kegels; durch die Kegelhülle werden daraus wieder alle Vektoren des Kegels gewonnen.