Chapitre III. Minimisation avec contraintes. Conditions de minimalité
fonctions-contraintes h i et g j représentant S. On considère par exemple la condition (QC) x de Mangasarian-Fromovitz suivante :
(QC) x
⎧
⎪ ⎨
⎪ ⎩
Il existe d 0 tel que ∇h i (x) , d 0 = 0 pour tout i = 1, . . . , m
et ∇g j (x) , d 0 < 0 pour tout j vérifiant g j (x) = 0 ;
les vecteurs ∇h 1 (x) , . . . , ∇h m (x) sont linéairement indépendants.
Th´ eor` eme (Karush-Kuhn-Tucker). Si x ∈ O∩S est un minimum local de f sur S,
et si (QC) x a lieu, il existe alors λ =
λ 1 , . . . , λ m
∈ R m et μ = (μ 1 , . . . , μ p ) ∈ R p
tels que :
(i) ∇f (x) +
m
i=1
λ i ∇h i (x) +
p
j=1
μ j ∇g j (x) = 0 ;
(ii) μ j 0 pour tout j = 1, . . . , p ;
(iii) μ j = 0 si g j (x) < 0.
Les λ i et μ j mis en évidence dans ce théorème de Karush-Kuhn-Tucker (KKT
en abrégé) sont appelés multiplicateurs de Lagrange (ou de Lagrange-KKT).
Une hypothèse de qualification des contraintes en x, plus forte que (QC) x , est
la suivante :
(QC)
x Les vecteurs ∇h 1 (x) , . . . , ∇h m (x) , ∇g j (x) , j ∈ J (x), sont linéairement indépendants, où J (x) := {j | g j (x) = 0} est l’ensemble des indices des
contraintes (de type inégalité) actives (ou saturées) en x.
Si les fonctions h i et g j sont affines, on peut se dispenser de toute hypothèse
de qualification des contraintes et déduire quand même les conditions nécessaires
de minimalité de KKT.
Les conditions (i) - (ii) - (iii) du théorème de KKT (appelées conditions de
KKT) deviennent suffisantes en présence de convexité dans les données. Considérons à cet effet le contexte suivant :
(C)
⎧
⎪ ⎨
⎪ ⎩
f est convexe sur l’ouvert convexe O ;
les fonctions h i : R n → R sont affines ;
les fonctions g j : R n → R sont convexes.
Th´ eor` eme. Dans la situation décrite par (C) ci-dessus, les conditions de KKT
sont suffisantes pour que x soit un minimum de f sur O ∩ S.
Dans le contexte décrit par (C), il y a une condition d’énoncé simple assurant
(QC) x en tout point de S ; c’est la condition dite de Slater que voici : en notant
64
fonctions-contraintes h i et g j représentant S. On considère par exemple la condition (QC) x de Mangasarian-Fromovitz suivante :
(QC) x
⎧
⎪ ⎨
⎪ ⎩
Il existe d 0 tel que ∇h i (x) , d 0 = 0 pour tout i = 1, . . . , m
et ∇g j (x) , d 0 < 0 pour tout j vérifiant g j (x) = 0 ;
les vecteurs ∇h 1 (x) , . . . , ∇h m (x) sont linéairement indépendants.
Th´ eor` eme (Karush-Kuhn-Tucker). Si x ∈ O∩S est un minimum local de f sur S,
et si (QC) x a lieu, il existe alors λ =
λ 1 , . . . , λ m
∈ R m et μ = (μ 1 , . . . , μ p ) ∈ R p
tels que :
(i) ∇f (x) +
m
i=1
λ i ∇h i (x) +
p
j=1
μ j ∇g j (x) = 0 ;
(ii) μ j 0 pour tout j = 1, . . . , p ;
(iii) μ j = 0 si g j (x) < 0.
Les λ i et μ j mis en évidence dans ce théorème de Karush-Kuhn-Tucker (KKT
en abrégé) sont appelés multiplicateurs de Lagrange (ou de Lagrange-KKT).
Une hypothèse de qualification des contraintes en x, plus forte que (QC) x , est
la suivante :
(QC)
x Les vecteurs ∇h 1 (x) , . . . , ∇h m (x) , ∇g j (x) , j ∈ J (x), sont linéairement indépendants, où J (x) := {j | g j (x) = 0} est l’ensemble des indices des
contraintes (de type inégalité) actives (ou saturées) en x.
Si les fonctions h i et g j sont affines, on peut se dispenser de toute hypothèse
de qualification des contraintes et déduire quand même les conditions nécessaires
de minimalité de KKT.
Les conditions (i) - (ii) - (iii) du théorème de KKT (appelées conditions de
KKT) deviennent suffisantes en présence de convexité dans les données. Considérons à cet effet le contexte suivant :
(C)
⎧
⎪ ⎨
⎪ ⎩
f est convexe sur l’ouvert convexe O ;
les fonctions h i : R n → R sont affines ;
les fonctions g j : R n → R sont convexes.
Th´ eor` eme. Dans la situation décrite par (C) ci-dessus, les conditions de KKT
sont suffisantes pour que x soit un minimum de f sur O ∩ S.
Dans le contexte décrit par (C), il y a une condition d’énoncé simple assurant
(QC) x en tout point de S ; c’est la condition dite de Slater que voici : en notant
64