Optymalizacja wypukłości - stożek biegunowy

Niech S będzie niepustym zbiorem w $ \ mathbb {R} ^ n $ Wtedy stożek biegunowy S oznaczony przez $ S ^ * $ jest określony przez $ S ^ * = \ left \ {p \ in \ mathbb {R } ^ n, p ^ Tx \ leq 0 \: \ forall x \ in S \ right \} $.

Uwaga

  • Stożek biegunowy jest zawsze wypukły, nawet jeśli S nie jest wypukły.

  • Jeśli S jest pusty, to $ S ^ * = \ mathbb {R} ^ n $.

  • Biegunowość można postrzegać jako uogólnienie ortogonalności.

Niech $ C \ subseteq \ mathbb {R} ^ n $, a następnie ortogonalna przestrzeń C, oznaczona przez $ C ^ \ perp = \ left \ {y \ in \ mathbb {R} ^ n: \ left \ langle x, y \ right \ rangle = 0 \ forall x \ in C \ right \} $.

Lemat

Niech $ S, S_1 $ i $ S_2 $ będą niepustymi zbiorami w $ \ mathbb {R} ^ n $, wtedy poniższe stwierdzenia są prawdziwe -

  • $ S ^ * $ to zamknięty wypukły stożek.

  • $ S \ subseteq S ^ {**} $ gdzie $ S ^ {**} $ jest stożkiem biegunowym o długości $ S ^ * $.

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

Dowód

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

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

    Dla $ \ 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 $

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

    Dlatego $ S ^ * $ jest zbiorem wypukłym.

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

    Dlatego $ \ lambda p ^ T x \ leq 0, $

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

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

    Zatem $ S ^ * $ jest stożkiem.

  • Aby pokazać $ S ^ * $ jest zamknięte, tj. Pokazać, czy $ p_n \ rightarrow p $ as $ n \ rightarrow \ infty $, a następnie $ p \ in S ^ * $

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

    As $ p_n \ rightarrow p $ as $ n \ rightarrow \ infty \ Rightarrow \ left (p_n \ rightarrow p \ right) \ rightarrow 0 $

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

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

    $ \ Rightarrow p \ in S ^ * $

    Stąd $ S ^ * $ jest zamknięte.

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

Niech $ x \ in S $, a następnie $ \ forall p \ in S ^ *, p ^ T x \ leq 0 \ Rightarrow x ^ Tp \ leq 0 \ Rightarrow x \ in S ^ {**} $

Zatem $ S \ subseteq S ^ {**} $

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

Ponieważ $ S_1 \ subseteq S_2 \ Rightarrow \ forall x \ in S_2 \ Rightarrow \ forall x \ in S_1 $

Dlatego jeśli $ \ hat {p} \ in S_2 ^ *, $ then $ \ 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 ^ * $

Twierdzenie

Niech C będzie niepustym zamkniętym wypukłym stożkiem, a następnie $ C = C ^ ** $

Dowód

$ C = C ^ {**} $ według poprzedniego lematu.

Aby udowodnić: $ x \ in C ^ {**} \ subseteq C $

Niech $ x \ w C ^ {**} $ i niech $ x \ notin C $

Następnie według twierdzenia o separacji fundamentalnej istnieje wektor $ p \ neq 0 $ i skalar $ \ alpha $ takie, że $ p ^ Ty \ leq \ alpha, \ forall y \ in C $

Dlatego $ p ^ Tx> \ alpha $

Ale ponieważ $ \ left (y = 0 \ right) \ in C $ i $ p ^ Ty \ leq \ alpha, \ forall y \ in C \ Rightarrow \ alpha \ geq 0 $ i $ p ^ Tx> 0 $

Jeśli $ p \ notin C ^ * $, to istnieje taki $ \ bar {y} \ in C $ taki, że $ p ^ T \ bar {y}> 0 $ i $ p ^ T \ left (\ lambda \ bar {y} \ right) $ można uczynić dowolnie dużym, przyjmując $ \ lambda $ wystarczająco duże.

Jest to sprzeczne z faktem, że $ p ^ Ty \ leq \ alpha, \ forall y \ in C $

Dlatego $ p \ w C ^ * $

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

Dlatego $ x ^ Tp \ leq 0 \ Rightarrow p ^ Tx \ leq 0 $

Ale $ p ^ Tx> \ alpha $

Tak jest w przypadku sprzeczności.

Zatem $ x \ w C $

Stąd $ C = C ^ {**} $.