Optimización convexa: cono polar

Sea S un conjunto no vacío en $ \ mathbb {R} ^ n $ Entonces, el cono polar de S denotado por $ S ^ * $ viene dado por $ S ^ * = \ left \ {p \ in \ mathbb {R } ^ n, p ^ Tx \ leq 0 \: \ forall x \ in S \ right \} $.

Observación

  • El cono polar siempre es convexo incluso si S no es convexo.

  • Si S es un conjunto vacío, $ S ^ * = \ mathbb {R} ^ n $.

  • La polaridad puede verse como una generalización de la ortogonalidad.

Sea $ C \ subseteq \ mathbb {R} ^ n $ y luego el espacio 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

Deje que $ S, S_1 $ y $ S_2 $ sean conjuntos no vacíos en $ \ mathbb {R} ^ n $, entonces las siguientes declaraciones son verdaderas:

  • $ S ^ * $ es un cono convexo cerrado.

  • $ S \ subseteq S ^ {**} $ donde $ S ^ {**} $ es un cono polar de $ S ^ * $.

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

Prueba

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

  • Sea $ x_1, x_2 \ in S ^ * \ Rightarrow x_ {1} ^ {T} x \ leq 0 $ y $ 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 $

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

    Por tanto, $ S ^ * $ es un conjunto convexo.

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

    Por lo tanto, $ \ lambda p ^ T x \ leq 0, $

    $ \ Flecha derecha \ izquierda (\ lambda p \ derecha) ^ T x \ leq 0 $

    $ \ Flecha derecha \ lambda p \ in S ^ * $

    Por tanto, $ S ^ * $ es un cono.

  • Para mostrar que $ S ^ * $ está cerrado, es decir, para mostrar si $ p_n \ rightarrow p $ como $ n \ rightarrow \ infty $, entonces $ p \ in S ^ * $

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

    Como $ p_n \ rightarrow p $ como $ n \ rightarrow \ infty \ Rightarrow \ left (p_n \ rightarrow p \ right) \ rightarrow 0 $

    Por lo tanto $ p_ {n} ^ {T} x \ rightarrow p ^ {T} x $. Pero $ p_ {n} ^ {T} x \ leq 0, \: \ forall x \ in S $

    Por lo tanto, $ p ^ Tx \ leq 0, \ forall x \ in S $

    $ \ Flecha derecha p \ en S ^ * $

    Por tanto, $ S ^ * $ está cerrado.

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

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

Entonces, $ 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 $

Por lo tanto, si $ \ hat {p} \ in S_2 ^ *, $ entonces $ \ 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 ^ * $

$ \ Flecha derecha S_2 ^ * \ subseteq S_1 ^ * $

Teorema

Sea C un cono convexo cerrado no vacío, entonces $ C = C ^ ** $

Prueba

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

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

Deje $ x \ en C ^ {**} $ y deje $ x \ notin C $

Entonces, por el teorema de separación fundamental, existe un vector $ p \ neq 0 $ y un escalar $ \ alpha $ tal que $ p ^ Ty \ leq \ alpha, \ forall y \ in C $

Por lo tanto, $ p ^ Tx> \ alpha $

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

Si $ p \ notin C ^ * $, entonces existe algo $ \ bar {y} \ en C $ tal que $ p ^ T \ bar {y}> 0 $ y $ p ^ T \ left (\ lambda \ bar {y} \ right) $ puede hacerse arbitrariamente grande tomando $ \ lambda $ suficientemente grande.

Esto contradice el hecho de que $ p ^ Ty \ leq \ alpha, \ forall y \ in C $

Por lo tanto, $ p \ en C ^ * $

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

Por lo tanto, $ x ^ Tp \ leq 0 \ Rightarrow p ^ Tx \ leq 0 $

Pero $ p ^ Tx> \ alpha $

Así es la contardicción.

Por tanto, $ x \ en C $

Por tanto, $ C = C ^ {**} $.