Dışbükey Optimizasyon - Polar Cone

S $ \ mathbb {R} ^ n $ içinde boş olmayan bir küme olsun. O zaman, S'nin $ S ^ * $ ile gösterilen kutupsal konisi $ S ^ * = \ left \ {p \ in \ mathbb {R ile verilir } ^ n, p ^ Tx \ leq 0 \: \ forall x \ in S \ right \} $.

Açıklama

• Kutupsal koni, S dışbükey olmasa bile her zaman dışbükeydir.

• S boş küme ise, $ S ^ * = \ mathbb {R} ^ n $.

• Polarite, ortogonalitenin bir genellemesi olarak görülebilir.

$ C \ subseteq \ mathbb {R} ^ n $ olsun, sonra C'nin ortogonal uzayını $ C ^ \ perp = \ left \ {y \ in \ mathbb {R} ^ n: \ left \ langle x, y ile gösterilen \ right \ rangle = 0 \ forall x \ in C \ right \} $.

Lemma

$ S, S_1 $ ve $ S_2 $, $ \ mathbb {R} ^ n $ içinde boş kümeler olmasın, o zaman aşağıdaki ifadeler doğrudur -

• $ S ^ * $ kapalı bir dışbükey konidir.

• $ S \ subseteq S ^ {**} $, burada $ S ^ {**} $, $ S ^ * $ şeklinde bir kutup konisidir.

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

Kanıt

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

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

  $ \ Lambda \ in \ left (0, 1 \ right), \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right] ^ Tx = \ left [\ left (\ lambda x_1 \ sağ ) ^ 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} \ sağ] x = \ lambda x_ {1} ^ {T} x + \ left (1- \ lambda \ right) x_ {2} ^ {T} \ leq 0 $

  Böylece S ^ * $ içinde $ \ lambda x_1 + \ left (1- \ lambda \ right) x_ {2} \

  Dolayısıyla $ S ^ * $ bir dışbükey kümedir.

• S $ için $ \ lambda \ geq 0, p ^ {T} x \ leq 0, \ forall \: x \ için

  Bu nedenle, $ \ lambda p ^ T x \ leq 0, $

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

  S ^ * $ içinde $ \ Rightarrow \ lambda p \

  Böylece, $ S ^ * $ bir konidir.

• $ S ^ * $ kapalı olduğunu göstermek için, yani $ p_n \ rightarrow p $ 'ın $ n \ rightarrow \ infty $ olduğunu, ardından S ^ * $ içinde $ p \ olduğunu göstermek için

  S içinde $ \ forall x \, p_ {n} ^ {T} xp ^ T x = \ left (p_n-p \ sağ) ^ T x $

  $ P_n \ rightarrow p $, $ n \ rightarrow \ infty \ Rightarrow \ left (p_n \ rightarrow p \ right) \ rightarrow 0 $ olarak

  Dolayısıyla, $ p_ {n} ^ {T} x \ rightarrow p ^ {T} x $. Ama $ p_ {n} ^ {T} x \ leq 0, \: \ forall x \ S $ içinde

  Böylece, S $ için $ p ^ Tx \ leq 0, \ forall x \

  S ^ * $ içinde $ \ Rightarrow p \

  Bu nedenle, $ S ^ * $ kapalıdır.

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

S $ içinde $ x \, sonra S ^ * için $ \ forall p \, p ^ T x \ leq 0 \ Rightarrow x ^ Tp \ leq 0 \ Rightarrow x \ in S ^ {**} $

Böylece, $ S \ subseteq S ^ {**} $

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

$ S_1 \ subseteq S_2 \ Rightarrow \ forall x \ S_2 \ Rightarrow \ forall x \ S_1 $ içinde beri

Bu nedenle, S_2 ^ * içinde $ \ hat {p} \ ise, $ \ hat {p} ^ Tx \ leq 0, \ forall x \ S_2 $ içinde

$ \ Rightarrow \ hat {p} ^ Tx \ leq 0, \ forall x \ S_1 $ içinde

S_1 ^ * $ içinde $ \ Rightarrow \ hat {p} ^ T \

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

Teoremi

C boş olmayan kapalı bir dışbükey koni olsun, sonra $ C = C ^ ** $

Kanıt

$ C = C ^ {**} $ önceki lemmaya göre.

Kanıtlamak için: $ x \ in C ^ {**} \ subseteq C $

$ X \ in C ^ {**} $ ve $ x \ notin C $ olsun

Daha sonra temel ayırma teoremine göre, bir $ p \ neq 0 $ vektörü ve C $ 'da $ p ^ Ty \ leq \ alpha, \ forall y \ şeklinde bir skaler $ \ alpha $ vardır.

Bu nedenle, $ p ^ Tx> \ alpha $

Ancak C $ ve $ p ^ Ty \ leq \ alpha'da $ \ left (y = 0 \ right) \ olduğundan, C \ Rightarrow \ alpha \ geq 0 $ ve $ p ^ Tx> 0 $ içinde \ forall y \

$ P \ C ^ * $ içinde değilse, o zaman C $ içinde $ p ^ T \ bar {y}> 0 $ ve $ p ^ T \ left (\ lambda \ bar olacak şekilde bir $ \ bar {y} \ vardır {y} \ right) $, $ \ lambda $ yeterince büyük alınarak keyfi olarak büyük yapılabilir.

Bu, C $ 'da $ p ^ Ty \ leq \ alpha, \ forall y \ olduğu gerçeğiyle çelişir.

Bu nedenle, C ^ * $ içinde $ p \

C ^ * = \ left \ {q: q ^ Tp \ leq 0, \ forall p \ içinde C ^ * \ right \} $ içinde $ x \ olduğundan

Bu nedenle, $ x ^ Tp \ leq 0 \ Rightarrow p ^ Tx \ leq 0 $

Ama $ p ^ Tx> \ alpha $

Bu bir ihtilaftır.

Böylece, C $ 'da $ x \

Dolayısıyla $ C = C ^ {**} $.