154
CHAPITRE 6. SOUS-DIFFÉRENTIELS GÉNÉRALISÉS
Ici, I ( ¯
x) = {i | g i ( ¯
x) = 0}, la somme sur I ( ¯
x) vaut 0 si I ( ¯
x) = ∅.
Des conditions, dites de qualification des contraintes en ¯
x (conditions aux
énoncés très variés) assurent que ¯
μ 0 peut être choisi = 0 dans l’énoncé
précédent. Un exemple de condition de qualification des contraintes est :
(QC) ¯
x Il existe d tel que Dg i ( ¯
x), d < 0 pour tout i ∈ I ( ¯
x).
Auquel cas nous avons accès à :
Conditions à la KARUSH-KUHN-TUCKER (KKT). Si ¯
x est un minimiseur local de f sur S, et si une condition comme (QC) ¯
x est satisfaite, il existe
alors des ¯
μ i , i ∈ I ( ¯
x), tels que :
D f ( ¯
x) +
i∈I ( ¯
x)
¯
μ i Dg i ( ¯
x) = 0.
(6.24)
Dans le cas où les données f, g 1 , . . . , g p dans (P) sont simplement localement Lipschitz, on a, comme on pouvait s’y attendre, des conditions nécessaires d’optimalité où les différentielles Dϕ sont remplacées par des sousdifférentiels généralisés ∂ϕ. Ceci a déjà été vu dans le cas d’un problème
d’optimisation sans contraintes (cf. (iii) des Règles de calcul 6.12).
Théorème 6.13 (à la F. JOHN) Si ¯
x ∈ S est un minimiseur local de f sur S,
il existe alors ¯
μ 0 , ¯
μ i (i ∈ I ( ¯
x)) positifs et non tous nuls tels que :
0 ∈ ¯
μ 0 ∂ f ( ¯
x) +
i∈I ( ¯
x)
¯
μ i ∂g i ( ¯
x) = 0.
(6.25)
Théorème 6.14 (à la KKT) Si ¯
x ∈ S est un minimiseur local de f sur S, et
si, par exemple, on suppose
(QC) ¯
x Il existe d tel que g ◦
i ( ¯
x ; d) < 0 pour tout i ∈ I ( ¯
x),
alors il existe des ¯
μ i , i ∈ I ( ¯
x) tels que :
0 ∈ ∂ f ( ¯
x) +
i∈I ( ¯
x)
¯
μ i ∂g i ( ¯
x).
(6.26)
Démonstrations. Nous démontrons les deux théorèmes, l’un à la suite de
l’autre. La technique de démonstration a ceci d’intéressant qu’elle fait appel
elle-même à une "construction non différentiable" (et donc n’apparaissant
pas dans le monde de l’optimisation différentiable).
Par hypothèse, il existe un voisinage de ¯
x, appelons-le V , tel que
f (x) ≥ f ( ¯
x) pour tout x ∈ V ∩ S.
(6.27)
CHAPITRE 6. SOUS-DIFFÉRENTIELS GÉNÉRALISÉS
Ici, I ( ¯
x) = {i | g i ( ¯
x) = 0}, la somme sur I ( ¯
x) vaut 0 si I ( ¯
x) = ∅.
Des conditions, dites de qualification des contraintes en ¯
x (conditions aux
énoncés très variés) assurent que ¯
μ 0 peut être choisi = 0 dans l’énoncé
précédent. Un exemple de condition de qualification des contraintes est :
(QC) ¯
x Il existe d tel que Dg i ( ¯
x), d < 0 pour tout i ∈ I ( ¯
x).
Auquel cas nous avons accès à :
Conditions à la KARUSH-KUHN-TUCKER (KKT). Si ¯
x est un minimiseur local de f sur S, et si une condition comme (QC) ¯
x est satisfaite, il existe
alors des ¯
μ i , i ∈ I ( ¯
x), tels que :
D f ( ¯
x) +
i∈I ( ¯
x)
¯
μ i Dg i ( ¯
x) = 0.
(6.24)
Dans le cas où les données f, g 1 , . . . , g p dans (P) sont simplement localement Lipschitz, on a, comme on pouvait s’y attendre, des conditions nécessaires d’optimalité où les différentielles Dϕ sont remplacées par des sousdifférentiels généralisés ∂ϕ. Ceci a déjà été vu dans le cas d’un problème
d’optimisation sans contraintes (cf. (iii) des Règles de calcul 6.12).
Théorème 6.13 (à la F. JOHN) Si ¯
x ∈ S est un minimiseur local de f sur S,
il existe alors ¯
μ 0 , ¯
μ i (i ∈ I ( ¯
x)) positifs et non tous nuls tels que :
0 ∈ ¯
μ 0 ∂ f ( ¯
x) +
i∈I ( ¯
x)
¯
μ i ∂g i ( ¯
x) = 0.
(6.25)
Théorème 6.14 (à la KKT) Si ¯
x ∈ S est un minimiseur local de f sur S, et
si, par exemple, on suppose
(QC) ¯
x Il existe d tel que g ◦
i ( ¯
x ; d) < 0 pour tout i ∈ I ( ¯
x),
alors il existe des ¯
μ i , i ∈ I ( ¯
x) tels que :
0 ∈ ∂ f ( ¯
x) +
i∈I ( ¯
x)
¯
μ i ∂g i ( ¯
x).
(6.26)
Démonstrations. Nous démontrons les deux théorèmes, l’un à la suite de
l’autre. La technique de démonstration a ceci d’intéressant qu’elle fait appel
elle-même à une "construction non différentiable" (et donc n’apparaissant
pas dans le monde de l’optimisation différentiable).
Par hypothèse, il existe un voisinage de ¯
x, appelons-le V , tel que
f (x) ≥ f ( ¯
x) pour tout x ∈ V ∩ S.
(6.27)