Konvexe Optimierung - Polkegel

Sei S eine nicht leere Menge in $ \ mathbb {R} ^ n $. Dann ist der mit $ S ^ * $ bezeichnete Polarkegel von S gegeben durch $ S ^ * = \ left \ {p \ in \ mathbb {R. } ^ n, p ^ Tx \ leq 0 \: \ forall x \ in S \ right \} $.

Anmerkung

• Der Polkegel ist immer konvex, auch wenn S nicht konvex ist.

• Wenn S leer ist, ist $ S ^ * = \ mathbb {R} ^ n $.

• Die Polarität kann als Verallgemeinerung der Orthogonalität angesehen werden.

Sei $ C \ subseteq \ mathbb {R} ^ n $ dann der orthogonale Raum von C, bezeichnet mit $ C ^ \ perp = \ left \ {y \ in \ mathbb {R} ^ n: \ left \ langle x, y \ right \ rangle = 0 \ forall x \ in C \ right \} $.

Lemma

Sei $ S, S_1 $ und $ S_2 $ nicht leere Mengen in $ \ mathbb {R} ^ n $, dann sind die folgenden Aussagen wahr -

• $ S ^ * $ ist ein geschlossener konvexer Kegel.

• $ S \ subseteq S ^ {**} $ wobei $ S ^ {**} $ ein Polarkegel von $ S ^ * $ ist.

• $ S_1 \ subseteq S_2 \ Rightarrow S_ {2} ^ {*} \ subseteq S_ {1} ^ {*} $.

Beweis

Step 1 - $ S ^ * = \ left \ {p \ in \ mathbb {R} ^ n, p ^ Tx \ leq 0 \: \ forall \: x \ in S \ right \} $

• Sei $ x_1, x_2 \ in S ^ * \ Rightarrow x_ {1} ^ {T} x \ leq 0 $ und $ x_ {2} ^ {T} x \ leq 0, \ forall x \ in S $

  Für $ \ lambda \ in \ left (0, 1 \ right), \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right] ^ Tx = \ left [\ left (\ lambda x_1 \ right) ) ^ T + \ left \ {\ left (1- \ lambda \ right) x_ {2} \ right \} ^ {T} \ right] x, \ forall x \ in S $

  $ = \ left [\ lambda x_ {1} ^ {T} + \ left (1- \ lambda \ right) x_ {2} ^ {T} \ right] x = \ lambda x_ {1} ^ {T} x + \ left (1- \ lambda \ right) x_ {2} ^ {T} \ leq 0 $

  Also $ \ lambda x_1 + \ left (1- \ lambda \ right) x_ {2} \ in S ^ * $

  Daher ist $ S ^ * $ eine konvexe Menge.

• Für $ \ lambda \ geq 0 ist p ^ {T} x \ leq 0, \ forall \: x \ in S $

  Daher ist $ \ lambda p ^ T x \ leq 0, $

  $ \ Rightarrow \ left (\ lambda p \ right) ^ T x \ leq 0 $

  $ \ Rightarrow \ lambda p \ in S ^ * $

  Somit ist $ S ^ * $ ein Kegel.

• Das Anzeigen von $ S ^ * $ ist geschlossen, dh das Anzeigen von $ p_n \ rightarrow p $ als $ n \ rightarrow \ infty $, dann $ p \ in S ^ * $

  $ \ forall x \ in S, p_ {n} ^ {T} xp ^ T x = \ left (p_n-p \ right) ^ T x $

  Als $ p_n \ rightarrow p $ als $ n \ rightarrow \ infty \ Rightarrow \ left (p_n \ rightarrow p \ right) \ rightarrow 0 $

  Daher $ p_ {n} ^ {T} x \ rightarrow p ^ {T} x $. Aber $ p_ {n} ^ {T} x \ leq 0, \: \ forall x \ in S $

  Somit ist $ p ^ Tx \ leq 0, \ forall x \ in S $

  $ \ Rightarrow p \ in S ^ * $

  Daher ist $ S ^ * $ geschlossen.

Step 2 - $ S ^ {**} = \ left \ {q \ in \ mathbb {R} ^ n: q ^ T p \ leq 0, \ forall p \ in S ^ * \ right \} $

Sei $ x \ in S $, dann $ \ forall p \ in S ^ *, p ^ T x \ leq 0 \ Rightarrow x ^ Tp \ leq 0 \ Rightarrow x \ in S ^ {**} $

Somit ist $ S \ subseteq S ^ {**} $

Step 3 - $ S_2 ^ * = \ left \ {p \ in \ mathbb {R} ^ n: p ^ Tx \ leq 0, \ forall x \ in S_2 \ right \} $

Da $ S_1 \ subseteq S_2 \ Rightarrow \ forall x \ in S_2 \ Rightarrow \ forall x \ in S_1 $

Wenn also $ \ hat {p} \ in S_2 ^ *, $ dann $ \ hat {p} ^ Tx \ leq 0, \ forall x \ in S_2 $

$ \ Rightarrow \ hat {p} ^ Tx \ leq 0, \ forall x \ in S_1 $

$ \ Rightarrow \ hat {p} ^ T \ in S_1 ^ * $

$ \ Rightarrow S_2 ^ * \ subseteq S_1 ^ * $

Satz

Sei C ein nicht leerer geschlossener konvexer Kegel, dann ist $ C = C ^ ** $

Beweis

$ C = C ^ {**} $ nach vorherigem Lemma.

Zum Beweis: $ x \ in C ^ {**} \ subseteq C $

Lassen Sie $ x \ in C ^ {**} $ und lassen Sie $ x \ notin C $

Dann existiert nach dem fundamentalen Trennungssatz ein Vektor $ p \ neq 0 $ und ein Skalar $ \ alpha $, so dass $ p ^ Ty \ leq \ alpha, \ forall y \ in C $

Daher ist $ p ^ Tx> \ alpha $

Aber da $ \ left (y = 0 \ right) \ in C $ und $ p ^ Ty \ leq \ alpha, \ forall y \ in C \ Rightarrow \ alpha \ geq 0 $ und $ p ^ Tx> 0 $

Wenn $ p \ notin C ^ * $ ist, existiert in C $ ein $ \ bar {y} \, so dass $ p ^ T \ bar {y}> 0 $ und $ p ^ T \ left (\ lambda \ bar) {y} \ right) $ kann beliebig groß gemacht werden, indem $ \ lambda $ ausreichend groß genommen wird.

Dies widerspricht der Tatsache, dass $ p ^ Ty \ leq \ alpha, \ forall y \ in C $

Daher $ p \ in C ^ * $

Da $ x \ in C ^ * = \ left \ {q: q ^ Tp \ leq 0, \ forall p \ in C ^ * \ right \} $

Daher ist $ x ^ Tp \ leq 0 \ Rightarrow p ^ Tx \ leq 0 $

Aber $ p ^ Tx> \ alpha $

So ist Widerspruch.

Also $ x \ in C $

Daher ist $ C = C ^ {**} $.