Otimização Convexa - Cone Polar

Seja S um conjunto não vazio em $ \ mathbb {R} ^ n $ Então, o cone polar de S denotado por $ S ^ * $ é dado por $ S ^ * = \ left \ {p \ in \ mathbb {R } ^ n, p ^ Tx \ leq 0 \: \ forall x \ in S \ right \} $.

Observação

  • O cone polar é sempre convexo, mesmo que S não seja convexo.

  • Se S for um conjunto vazio, $ S ^ * = \ mathbb {R} ^ n $.

  • A polaridade pode ser vista como uma generalização da ortogonalidade.

Seja $ C \ subseteq \ mathbb {R} ^ n $ então o espaço ortogonal de C, denotado por $ C ^ \ perp = \ left \ {y \ in \ mathbb {R} ^ n: \ left \ langle x, y \ right \ rangle = 0 \ forall x \ in C \ right \} $.

Lema

Sejam $ S, S_1 $ e $ S_2 $ conjuntos não vazios em $ \ mathbb {R} ^ n $, então as seguintes afirmações são verdadeiras -

  • $ S ^ * $ é um cone convexo fechado.

  • $ S \ subseteq S ^ {**} $ onde $ S ^ {**} $ é um cone polar de $ S ^ * $.

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

Prova

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

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

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

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

    Portanto, $ S ^ * $ é um conjunto convexo.

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

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

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

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

    Portanto, $ S ^ * $ é um cone.

  • Para mostrar $ S ^ * $ está fechado, ou seja, para mostrar se $ p_n \ rightarrow p $ como $ n \ rightarrow \ infty $, então $ 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 $

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

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

    $ \ Rightarrow p \ in S ^ * $

    Portanto, $ S ^ * $ está fechado.

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

Seja $ x \ em S $, então $ \ forall p \ in S ^ *, p ^ T x \ leq 0 \ Rightarrow x ^ Tp \ leq 0 \ Rightarrow x \ in S ^ {**} $

Assim, $ S \ subseteq S ^ {**} $

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

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

Portanto, se $ \ hat {p} \ em S_2 ^ *, $ então $ \ hat {p} ^ Tx \ leq 0, \ forall x \ em S_2 $

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

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

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

Teorema

Seja C um cone convexo fechado não vazio, então $ C = C ^ ** $

Prova

$ C = C ^ {**} $ pelo lema anterior.

Para provar: $ x \ in C ^ {**} \ subseteq C $

Seja $ x \ em C ^ {**} $ e seja $ x \ notin C $

Então, pelo teorema da separação fundamental, existe um vetor $ p \ neq 0 $ e um escalar $ \ alpha $ tal que $ p ^ Ty \ leq \ alpha, \ forall y \ in C $

Portanto, $ p ^ Tx> \ alpha $

Mas como $ \ left (y = 0 \ right) \ in C $ e $ p ^ Ty \ leq \ alpha, \ forall y \ in C \ Rightarrow \ alpha \ geq 0 $ e $ p ^ Tx> 0 $

Se $ p \ notin C ^ * $, então existe algum $ \ bar {y} \ em C $ tal que $ p ^ T \ bar {y}> 0 $ e $ p ^ T \ left (\ lambda \ bar {y} \ right) $ pode ser arbitrariamente grande tomando $ \ lambda $ suficientemente grande.

Isso contradiz o fato de que $ p ^ Ty \ leq \ alpha, \ forall y \ in C $

Portanto, $ p \ in C ^ * $

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

Portanto, $ x ^ Tp \ leq 0 \ Rightarrow p ^ Tx \ leq 0 $

Mas $ p ^ Tx> \ alpha $

Assim é a contardição.

Assim, $ x \ em C $

Portanto, $ C = C ^ {**} $.