Dualer Kegel

Grundidee und Bedeutung

Der duale Kegel ist ein Kegel, der einem gegebenen Kegel zugeordnet wird. Er ist wichtig in der mathematischen Optimierung, zum Beispiel bei Dualitätsaussagen der Lagrange-Dualität. Eng verwandt ist er mit dem polaren Kegel.

Anschaulich beschreibt der duale Kegel diejenigen Vektoren oder Funktionale, die mit allen Elementen des ursprünglichen Kegels ein nichtnegatives Skalarprodukt beziehungsweise eine nichtnegative duale Paarung haben. In einem Hilbertraum bedeutet das: Die Vektoren des dualen Kegels schließen mit allen Vektoren des ursprünglichen Kegels einen Winkel von höchstens 90° ein.

Definition im Hilbertraum

Sei V ein Hilbertraum, also ein vollständiger Vektorraum mit Skalarprodukt ⟨.;.⟩, und sei K ein Kegel in V. Dann heißt

operatorname{dual}(K) = { y ∈ V | ∀ x ∈ K: ⟨y;x⟩ ≥ 0 }

der duale Kegel von K.

Das bedeutet: Ein Vektor y gehört genau dann zum dualen Kegel, wenn sein Skalarprodukt mit jedem x aus K nichtnegativ ist. Der duale Kegel wird gelegentlich auch mit K* oder K^D bezeichnet.

Allgemeine Definition

Im allgemeinen Fall liegt der duale Kegel nicht unbedingt im ursprünglichen Vektorraum V, sondern im Dualraum V*. Der Dualraum V* besteht aus den linearen Funktionalen auf V.

Ist K ein Kegel in V, dann ist der duale Kegel definiert durch

operatorname{dual}(K) := { y* ∈ V* | ∀ x ∈ K: ⟨y*;x⟩ ≥ 0 }.

Dabei bezeichnet ⟨.;.⟩ die duale Paarung. Das heißt konkret: ⟨y*;x⟩ := y*(x). Teilweise wird auch in unvollständigen Prähilberträumen die Hilbertraum-Form der Definition verwendet, damit die entstehenden Mengen als Kegel im Ursprungsraum V aufgefasst werden können.

Polarer und selbstdualer Kegel

Der polare Kegel wird ähnlich definiert, aber mit der entgegengesetzten Ungleichung:

operatorname{pol}(K) := { y* ∈ V* | ∀ x ∈ K: ⟨y*;x⟩ ≤ 0 }.

In einem Hilbertraum gilt entsprechend:

operatorname{pol}(K) = { y ∈ V | ∀ x ∈ K: ⟨y;x⟩ ≤ 0 }.

Anschaulich enthält der polare Kegel alle Vektoren, die mit allen Elementen des Kegels einen Winkel von mindestens 90° haben. Deshalb gilt K ∩ operatorname{pol}(K) = {0_V}.

Zwischen polarem und dualem Kegel besteht die Beziehung

operatorname{pol}(K) = -operatorname{dual}(K)

im jeweiligen Vektorraum. Diese Beziehung kann auch als Definition genutzt werden.

Ein Kegel heißt selbstdual, wenn operatorname{dual}(K) = K gilt. In der Literatur werden die Begriffe dualer Kegel und polarer Kegel gelegentlich mit vertauschter Ungleichungsrichtung verwendet; deshalb muss man immer auf die Richtung der Ungleichung achten.

Beispiele in R2

Betrachtet man in R^2 mit dem Standardskalarprodukt den Kegel

K := { x ∈ R^2 | x_1 ≥ 0, x_2 = 0 } = λ(1,0)^T mit λ ≥ 0,

so ist der duale Kegel die rechte Halbebene:

operatorname{dual}(K) = R^+ × R.

Denn für x ∈ K gilt x^T y = λ y_1. Dieser Ausdruck soll für alle λ ≥ 0 größer oder gleich 0 sein. Daher muss y_1 ≥ 0 gelten. Nach der Beziehung zwischen polarem und dualem Kegel ist der polare Kegel in diesem Fall die linke Halbebene.

Ändert man das Skalarprodukt, ändert sich auch der duale Kegel. Wird R^2 mit dem Skalarprodukt ⟨x;y⟩_A := x^T A y versehen, wobei

A = ((4,1),(1,2))

eine symmetrische positiv definite Matrix ist, dann ergibt sich für denselben Kegel

operatorname{dual}(K) = { y ∈ R^2 | 4y_1 + y_2 ≥ 0 }.

Das ist die Halbebene, die von der Geraden y_2 = -4y_1 begrenzt wird und den ersten Quadranten enthält. Das Skalarprodukt ist also entscheidend dafür, welcher duale oder polare Kegel entsteht.

Ein Beispiel für einen selbstdualen Kegel ist

K := { x ∈ R^2 | x_1 ≥ 0, x_2 ≥ 0 }.

Wichtige Eigenschaften

Der duale Kegel und der polare Kegel sind immer konvex. Konvex bedeutet hier: Verbindungsstrecken zwischen Punkten des Kegels bleiben im Kegel. Diese Eigenschaft gilt unabhängig davon, ob der ursprüngliche Kegel selbst konvex ist.

Ist V ein topologischer Vektorraum und V* sein topologischer Dualraum, dann sind der polare und der duale Kegel stets abgeschlossen.