Optimisation convexe - Problème de programmation
Il existe quatre types de problèmes de programmation convexe -
Step 1 - $ min \: f \ left (x \ right) $, où $ x \ in S $ et S un ensemble convexe non vide dans $ \ mathbb {R} ^ n $ et $ f \ left (x \ right ) $ est une fonction convexe.
Step 2 - $ min \: f \ left (x \ right), x \ in \ mathbb {R} ^ n $ soumis à
$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ et $ g_i \ left (x \ right) $ est une fonction convexe.
$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ et $ g_i \ left (x \ right) $ est une fonction concave.
$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ et $ g_i \ left (x \ right) $ est une fonction linéaire.
où $ f \ left (x \ right) $ est une fonction convexe.
Step 3 - $ max \: f \ left (x \ right) $ où $ x \ in S $ et S un ensemble convexe non vide dans $ \ mathbb {R} ^ n $ et $ f \ left (x \ right) $ est une fonction concave.
Step 4 - $ min \: f \ left (x \ right) $, où $ x \ in \ mathbb {R} ^ n $ soumis à
$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ et $ g_i \ left (x \ right) $ est une fonction convexe.
$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ et $ g_i \ left (x \ right) $ est une fonction concave.
$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ et $ g_i \ left (x \ right) $ est une fonction linéaire.
où $ f \ left (x \ right) $ est une fonction concave.
Cône de direction faisable
Soit S un ensemble non vide dans $ \ mathbb {R} ^ n $ et soit $ \ hat {x} \ in \: Closure \ left (S \ right) $, puis le cône de direction faisable de S à $ \ hat {x} $, noté D, est défini comme $ D = \ left \ {d: d \ neq 0, \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta \ right), \ delta> 0 \ right \} $
Chaque vecteur non nul $ d \ dans D $ est appelé direction réalisable.
Pour une fonction donnée $ f: \ mathbb {R} ^ n \ Rightarrow \ mathbb {R} $ le cône de direction d'amélioration à $ \ hat {x} $ est noté F et est donné par
$$ F = \ left \ {d: f \ left (\ hat {x} + \ lambda d \ right) \ leq f \ left (\ hat {x} \ right), \ forall \ lambda \ in \ left ( 0, \ delta \ droite), \ delta> 0 \ droite \} $$
Chaque direction $ d \ dans F $ est appelée une direction d'amélioration ou direction de descente de f à $ \ hat {x} $
Théorème
Necessary Condition
Considérons le problème $ min f \ left (x \ right) $ tel que $ x \ in S $ où S est un ensemble non vide dans $ \ mathbb {R} ^ n $. Supposons que f soit différentiable en un point $ \ hat {x} \ dans S $. Si $ \ hat {x} $ est une solution optimale locale, alors $ F_0 \ cap D = \ phi $ où $ F_0 = \ left \ {d: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \} $ et D est un cône de direction possible.
Sufficient Condition
Si $ F_0 \ cap D = \ phi $ f est une fonction pseudoconvexe à $ \ hat {x} $ et qu'il existe un voisinage de $ \ hat {x}, N_ \ varepsilon \ left (\ hat {x} \ right) , \ varepsilon> 0 $ tel que $ d = x- \ hat {x} \ in D $ pour tout $ x \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $, puis $ \ hat {x} $ est la solution optimale locale.
Preuve
Necessary Condition
Soit $ F_0 \ cap D \ neq \ phi $, c'est-à-dire qu'il existe un $ d \ dans F_0 \ cap D $ tel que $ d \ dans F_0 $ et $ d \ dans D $
Puisque $ d \ dans D $, il existe donc $ \ delta_1> 0 $ tel que $ \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta_1 \ right). $
Puisque $ d \ in F_0 $, donc $ \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 $
Ainsi, il existe $ \ delta_2> 0 $ tel que $ f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ in f \ gauche (0, \ delta_2 \ droite) $
Soit $ \ delta = min \ left \ {\ delta_1, \ delta_2 \ right \} $
Alors $ \ hat {x} + \ lambda d \ in S, f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ dans f \ left (0, \ delta \ right) $
Mais $ \ hat {x} $ est la solution optimale locale.
C'est donc une contradiction.
Ainsi $ F_0 \ cap D = \ phi $
Sufficient Condition
Soit $ F_0 \ cap D \ neq \ phi $ nd soit f une fonction pseudoconvexe.
Soit un voisinage de $ \ hat {x}, N _ {\ varepsilon} \ left (\ hat {x} \ right) $ tel que $ d = x- \ hat {x}, \ forall x \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $
Soit $ \ hat {x} $ n'est pas une solution optimale locale.
Ainsi, il existe $ \ bar {x} \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $ tel que $ f \ left (\ bar {x} \ right) <f \ left ( \ hat {x} \ right) $
Par hypothèse sur $ S \ cap N_ \ varepsilon \ left (\ hat {x} \ right), d = \ left (\ bar {x} - \ hat {x} \ right) \ in D $
Par pseudoconvexe de f,
$$ f \ left (\ hat {x} \ right)> f \ left (\ bar {x} \ right) \ Rightarrow \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (\ bar {x} - \ hat {x} \ right) <0 $$
$ \ Rightarrow \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 $
$ \ Rightarrow d \ in F_0 $
d'où $ F_0 \ cap D \ neq \ phi $
ce qui est une contradiction.
Par conséquent, $ \ hat {x} $ est la solution optimale locale.
Considérons le problème suivant: $ min \: f \ left (x \ right) $ où $ x \ in X $ tel que $ g_x \ left (x \ right) \ leq 0, i = 1,2, ..., m $
$ f: X \ rightarrow \ mathbb {R}, g_i: X \ rightarrow \ mathbb {R} ^ n $ et X est un ensemble ouvert dans $ \ mathbb {R} ^ n $
Soit $ S = \ left \ {x: g_i \ left (x \ right) \ leq 0, \ forall i \ right \} $
Soit $ \ hat {x} \ in X $, puis $ M = \ left \ {1,2, ..., m \ right \} $
Soit $ I = \ left \ {i: g_i \ left (\ hat {x} \ right) = 0, i \ in M \ right \} $ où I est appelé ensemble d'index pour toutes les contraintes actives à $ \ hat {x } $
Soit $ J = \ left \ {i: g_i \ left (\ hat {x} \ right) <0, i \ in M \ right \} $ où J est appelé ensemble d'index pour toutes les contraintes actives à $ \ hat {x } $.
Soit $ F_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \} $
Soit $ G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gI \ left (\ hat {x} \ right) ^ T d <0 \ right \} $
ou $ G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gi \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I \ right \} $
Lemme
Si $ S = \ left \ {x \ in X: g_i \ left (x \ right) \ leq 0, \ forall i \ in I \ right \} $ et X est un ensemble ouvert non vide dans $ \ mathbb {R } ^ n $. Soit $ \ hat {x} \ in S $ et $ g_i $ sont différents en $ \ hat {x}, i \ in I $ et soit $ g_i $ où $ i \ in J $ sont continus en $ \ hat {x } $, puis $ G_0 \ subseteq D $.
Preuve
Soit $ d \ dans G_0 $
Puisque $ \ hat {x} \ in X $ et X est un ensemble ouvert, il existe donc $ \ delta_1> 0 $ tel que $ \ hat {x} + \ lambda d \ in X $ pour $ \ lambda \ in \ gauche (0, \ delta_1 \ droite) $
Aussi puisque $ g_ \ hat {x} <0 $ et $ g_i $ sont continus en $ \ hat {x}, \ forall i \ in J $, il existe $ \ delta_2> 0 $, $ g_i \ left (\ hat {x} + \ lambda d \ right) <0, \ lambda \ in \ left (0, \ delta_2 \ right) $
Puisque $ d \ in G_0 $, donc, $ \ bigtriangledown g_i \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I $ donc il existe $ \ delta_3> 0, g_i \ left (\ hat {x} + \ lambda d \ right) <g_i \ left (\ hat {x} \ right) = 0 $, pour $ \ lambda \ in \ left (0, \ delta_3 \ right) i \ in J $
Soit $ \ delta = min \ left \ {\ delta_1, \ delta_2, \ delta_3 \ right \} $
donc $ \ hat {x} + \ lambda d \ in X, g_i \ left (\ hat {x} + \ lambda d \ right) <0, i \ in M $
$ \ Rightarrow \ hat {x} + \ lambda d \ en S $
$ \ Flèche droite d \ en D $
$ \ Rightarrow G_0 \ subseteq D $
D'où prouvé.
Théorème
Necessary Condition
Soit $ f $ et $ g_i, i \ dans I $, sont différents en $ \ hat {x} \ en S, $ et $ g_j $ sont continus en $ \ hat {x} \ en S $. Si $ \ hat {x} $ est des minima locaux de $ S $, alors $ F_0 \ cap G_0 = \ phi $.
Sufficient Condition
Si $ F_0 \ cap G_0 = \ phi $ et f est une fonction pseudoconvexe à $ \ left (\ hat {x}, g_i 9x \ right), i \ in I $ sont strictement des fonctions pseudoconvexes sur certains $ \ varepsilon $ - voisinage de $ \ hat {x}, \ hat {x} $ est une solution optimale locale.
Remarques
Soit $ \ hat {x} $ un point réalisable tel que $ \ bigtriangledown f \ left (\ hat {x} \ right) = 0 $, alors $ F_0 = \ phi $. Ainsi, $ F_0 \ cap G_0 = \ phi $ mais $ \ hat {x} $ n'est pas une solution optimale
Mais si $ \ bigtriangledown g \ left (\ hat {x} \ right) = 0 $, alors $ G_0 = \ phi $, donc $ F_0 \ cap G_0 = \ phi $
Considérons le problème: min $ f \ left (x \ right) $ tel que $ g \ left (x \ right) = 0 $.
Puisque $ g \ left (x \ right) = 0 $, donc $ g_1 \ left (x \ right) = g \ left (x \ right) <0 $ et $ g_2 \ left (x \ right) = - g \ gauche (x \ droite) \ leq 0 $.
Soit $ \ hat {x} \ in S $, puis $ g_1 \ left (\ hat {x} \ right) = 0 $ et $ g_2 \ left (\ hat {x} \ right) = 0 $.
Mais $ \ bigtriangledown g_1 \ left (\ hat {x} \ right) = - \ bigtriangledown g_2 \ left (\ hat {x} \ right) $
Ainsi, $ G_0 = \ phi $ et $ F_0 \ cap G_0 = \ phi $.