Optimisation convexe - Cône polaire

Soit S un ensemble non vide dans $ \ mathbb {R} ^ n $ Alors, le cône polaire de S noté $ S ^ * $ est donné par $ S ^ * = \ left \ {p \ in \ mathbb {R } ^ n, p ^ Tx \ leq 0 \: \ forall x \ in S \ right \} $.

Remarque

  • Le cône polaire est toujours convexe même si S n'est pas convexe.

  • Si S est un ensemble vide, $ S ^ * = \ mathbb {R} ^ n $.

  • La polarité peut être vue comme une généralisation de l'orthogonalité.

Soit $ C \ subseteq \ mathbb {R} ^ n $ alors l'espace orthogonal de C, noté $ C ^ \ perp = \ left \ {y \ in \ mathbb {R} ^ n: \ left \ langle x, y \ right \ rangle = 0 \ forall x \ in C \ right \} $.

Lemme

Soit $ S, S_1 $ et $ S_2 $ des ensembles non vides dans $ \ mathbb {R} ^ n $ alors les déclarations suivantes sont vraies -

  • $ S ^ * $ est un cône convexe fermé.

  • $ S \ subseteq S ^ {**} $ où $ S ^ {**} $ est un cône polaire de $ S ^ * $.

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

Preuve

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

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

    Pour $ \ 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 + \ gauche (1- \ lambda \ droite) x_ {2} ^ {T} \ leq 0 $

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

    Donc $ S ^ * $ est un ensemble convexe.

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

    Par conséquent, $ \ lambda p ^ T x \ leq 0, $

    $ \ Flèche droite \ gauche (\ lambda p \ droite) ^ T x \ leq 0 $

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

    Ainsi, $ S ^ * $ est un cône.

  • Montrer que $ S ^ * $ est fermé, c'est-à-dire montrer si $ p_n \ rightarrow p $ comme $ n \ rightarrow \ infty $, alors $ p \ dans S ^ * $

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

    Comme $ p_n \ rightarrow p $ comme $ n \ rightarrow \ infty \ Rightarrow \ left (p_n \ rightarrow p \ right) \ rightarrow 0 $

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

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

    $ \ Flèche droite p \ dans S ^ * $

    Par conséquent, $ S ^ * $ est fermé.

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

Soit $ x \ dans S $, puis $ \ forall p \ in S ^ *, p ^ T x \ leq 0 \ Rightarrow x ^ Tp \ leq 0 \ Rightarrow x \ in S ^ {**} $

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

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

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

Donc, si $ \ hat {p} \ in S_2 ^ *, $ alors $ \ 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 \ dans S_1 ^ * $

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

Théorème

Soit C un cône convexe fermé non vide, alors $ C = C ^ ** $

Preuve

$ C = C ^ {**} $ par le lemme précédent.

Pour prouver: $ x \ in C ^ {**} \ subseteq C $

Soit $ x \ in C ^ {**} $ et soit $ x \ notin C $

Alors par théorème de séparation fondamental, il existe un vecteur $ p \ neq 0 $ et un scalaire $ \ alpha $ tel que $ p ^ Ty \ leq \ alpha, \ forall y \ dans C $

Par conséquent, $ p ^ Tx> \ alpha $

Mais puisque $ \ left (y = 0 \ right) \ en C $ et $ p ^ Ty \ leq \ alpha, \ forall y \ in C \ Rightarrow \ alpha \ geq 0 $ et $ p ^ Tx> 0 $

Si $ p \ notin C ^ * $, alors il existe des $ \ bar {y} \ dans C $ tels que $ p ^ T \ bar {y}> 0 $ et $ p ^ T \ left (\ lambda \ bar {y} \ right) $ peut être rendu arbitrairement grand en prenant $ \ lambda $ suffisamment grand.

Cela contredit le fait que $ p ^ Ty \ leq \ alpha, \ forall y \ in C $

Par conséquent, $ p \ dans C ^ * $

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

Par conséquent, $ x ^ Tp \ leq 0 \ Rightarrow p ^ Tx \ leq 0 $

Mais $ p ^ Tx> \ alpha $

Ainsi est la contardiction.

Ainsi, $ x \ en C $

D'où $ C = C ^ {**} $.