108
CHAPITRE 4. ANALYSE CONVEXE OPÉRATOIRE
4.4 Sur le besoin d’un agrandissement de ∂ f
La Définition 4.4 de ∂ f (x) apparaît parfois trop contraignante, aussi bien dans
des considérations théoriques qu’algorithmiques. On est amené à proposer
un agrandissement de ∂ f "par viscosité".
Définition 4.5 Soit f ∈ 0 (E), x un point en lequel f est finie, et ε > 0.
On dit que s est un ε-sous-gradient de f en x lorsque
f (y) ≥ f (x) + +s, y − x − ε pour tout y ∈ E.
(4.60)
L’ensemble des ε-sous-gradients de f en x est appelé l’ε-sous-différentiel
de f en x et est noté ∂ ε f (x).
Avoir juste modifié la définition de ∂ f (x) par une perturbation par ε > 0 a
eu un effet "robustifiant" ; ∂ ε f (x) est par exemple une notion plus globale
que ∂ f (x) (il suffit de connaître f ∈ 0 (E) dans un voisinage de x pour
accéder à ∂ f (x), alors que ce n’est pas le cas pour ∂ ε f (x)).
Une illustration est proposée en exercice (des conditions d’optimalité globale
dans un problème d’optimisation non convexe).
Dans un contexte algorithmique, ce à quoi on a accès après calculs (via une
boîte noire) en x k est l’évaluation de f en x k et un sous-gradient ou ε k -sousgradient de f en x k . Après, il faut faire avec...
Ces aspects sont traités, entre autres, dans le Vol. 2 de [HUL].
5 Un exemple d’utilisation du sous-différentiel : les conditions
nécessaires et suffisantes d’optimalité dans un problème
d’optimisation convexe avec contraintes
Considérons le problème de minimisation convexe avec contraintes suivant :
(P)
Minimiser f (x)
x ∈ C,
où f ∈ 0 (E) et C est une partie convexe fermée de E. La seule hypothèse
que nous allons faire est : il existe ˜
x ∈ C en lequel f est finie et continue. Cela
permet d’utiliser la règle de calcul décrite en (4.54) et d’obtenir facilement
le théorème que voici.
CHAPITRE 4. ANALYSE CONVEXE OPÉRATOIRE
4.4 Sur le besoin d’un agrandissement de ∂ f
La Définition 4.4 de ∂ f (x) apparaît parfois trop contraignante, aussi bien dans
des considérations théoriques qu’algorithmiques. On est amené à proposer
un agrandissement de ∂ f "par viscosité".
Définition 4.5 Soit f ∈ 0 (E), x un point en lequel f est finie, et ε > 0.
On dit que s est un ε-sous-gradient de f en x lorsque
f (y) ≥ f (x) + +s, y − x − ε pour tout y ∈ E.
(4.60)
L’ensemble des ε-sous-gradients de f en x est appelé l’ε-sous-différentiel
de f en x et est noté ∂ ε f (x).
Avoir juste modifié la définition de ∂ f (x) par une perturbation par ε > 0 a
eu un effet "robustifiant" ; ∂ ε f (x) est par exemple une notion plus globale
que ∂ f (x) (il suffit de connaître f ∈ 0 (E) dans un voisinage de x pour
accéder à ∂ f (x), alors que ce n’est pas le cas pour ∂ ε f (x)).
Une illustration est proposée en exercice (des conditions d’optimalité globale
dans un problème d’optimisation non convexe).
Dans un contexte algorithmique, ce à quoi on a accès après calculs (via une
boîte noire) en x k est l’évaluation de f en x k et un sous-gradient ou ε k -sousgradient de f en x k . Après, il faut faire avec...
Ces aspects sont traités, entre autres, dans le Vol. 2 de [HUL].
5 Un exemple d’utilisation du sous-différentiel : les conditions
nécessaires et suffisantes d’optimalité dans un problème
d’optimisation convexe avec contraintes
Considérons le problème de minimisation convexe avec contraintes suivant :
(P)
Minimiser f (x)
x ∈ C,
où f ∈ 0 (E) et C est une partie convexe fermée de E. La seule hypothèse
que nous allons faire est : il existe ˜
x ∈ C en lequel f est finie et continue. Cela
permet d’utiliser la règle de calcul décrite en (4.54) et d’obtenir facilement
le théorème que voici.